移动应用开发实验室大一考核题解

2024-04-18 22:29

本文主要是介绍移动应用开发实验室大一考核题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

238. 除自身以外数组的乘积

题解:

我们使用L数组,L[i]代表i对应元素左侧所有元素的乘积;

使用R数组,R[i]代表i对应元素右侧所有元素的乘积;

这样ret[i]数组值为L[i] * R[i]

注意L[0]的值为1,第一个元素左侧无元素,初始化为1;

R[n-1]同理

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int* ret = (int*)malloc(sizeof(int) * numsSize);int* L = (int*)malloc(sizeof(int) * numsSize);int* R = (int*)malloc(sizeof(int) * numsSize);int i = 0;L[0] = 1;R[numsSize - 1] = 1;for (i = 1; i < numsSize; i++) {L[i] = L[i - 1] * nums[i - 1];}for (i = numsSize - 2; i >= 0; i--) {R[i] = R[i + 1] * nums[i + 1];}for (i = 0; i < numsSize; i++) {ret[i] = L[i] * R[i];}*returnSize = numsSize;return ret;
}

73. 矩阵置零

题解:

第一次用两个标记数组遍历二维数组进行标记需要置零的行和列,第二次遍历通过两个标记数组使数组置零

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {int* arri = (int*)malloc(sizeof(int) * matrixSize);int* arrj = (int*)malloc(sizeof(int) * (*matrixColSize));memset(arri, 0, sizeof(int) * matrixSize);memset(arrj, 0, sizeof(int) * (*matrixColSize));int i = 0;int j = 0;for (i = 0; i < matrixSize; i++) {for (j = 0; j < (*matrixColSize); j++) {if (matrix[i][j] == 0) {arri[i] = 1;arrj[j] = 1;}}}for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < (*matrixColSize); j++) {if (arri[i] || arrj[j]) {matrix[i][j] = 0;}}}
}

394. 字符串解码

遍历输入字符串 s,对每个字符进行处理。

如果遇到 [,则将之前累积的数字压入 nums 栈,将 [ 压入 letter 栈,并重置 tmp 为0,用于记录接下来的倍数。

如果遇到 ],则从 letter 栈中取出字符,直到遇到 [,将这些字符组成的子串进行反转,然后根据倍数将其添加到 letter 栈中。

如果遇到数字,则将其转换为整数并存储在 tmp 中。

如果遇到其他字符,则直接将其压入 letter 栈中。最后,将 letter 栈中的字符拼接成一个字符串,并返回

char* decodeString(char* s) {char* result = (char*)malloc(sizeof(char) * 10000);int index = -1; int length = strlen(s); for (int i = 0; i < length; i++) {if (s[i] == ']') {// 找到与当前右括号匹配的左括号int rightChar = index;int leftChar = index;while (result[leftChar] != '[') {leftChar--;}leftChar++;int rightNum = leftChar - 2; // 右括号前一位索引int leftNum = rightNum;// 找到左括号前的数字字符的索引while (leftNum >= 0 && result[leftNum] >= '0' && result[leftNum] <= '9')leftNum--;if (leftNum != 0)leftNum++;char repeatArr[3000] = {0}; // 用于记录要重复的元素int repeatArrSize = 0; // repeatArr 数组的大小// 将左右括号之间的字符复制到 repeatArr 数组中for (int h = leftChar; h <= rightChar; h++) {repeatArr[repeatArrSize++] = result[h];}int repeatTimes = 0; // 记录重复次数// 将数字字符转换为整数for (int h = leftNum; h <= rightNum; h++) {repeatTimes *= 10;repeatTimes = repeatTimes + result[h] - '0';}index = leftNum - 1; // 更新结果字符串栈顶指针,指向左括号前的位置// 将 repeatArr 数组中的字符按重复次数添加到结果字符串中while (repeatTimes--) {for (int z = 0; z < repeatArrSize; z++)result[++index] = repeatArr[z];}} else {result[++index] = s[i]; // 将非右括号字符添加到结果字符串中}}// 存储解码后的字符串char* decodedString = (char*)malloc(sizeof(char) * 10000);// 将结果字符串复制到 decodedString 数组中for (int i = 0; i <= index; i++)decodedString[i] = result[i];decodedString[index + 1] = '\0'; // 添加字符串结束符free(result);return decodedString; 
}

23. 合并 K 个升序链表

先学会21. 合并两个有序链表,就可以做出这道题。

对于21题,代码是下面的mergeTwoLists函数。

合并两个有序链表的思路是递归:

我们要判断 list1list2 哪一个链表的头节点的值更小。

     list1->next = mergeTwoLists(list1->next, list2);

假设list1的头结点小于 list2,就把list1的头结点的next指向mergeTwoLists(list1->next, list2)

这样我们就把第一个最小的节点找到了,下一步我们将比较之后小的节点的下一个节点另一条链表的节点比较,持续递归。

直到结束条件(任意一个为空),那么我们就返回另一条链表,这样可以合并好完整的链表。

那么本题也就有了思路,只要遍历调用该函数,最终就可以合并N条了

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL) {return list2;} else if (list2 == NULL) {return list1;} else if (list1->val < list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (listsSize == 1) {return lists[0];}if (listsSize == 0) {return NULL;}int i = 0;for (i = 1; i < listsSize; i++) {lists[0] = mergeTwoLists(lists[0], lists[i]);}return lists[0];
}

232. 用栈实现队列

入队列入栈。

出队列由于顺序原因需要另一个栈,需要出队列时,把栈的所有元素入栈到另一个栈中。所以需要两个栈一个输入栈,一个输出栈。

myQueuePop 弹出队列的头部元素,从第二个栈中弹出元素,如果第二个栈为空,先将第一个栈的元素复制到第二个栈中,然后再弹出。写的时候,在出栈操作完后又讲stackout元素复制回了stackin,但不这样好像也行。后来明白了当执行出队操作时,先检查第二个栈是否为空,如果为空,则将第一个栈的元素移动到第二个栈中,然后从第二个栈中弹出元素,实现了出队操作。而不再需要将元素复制回第一个栈,因为出队操作不会影响到第一个栈中的元素顺序。

myQueuePeek函数和myQueuePop函数基本一致,最后不出栈stackout的栈顶元素即可。

typedef struct {int stackintop, stackouttop;int stackin[100], stackout[100];
} MyQueue;MyQueue* myQueueCreate() {MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));queue->stackintop = 0;queue->stackouttop = 0;return queue;
}void myQueuePush(MyQueue* obj, int x) {obj->stackin[obj->stackintop++] = x;
}int myQueuePop(MyQueue* obj) {if (obj->stackouttop == 0) {while (obj->stackintop > 0) {obj->stackout[obj->stackouttop++] = obj->stackin[--obj->stackintop];}}return obj->stackout[--obj->stackouttop];
}int myQueuePeek(MyQueue* obj) {if (obj->stackouttop == 0) {while (obj->stackintop > 0) {obj->stackout[obj->stackouttop++] = obj->stackin[--obj->stackintop];}}return obj->stackout[obj->stackouttop - 1];
}bool myQueueEmpty(MyQueue* obj) {return obj->stackintop == 0 && obj->stackouttop == 0;
}void myQueueFree(MyQueue* obj) {free(obj);
}

61. 旋转链表

先遍历链表,遍历到最后一个节点,把他链接成一个环形链表。

同时计算链表长度,用k取模长度,防止len减成负数。

目的是找到旋转后链表的头结点的前一个元素,然后断开那一条next

此时我们找一下从旋转前的尾结点开始,遍历多少次,可以达到找到旋转后链表的头结点的前一个元素的目的,是len - k次。对着示例图模拟一下就可以得出了。

struct ListNode* rotateRight(struct ListNode* head, int k) {if(k == 0 || head == NULL){return head;}struct ListNode* tail = head;int len = 1;while(tail->next){tail = tail->next;len++;}tail->next = head;k = len - k % len;while(k--){tail = tail->next;}struct ListNode* ret = tail->next;tail->next = NULL;return ret;
}

392. 判断子序列

初始化两个指针slowfast,分别指向st的初始位置。不断循环进行匹配.

匹配成功则slowfast同时右移,匹配s的下一个位置,匹配失败则fast右移,尝试用t的下一个字符匹配s

这样下来最后如果slow的数值等于s的长度,那么就说明s中的在t中,都能按顺序找到。返回true

bool isSubsequence(char* s, char* t) {int slow = 0;int fast = 0;int lena = strlen(s);int lenb = strlen(t);while (fast < lenb) {while (fast < lenb && s[slow] == t[fast]) {slow++;fast++;}while (fast < lenb && s[slow] != t[fast]) {fast++;}}if (slow == lena) {return true;} else {return false;}
}

125. 验证回文串

最直观好想的方法是把与阿UN子非固化窜处理一下,在进行回文的判断即可。

bool ishui(char* s) {int len = strlen(s);int left = 0;int right = len - 1;while (left < right) {if (s[left] == s[right]) {left++;right--;} else {return false;}}return true;
}bool isPalindrome(char* s) {int len = strlen(s);int slow = 0;int fast = 0;// 遍历字符串,将有效字符移到字符串前部分while (fast < len) {// 将字母和数字移到前部分while (fast < len && ((s[fast] >= 'a' && s[fast] <= 'z') || (s[fast] >= '0' && s[fast] <= '9'))) {s[slow++] = s[fast++];}// 处理非字母数字的字符(如果是大写字母就转换成小写字母)while (fast < len && (s[fast] < 'a' || s[fast] > 'z')) {if (s[fast] >= 'A' && s[fast] <= 'Z') {s[fast] += 32;break;} else if (s[fast] >= '0' && s[fast] <= '9') {break;}fast++;}}s[slow] = '\0'; // 添加字符串结尾标志// 判断前部分是否为回文串return ishui(s);
}

147. 对链表进行插入排序

链表的插入排序的实现,和数组的插入排序思路一样,每次从未排序部分取出一个元素,放到已排序部分的合适位置。

不过对于单链表来说,我们只能从前往后遍历,所以我们需要利用指针从前往后查找合适的插入位置。

先构建一个虚拟头结点,构造三个指针。

分别是已排序部分的lastSorted指针,指向已排序部分最后一个元素,主要是用来方便交换节点的。

另一个是cur,用于指向未排序部分的第一个元素,lastSorted->next

还有一个是pre,用于找到合适的插入位置。

具体实现如下

cur->val >= lastSorted->val表示当前未排序部分的第一个元素大于等于已排序部分最后一个元素,所以不必交换。直接继续遍历

else情况利用pre指针,找到pre->next->val大于cur->val的,找到后进行插入操作,

lastSorted->next = cur->next;
cur->next = pre->next;
pre->next = cur;

这样我们就把cur放在了合适的位置。

最终返回虚拟头结点的下一个节点。

struct ListNode* insertionSortList(struct ListNode* head) {if (head == NULL) {return head;}struct ListNode* shead = (struct ListNode*)malloc(sizeof(struct ListNode));shead->next = head;shead->val = 0;struct ListNode* lastSorted = head;struct ListNode* cur = head->next;while (cur) {if (cur->val >= lastSorted->val) {lastSorted = lastSorted->next;} else {// 从前向后查找struct ListNode* pre = shead;while (pre->next->val <= cur->val) {pre = pre->next;}lastSorted->next = cur->next;cur->next = pre->next;pre->next = cur;}cur = lastSorted->next;}return shead->next;
}

309. 买卖股票的最佳时机含冷冻期

dp数组含义:

dp[i][j]i表示第i天,j[0 - 4]五个状态,dp[i][j]表示第i天状态j所剩最大现金。

共存在五种状态

  1. 无操作
  2. 第一次持有股票
  3. 第一次不持有股票
  4. 第二次持有股票
  5. 第二次不持有股票

初始化:

  • dp[0][0]:买入股票,所以是 -prices[0]
  • dp[0][1]dp[0][2]dp[0][3]:分别是0,因为第一天不可能处于冷冻期或不持有股票。

接下来遍历:

  • dp[i][0]:可以从前一天的持有股票状态(dp[i - 1][0])转换而来,也可以在冷冻期结束后购买股票(dp[i - 1][1] - prices[i])或者在新冷冻期后购买股票(dp[i - 1][3] - prices[i])。
  • dp[i][1]:保持卖出股票的状态,或者保持前一天的冷冻期状态。
  • dp[i][2]:今天卖出股票,所以是 dp[i - 1][0] + prices[i]
  • dp[i][3]:冷冻期状态,即前一天的卖出股票状态。

最终返回最后一天可能的最大利润。

int maxProfit(int* prices, int pricesSize) {int** dp = (int**)malloc(sizeof(int*) * pricesSize);int i = 0;for (i = 0; i < pricesSize; i++) {dp[i] = (int*)malloc(sizeof(int) * 4);}dp[0][0] = -prices[0];dp[0][1] = 0;dp[0][2] = 0;dp[0][3] = 0;for (i = 1; i < pricesSize; i++) {dp[i][0] =  fmax(dp[i - 1][0], fmax(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i])); // 持有股票状态dp[i][1] = fmax(dp[i - 1][1], dp[i - 1][3]); // 保持卖出股票的状态dp[i][2] = dp[i - 1][0] + prices[i];         // 今天卖出股票dp[i][3] = dp[i - 1][2];                     // 冷冻期状态}return fmax(dp[pricesSize - 1][1], fmax(dp[pricesSize - 1][2], dp[pricesSize - 1][3]));
}

35. 搜索插入位置

这道二分题目的写法有很多,这里展示两种左闭右闭的写法。

首先对于第一个代码来说:

  • 如果 nums[mid] < target,则说明目标值在当前元素后面,应该插入到当前元素的后面,因此left = mid + 1
  • 如果 nums[mid] > target,则说明目标值在当前元素前面,应该插入到当前元素的位置,因此right = mid - 1
  • 如果 nums[mid] == target,则说明找到了目标值,直接返回 mid

最后返回 left 或者 right + 1 也都是正确的,因为它们都是指向应该插入的位置的下标。

然后第二个代码

ans 用于记录可能的插入位置。通过二分不断缩小范围,找到目标值或插入位置。

在每次循环中,如果当前中间元素大于或等于目标值,则更新 ans 为当前中间位置 mid。随着循环进行,ans 会记录下第一个大于或等于目标值的元素的索引位置。而由于 ans 初始值为数组大小,若找不到满足条件的元素,插入位置为数组末尾。

最终ans 存储的就是答案。

int searchInsert(int* nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid = 0;while(left <= right){mid = left + (right - left) / 2;if(nums[mid] < target) {left = mid + 1;} else if(nums[mid] > target) {right = mid - 1;} else if(nums[mid] == target) {return mid;}}return right+1;//return left;
}
int searchInsert(int* nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int ans = numsSize;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {ans = mid;	//ans中存储的是第一个大于或等于目标值的元素的索引位置right = mid - 1;} else {left = mid + 1;}}return ans;
}


如有错误烦请指正。

感谢您的阅读。

这篇关于移动应用开发实验室大一考核题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/915985

相关文章

Qt把文件夹从A移动到B的实现示例

《Qt把文件夹从A移动到B的实现示例》本文主要介绍了Qt把文件夹从A移动到B的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录如何移动一个文件? 如何移动文件夹(包含里面的全部内容):如何删除文件夹:QT 文件复制,移动(

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

基于Python开发PDF转PNG的可视化工具

《基于Python开发PDF转PNG的可视化工具》在数字文档处理领域,PDF到图像格式的转换是常见需求,本文介绍如何利用Python的PyMuPDF库和Tkinter框架开发一个带图形界面的PDF转P... 目录一、引言二、功能特性三、技术架构1. 技术栈组成2. 系统架构javascript设计3.效果图

基于Python开发PDF转Doc格式小程序

《基于Python开发PDF转Doc格式小程序》这篇文章主要为大家详细介绍了如何基于Python开发PDF转Doc格式小程序,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用python实现PDF转Doc格式小程序以下是一个使用Python实现PDF转DOC格式的GUI程序,采用T

使用Python开发一个图像标注与OCR识别工具

《使用Python开发一个图像标注与OCR识别工具》:本文主要介绍一个使用Python开发的工具,允许用户在图像上进行矩形标注,使用OCR对标注区域进行文本识别,并将结果保存为Excel文件,感兴... 目录项目简介1. 图像加载与显示2. 矩形标注3. OCR识别4. 标注的保存与加载5. 裁剪与重置图像

Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

《SpringAI集成DeepSeek三步搞定Java智能应用的详细过程》本文介绍了如何使用SpringAI集成DeepSeek,一个国内顶尖的多模态大模型,SpringAI提供了一套统一的接口,简... 目录DeepSeek 介绍Spring AI 是什么?Spring AI 的主要功能包括1、环境准备2

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

Android开发中gradle下载缓慢的问题级解决方法

《Android开发中gradle下载缓慢的问题级解决方法》本文介绍了解决Android开发中Gradle下载缓慢问题的几种方法,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、网络环境优化二、Gradle版本与配置优化三、其他优化措施针对android开发中Gradle下载缓慢的问

MobaXterm远程登录工具功能与应用小结

《MobaXterm远程登录工具功能与应用小结》MobaXterm是一款功能强大的远程终端软件,主要支持SSH登录,拥有多种远程协议,实现跨平台访问,它包括多会话管理、本地命令行执行、图形化界面集成和... 目录1. 远程终端软件概述1.1 远程终端软件的定义与用途1.2 远程终端软件的关键特性2. 支持的

使用Go语言开发一个命令行文件管理工具

《使用Go语言开发一个命令行文件管理工具》这篇文章主要为大家详细介绍了如何使用Go语言开发一款命令行文件管理工具,支持批量重命名,删除,创建,移动文件,需要的小伙伴可以了解下... 目录一、工具功能一览二、核心代码解析1. 主程序结构2. 批量重命名3. 批量删除4. 创建文件/目录5. 批量移动三、如何安