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

题解：

我们使用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;
}

题解：

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

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;}}}
}

遍历输入字符串 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; 
}

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

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

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

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

     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];
}

入队列入栈。

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

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);
}

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

同时计算链表长度，用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;
}

初始化两个指针slow和fast，分别指向s和t的初始位置。不断循环进行匹配.

匹配成功则slow和fast同时右移，匹配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;}
}

最直观好想的方法是把与阿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);
}

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

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

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

分别是已排序部分的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;
}

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]));
}

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

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

• 如果 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;
}

如有错误烦请指正。

感谢您的阅读。