大一上考核题解

文章目录

- [238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/)
- - - 代码
    - 题解
- [73. 矩阵置零](https://leetcode.cn/problems/set-matrix-zeroes/)
- - - 代码
    - 题解
- [394. 字符串解码](https://leetcode.cn/problems/decode-string/)
- - - 代码
    - 题解
- [23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/)
- - - 代码
    - 题解
- [232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/)
- - - 代码
    - 题解
- [61. 旋转链表](https://leetcode.cn/problems/rotate-list/)
- - - 代码
    - 题解
- [392. 判断子序列](https://leetcode.cn/problems/is-subsequence/)
- - - 代码
    - 题解

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

代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int* arr1 = (int*)malloc(sizeof(int) * (numsSize + 1));int* arr2 = (int*)malloc(sizeof(int) * (numsSize + 1));for (int i = 0; i < numsSize; i++) {if (i == 0)arr1[i] = nums[i];elsearr1[i] = nums[i] * arr1[i - 1];}for (int i = numsSize - 1; i >= 0; i--) {if (i == numsSize - 1)arr2[i] = nums[i];elsearr2[i] = nums[i] * arr2[i + 1];}int* ans = (int*)malloc(sizeof(int) * (numsSize + 1));for (int i = 0; i < numsSize; i++) {if (i == 0)ans[i] = arr2[i + 1];else if (i == numsSize - 1)ans[i] = arr1[i - 1];elseans[i] = arr1[i - 1] * arr2[i + 1];}*returnSize = numsSize;return ans;
}

题解

本题主要思路就是重新创建两个数组，一个用来记录下标为i左边数字的乘积和，一个用来记录下标为i右边数字的乘积和，这样子当我们统计的除nums[i]之外个元素的乘积就是arr1[i-1]*arr2[i+1]。

下面是具体思路：

我们开辟两个数组arr1和arr2，分别正序与逆序遍历整个数组去给arr1和arr2赋值；
正序遍历nums数组，当i==0时我们直接让arr1[i]=nums[i]就可以了，后面的我们就需要令arr1[i]等于nums[i]*arr[i-1]；
逆序遍历nums数组和正序遍历一样统计后面的乘积就可以了；
最后我们统计ans数组数值，我们只需要让ans[i]=arr1[i-1]*arr[i+1]（两个边界特殊处理）就可以了。

73. 矩阵置零

代码

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {int hash[201][201] = {0};for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < *matrixColSize; j++) {if (matrix[i][j] == 0)hash[i][j] = 1;}}for (int i = 0; i < 201; i++) {for (int j = 0; j < 201; j++) {if (hash[i][j] == 1) {int hang = i;int lie = j;for (int p = 0; p < *matrixColSize; p++)matrix[hang][p] = 0;for (int p = 0; p < matrixSize; p++)matrix[p][lie] = 0;}}}
}

题解

因为我们直接在原数组中进行修改会无法判断数组中的0是原题还是修改之后的，所以本题的最直接的思路就是我们直接重新创建一个二维数组进行标记原数组为0的位置，然后重新遍历一遍新创建的数组，当遇到之前标记的位置，我们就把数组对应的行和列全部设置为0，就可以实现本题了。

394. 字符串解码

代码

char* decodeString(char* s) {char* a = (char*)malloc(sizeof(char) * 10000);int m = -1;int len = strlen(s);for (int i = 0; i < len; i++) {if (s[i] == ']') {int rightzimu = m;int leftzimu = m;while (a[leftzimu] != '[') {leftzimu--;}leftzimu++;int rightshuzi = leftzimu - 2;int leftshuzi = rightshuzi;while (leftshuzi >= 0 && a[leftshuzi] >= '0' && a[leftshuzi] <= '9')leftshuzi--;if (leftshuzi != 0)leftshuzi++;char arr[3000] = {0}; // 记录要重复的元素int arr_num = 0;for (int h = leftzimu; h <= rightzimu; h++) {arr[arr_num++] = a[h];}int num = 0; // 记录重复次数for (int h = leftshuzi; h <= rightshuzi; h++) {num *= 10;num = num + a[h] - '0';}m = leftshuzi - 1;while (num--) {for (int z = 0; z < arr_num; z++)a[++m] = arr[z];}} else {a[++m] = s[i];}}char* ans = (char*)malloc(sizeof(char) * 10000);for (int i = 0; i <= m; i++)ans[i] = a[i];ans[m + 1] = '\0';return ans;
}

题解

本题我的大概思路就是开辟一个栈去存放原字符串，当遇到非 ']' 字符时直接存进去就可以了，如果遇到了 ']' 我们就要开始进行操作了。我们需要找出所有的字母与 '[' 前的数字M，然后我们重复M次存放进栈中就可以了，最后用ans重新读取，返回答案。

具体思路如下：

我们创建了一个a进行字符的存放，设置栈顶m=-1，然后遍历字符串s；
当没有遇到’]‘直接存放，当遇到了’]'我们便要开始进行操作；
我们令rightzimu，leftzimu等于m，此时rightzimu指的就是最后一个字母；
然后我们向前遍历栈a，令leftzimu–，直到遇到’['停止，我们再令leftzimu++，此时我们rightzimu，leftzimu中间夹的就是所有的字母；
然后我们令rightshuzi=leftzimu-2，因为字母与前面的数字中间有个’['；
令leftshuzi=rightshuzi，再次向前遍历，令leftshuzi–，满足leftshuzi >= 0 && a[leftshuzi] >= ‘0’ && a[leftshuzi] <= ‘9’，这里有两个停止条件，一个是遍历到不是数字了，另一个是遍历到栈底停止，所以我们要进行判断：如果leftshuzi != 0，我们才需要leftshuzi++，此时我们leftshuzi和rightshuzi中间夹的就是所有的数字；
然后我们统计出要重复的元素arr和重复次数num，还要将num位置更新到leftshuzi-1的位置重新开始存储；
我们再循环num次，将arr中所有元素再次存放进栈中；
遍历完所有s元素之后我们申请一个ans用来存放答案就可以了。

23. 合并 K 个升序链表

代码

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

题解

本题是 21. 合并两个有序链表这道题的升级版，合并多个有序链表。

所以我们只要会了上面这一道题，那么实现本题就很简单了。

如果是合并两个有序链表，我们用递归很容易就可以实现：

如果list1为空，直接返回list2；
如果list2为空，直接返回list1；
后面我们就需要进行递归了；
如果list1数值大于list2，那么我们就需要保存此时的list2节点并且将list1与list2->next继续进行合并并且用list2->next进行接收；
反之将list2与list1->next继续进行合并并用list1->next进行接收；
返回list1或list2。

下面是具体代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL)return list2;if (list2 == NULL)return list1;if (list1->val > list2->val) {list2->next = mergeTwoLists(list1, list2->next);return list2;} else {list1->next = mergeTwoLists(list1->next, list2);return list1;}
}

会了上面这一道题，本题只需要进行遍历整个lists并用lists[0]与list[i] (i!=0)进行合并就可以了。

下面是本题代码：

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

232. 用栈实现队列

代码

typedef struct MyQueue {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) {int inTop = obj->stackIntop;int outTop = obj->stackOuttop;if (outTop == 0) {while (inTop > 0) {obj->stackOut[outTop++] = obj->stackIn[--inTop];}}int top = obj->stackOut[--(outTop)];while (outTop > 0) {obj->stackIn[inTop++] = obj->stackOut[--outTop];}obj->stackIntop = inTop;obj->stackOuttop = outTop;return top;
}int myQueuePeek(MyQueue* obj) { return obj->stackIn[0]; }bool myQueueEmpty(MyQueue* obj) {if (obj->stackIntop == 0)return true;return false;
}void myQueueFree(MyQueue* obj) {obj->stackIntop = 0;obj->stackOuttop = 0;
}

题解

myQueueCreate 需要我们开辟空间，大小为MyQueue，并且将queue->stackIntop和queue->stackOuttop都初始化为0；
myQueuePush 直接给stackIn中存储数据并且令obj->stackIntop ++；
myQueuePop 需要用两个栈去实现，第一个栈是之前存数据的栈，另一个栈只是一个工具，我们需要把stackIn中的数据存储进stackOut中，这样就刚好将stackIn中栈底的元素放到了stackOut的栈顶位置，直接弹出就可以了，把剩余元素重新存入stackIn中；
myQueuePeek 直接返回栈底元素就可以了；
myQueueEmpty 若stackIntop是0，则证明没有元素，反之则有元素；
myQueueFree 直接将stackIntop和stackOuttop置零就可以了。

61. 旋转链表

代码

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

题解

本题我们需要先求出链表的长度len，用k进行取模（因为移动len次相当于没有移动，反倒会增加运行时间，导致超时），然后我们需要进行循环，每一次循环都找到最后一个节点，将该节点的next指向头结点，然后将最后一个节点的前一个节点pre的next指向NULL，这样就实现了一次旋转，我们循环k次就可以了。

392. 判断子序列

代码

bool isSubsequence(char* s, char* t) {int n = strlen(s), m = strlen(t);int i = 0, j = 0;while (i < n && j < m) {if (s[i] == t[j]) {i++;}j++;}if (i == n)return true;return false;
}

题解

我们用双指针可以很容易地实现本题。

我们令i指向s第一个元素，j指向t第一个元素；
让j向后移动，如果s[i]==t[j]，让i也向后移动；
遍历完t后若果i移动到了最后一个，则证明存在子序列，反之不存在。

以上就是大一上考核题解！

已经到底啦！！