大一下第一次考核题解

大一下第一次考核题解

1.反转链表（禁止递归）

原题链接：

206. 反转链表

这道题已经做过很多次了，这里直接上代码，其他各种解法与思路已经在反转链表详解（C语言）中详细说明了，这里就不再赘述了。

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* pre = NULL;struct ListNode* cur = head;while (cur) {struct ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;
}

2.用栈实现队列（要求C语言）

原题链接：

232. 用栈实现队列

代码随想录栈与队列部分第一题，思路很简单，就是一道模拟题，主要考察对栈和队列的掌握程度。

思路：定义两个栈，可以直接用数组模拟，一个栈stack1用来处理入队操作，另一个栈stack2用来处理出队操作，入队直接将元素压入stack1中，出队时先将stack1中所有元素压入stack2中，由于栈是先进后出，stack2的顶部元素就是队列的队头元素，弹出顶部元素后，再将stack2剩余元素压入stack1中。代码如下：

typedef struct {int top1, top2;int stack1[100], stack2[100];
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));obj->top1 = -1;obj->top2 = -1;return obj;
}void myQueuePush(MyQueue* obj, int x) {obj->stack1[++(obj->top1)] = x;
}int myQueuePop(MyQueue* obj) {int top1 = obj->top1;int top2 = obj->top2;while (top1 >= 0) {obj->stack2[++top2] = obj->stack1[top1--];}int top = obj->stack2[top2--];while (top2 >= 0) {obj->stack1[++top1] = obj->stack2[top2--];}obj->top1 = top1;obj->top2 = top2;return top;
}int myQueuePeek(MyQueue* obj) {return obj->stack1[0];
}bool myQueueEmpty(MyQueue* obj) {return obj->top1 == -1;
}void myQueueFree(MyQueue* obj) {obj->top1 = -1;
}

3.随机链表的复制

原题链接：

138. 随机链表的复制

这个题比较难的点在于链表每个节点都有一个random指针，需要知道 random指向的那个节点，在复制链表中是哪个节点。

这里的思路是直接将复制的节点添加在原链表，例如1 2 3，一次复制每个节点，把新节点直接插入原节点后面形成一个交错链表1 1' 2 2' 3 3'。然后遍历这个链表，假设1的random指向3，那么1'的random就指向3的下一个节点3'，这样就能找到复制链表每个节点的random。最后将这个交错链表分离即可。

struct Node* copyRandomList(struct Node* head) {if (head == NULL) {return NULL;}struct Node* cur = head;while (cur) {struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;copy->random = NULL;cur->next = copy;cur = copy->next;}cur = head;while (cur) {if (cur->random) {cur->next->random = cur->random->next;}cur = cur->next->next;}struct Node* newHead = head->next;cur = head;while (cur->next->next) {struct Node* copy = cur->next;cur->next = copy->next;copy->next = copy->next->next;cur = cur->next;}cur->next = NULL;return newHead;
}

4.字符串解码

原题链接：

394. 字符串解码

这道题之前做过，当时没做出来，也没去细看，考核时这道题看都没看直接跳过了，后面重新做了一遍，发现这道题并不难。

解码规则：

• 遇到数字，表示重复次数
• 遇到[，表示一个新的嵌套结构的开始
• 遇到]，表示当前嵌套结构结束，要将它展开

例：对字符串3[a2[c]]进行解码：

2[c]表示“c”重复2次，也就是“cc”

a2[c]就是把“a” + “cc”，也就是acc

3[a2[c]]就是把acc重复3次，最后答案就是accaccacc

递归

思路：可以从字符串开头往后扫，每当遇到一个数字，比如3， 后面肯定跟着一个[...]，然后解析[...]里面的内容，解析出来之后，把它重复3次，再拼接到结果里。

递归的关键就是：遇到[就进入递归，遇到]就返回这一层的结果。

还要注意在递归过程中要用一个指针记录目前的遍历位置。

char* decode(char* s, int* i) {char* res = (char*)calloc(10000, sizeof(char)); while (s[*i] && s[*i] != ']') {//遇到数字，进行递归解析if (isdigit(s[*i])) {int num = 0;//先将数字解析出来，可能是多位数while (isdigit(s[*i])) {num = num * 10 + (s[*i] - '0');(*i)++;}//跳过'['(*i)++;//递归解析[...]中的内容char* sub = decode(s, i);//跳过']'(*i)++;//把解析结果重复num次拼接到结果res中for (int j = 0; j < num; j++) {strcat(res, sub);}//释放内存free(sub);} else {//普通字符，直接加到结果中int len = strlen(res);res[len] = s[*i];res[len + 1] = '\0';(*i)++;}}return res;
}char* decodeString(char* s) {//i用于指向当前遍历位置int i = 0;return decode(s, &i);
}

这种嵌套结构用递归很好处理，思路也很清晰，遇到[就递归处理内部。那么非递归怎么写呢？怎么用栈模拟这个过程？

非递归

思路：可以使用两个栈，一个栈用来存储每个[前面的数字，一个栈用来存储[前面已经构建好的字符串。同时需要维护一个cur用来表示正在构建的字符串，一个num来表示当前累计的数字，然后需要对四种字符分类操作：

• 遇到数字0-9，把数字累加起来；
• 遇到[，入栈，把当前数字和字符串都保存起来，并重置cur和num；
• 遇到字母，加入当前正在构建的字符串cur；
• 遇到]，出栈，取出栈顶的数字和字符串，把当前构建的 cur 重复num次，然后接到上次字符串后面，成为新的 cur

代码如下：

char* decodeString(char* s) {char* strStack[100];int numStack[100];int top = -1;char* cur = (char*)calloc(10000, sizeof(char));int num = 0;for (int i = 0; s[i]; i++) {if (isdigit(s[i])) {num = num * 10 + (s[i] - '0');} else if (s[i] == '[') {strStack[++top] = cur;numStack[top] = num;cur = (char*)calloc(10000, sizeof(char));num = 0;} else if (s[i] == ']') {char* pre = strStack[top];int repeat = numStack[top--];for (int j = 0; j < repeat; j++) {strcat(pre, cur);}free(cur);cur = pre;} else {int len = strlen(cur);cur[len] = s[i];cur[len + 1] = '\0';}}return cur;
}

5.长度为K子数组中的最大和

原题链接：

2461. 长度为 K 子数组中的最大和

这道题本身作为滑动窗口题并不难，但他不允许有重复元素，考核时，这道题也是看都没看，因为之前做过这道题，隐约记得要使用哈希表，要我拿参C语言手搓一个哈希表，还很困难。但是重新做了一遍之后，发现数据量其实并不大，完全可以用数组模拟。

当时做这道题的时候想岔了，以为要开$10^5\ast 10^5$的大小的数组，无论是在全局定义，还是用动态开辟，无一例外，全部报错溢出，$10^{10}$个int已经是几十GB了，怎么可能开出来。今天重新看才发现只需要开100000的数组就可以了，剩下就是滑动窗口逻辑的实现，很简单，如果窗口长度等于k就更新答案，如果长度大于k或者出现重复元素，就将窗口左边界向右移动，具体代码实现如下：

#define MAX(a, b) ((a > b) ? (a) : (b))long long maximumSubarraySum(int* nums, int numsSize, int k) {int map[100001] = {0};long long ans = 0, sum = 0;int left = 0;for (int i = 0; i < numsSize; i++) {sum += nums[i];map[nums[i]]++;while (map[nums[i]] > 1 || (i - left + 1) > k) {          sum -= nums[left];map[nums[left]]--;left++;}if ((i - left + 1) == k) {ans = MAX(ans, sum);}}return ans;
}

6.买卖股票的最佳时机Ⅱ

原题链接：

122. 买卖股票的最佳时机 II

与经典的买卖股票的最佳时机问题（最多进行一次交易）不同，这里可以进行多次交易，即你可以在任何时候买入并卖出股票，只要能获得利润。

贪心

这道题的关键在于可以进行多次交易，所以如果当前的股票价格比前一天的股票价格高，那么我们就能获得一个正的利润。因此，只要每次股票价格上升时就进行买卖，我们就能获得最大利润。

思路：只要当前股价高于前一天的股价，就认为我们在前一天买入，今天卖出，获得的利润就是 prices[i] - prices[i - 1]。

int maxProfit(int* prices, int pricesSize) {int ans = 0;for (int i = 1; i < pricesSize; i++) {int profix = prices[i] - prices[i - 1];ans += profix > 0 ? profix : 0;}return ans;
}

动态规划

思路：可以通过动态规划来模拟每一天的买入、卖出行为，并定义一些状态来表示每个时刻的最佳利润。

可以定义两个状态：

• dp[i][0]：表示第 i 天结束时，不持有股票的最大利润。
• dp[i][1]：表示第 i 天结束时，持有股票的最大利润。

状态转移方程：

• dp[i][0]：不持有股票的最大利润，可以由两种情况转移过来：

  • 前一天就不持有股票：即 dp[i - 1][0]。

  • 前一天持有股票并在今天卖出：即 dp[i - 1][1] + prices[i]。

  因此，dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])。

• dp[i][1]：持有股票的最大利润，可以由两种情况转移过来：

  • 前一天就持有股票：即 dp[i - 1][1]。
  • 前一天不持有股票并在今天买入：即 dp[i - 1][0] - prices[i]。

  因此，dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])。

初始化：

• dp[0][0] = 0，表示第 0 天不持有股票的最大利润是 0。
• dp[0][1] = -prices[0]，表示第 0 天买入股票后的最大利润是负的股票价格。

dp[n - 1][0]即在最后一天结束时不持有股票的最大利润为最终答案。代码如下：

#define MAX(a, b) ((a) > (b) ? (a) : (b))int maxProfit(int* prices, int pricesSize) {int dp[pricesSize][2];dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < pricesSize; i++) {dp[i][0] = MAX(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = MAX(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[pricesSize - 1][0];
}

空间优化：

因为每次计算我们只需要知道前一天的状态，可以只保存dp[i - 1]的结果，可以将空间复杂度优化到O(1)

#define MAX(a, b) ((a) > (b) ? (a) : (b))int maxProfit(int* prices, int pricesSize) {int dp0 = 0, dp1 = -prices[0];for (int i = 1; i < pricesSize; i++) {int new0 = MAX(dp0, dp1 + prices[i]);dp1 = MAX(dp1, dp0 - prices[i]);dp0 = new0;}return dp0;
}

7.接雨水

原题链接：

42. 接雨水

每根柱子能接多少水主要取决于，前面柱子最大高度和后面柱子最大高度中较低的那根柱子与这根柱子的高度差。因为如果这根柱子比他左边柱子都高，水就从左边全流出去，或者比右边柱子都高，水也会全部流出去。

前缀和分解

前后缀分解思路：用两个额外数组分别记录前缀最大值和后缀最大值，对于第$i$根柱子用他俩的最小值减去这根柱子的高度，就是这根柱子能接多少水。

时间复杂度为$O(n)$，空间复杂度为$O(n)$

int trap(int* height, int heightSize) {if(heightSize < 3) return 0;    // 处理边界情况int* prevMax = (int*)malloc(sizeof(int) * heightSize);   // preMmax[i] 表示从 height[0] 到 height[i] 的最大值int* endMax = (int*)malloc(sizeof(int) * heightSize);   // endMax[i] 表示从 height[i] 到 height[heightSize - 1] 的最大值prevMax[0] = height[0];endMax[heightSize - 1] = height[heightSize - 1];for(int i = 1; i < heightSize; i++){prevMax[i] = prevMax[i - 1] > height[i] ? prevMax[i - 1] : height[i];}for(int i = heightSize - 2; i >= 0; i--){endMax[i] = endMax[i + 1] > height[i] ? endMax[i + 1] : height[i];}int ans = 0;for(int i = 0; i < heightSize - 1; i++){int min = prevMax[i] < endMax[i] ? prevMax[i] : endMax[i];ans += min - height[i]; }free(prevMax);free(endMax);return ans;
}

相向双指针

思路：用两个指针分别指向头和尾，那么前后缀最大值就可以分别用一个变量来表示，也就是一边移动指针，一边更新最大值，直到两个指针错开，即$left>right$时结束。

时间复杂度：$O(n)$，空间复杂度：$O(1)$

int trap(int* height, int heightSize) {if(heightSize < 3) return 0;    // 处理边界情况int ans = 0, left = 0, right = heightSize - 1;int preMax = 0, sufMax = 0;while(left <= right){preMax = preMax > height[left] ? preMax : height[left];sufMax = sufMax > height[right] ? sufMax : height[right];if(preMax < sufMax){ans += preMax - height[left];left++;} else{ans += sufMax - height[right];right--;}}return ans;
}

单调栈

思路：维护一个单调递减栈来高效地计算雨水量。遍历每个柱子，利用栈来找到当前柱子上面可以接的水。对于每个柱子，如果它比栈顶的柱子高，就开始计算水量，弹出栈顶元素，计算当前元素和栈顶元素之间的水量。更新栈顶元素，继续计算。如果当前柱子比栈顶的柱子矮或相等，就将当前柱子压入栈中。

时间复杂度：$O(n)$，空间复杂度：$O(n)$

int trap(int* height, int heightSize) {int ans = 0;int stack[20000];int top = -1;for(int i = 0; i < heightSize; i++) {int h_right = height[i];while(top >= 0 && h_right >= height[stack[top]]) {int h = height[stack[top--]];if(top < 0) {break;}int left = stack[top];int min = height[left] < h_right ? height[left] : h_right;ans += (min - h) * (i - left - 1);}stack[++top] = i;}return ans;
}

8.合并K个升序链表

原题链接：

23. 合并 K 个升序链表

这道题合并K个升序链表，简单做法就是写个for循环，依次合并两个升序链表即可。

暴力

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

分治

对上面这种写法进行优化，可以采取分治的思想，将K个链表尽量均匀的分成两部分，分别对这两部分进行合并，最后再合并这两部分，按照这种思路，不断二分，直到最后只剩一个链表或者为空，再进行回溯。那不还是要合并K个链表吗，乍一看好像没啥区别，但是注意链表的总结点数是一定的，而第一种暴力解法，一共要进行$K$（链表数量）次合并，而第二种则只需要$logK$次，链表数量较少的时候看不出来什么，但数据量很大的时候这种优化是非常可观的。代码如下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode dummyHead;dummyHead.next = NULL;struct ListNode* cur = &dummyHead;while (list1 && list2) {if (list1->val > list2->val) {cur->next = list2;list2 = list2->next;} else {cur->next = list1;list1 = list1->next;}cur = cur->next;}if (list1) {cur->next = list1;} else{cur->next = list2;}return dummyHead.next;
}struct ListNode* split(struct ListNode** lists, int l, int r) {int d = r - l;if (d == 0) {return NULL;}if (d == 1) {return lists[l];}struct ListNode* left = split(lists, l, l + d / 2);struct ListNode* right = split(lists, l + d / 2, r);return mergeTwoLists(left, right);
}struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {return split(lists, 0, listsSize);
}