---

Leetcode 147. 对链表进行插入排序

题目描述

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头。

插入排序算法的步骤：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

提示：

• 列表中的节点数在 [1, 5000]范围内
• -5000 <= Node.val <= 5000

C语言题解和思路

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* insertionSortList(struct ListNode* head) {struct ListNode* list = (struct ListNode* )malloc(sizeof(struct ListNode));list->next = head;struct ListNode *i, *q;struct ListNode *min;struct ListNode *last;struct ListNode *tail;for(tail = list; tail->next != NULL && tail != NULL;tail = tail->next){min = tail->next;for(i = tail, q = tail->next; q != NULL; i = q, q = q->next){if(min->val > q->val){min = q;last = i;}}if(min != tail->next){last->next = last->next->next;min->next = tail->next;tail->next = min;}}return list->next;
}

解题思路

遍历链表，将存储最小值链表结点的指针初始化为已遍历结点的下一个结点。

再遍历之后的链表寻找最小值，如果遇上值更小的结点，保存该节点和该节点的前一个结点，如果循环后存储最小值链表结点的指针存储的结点仍然为第一个循环已遍历结点的下一个结点，该节点不便；否则将该节点在后面的链表中删去，并插入到最后一个已遍历结点后。

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

题目描述

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

提示：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

C语言题解和思路

int maxProfit(int* prices, int pricesSize) {if(pricesSize == 0 || pricesSize == 1){return 0;}int f[pricesSize][3];int i;f[0][0] = -prices[0];f[0][1] = 0;f[0][2] = 0;for(i = 1; i < pricesSize; i++){f[i][0] = fmax(f[i - 1][0], f[i - 1][2] - prices[i]);f[i][1] = f[i - 1][0] + prices[i];f[i][2] = fmax(f[i - 1][1], f[i - 1][2]);}return fmax(f[i - 1][1], f[i - 1][2]);
}

解题思路

动态规划 + 状态转换

• f[i][0]：存储第 i 天持有一只股票时，累计的最大资产
• f[i][1]：存储第 i 天处于冷冻期时，累计的最大资产
• f[i][2]：存储第 i 天卖出一只股票时，累计的最大资产

如果天数为 0 时，无法做出任何买入或卖出的交易；或者天数为 1 时，只能买入不能卖出，资产为负数。遇到这两种情况，直接返回 0 。

定义一个二维数组 f ，存储 pricesSize 天的 3 个状态，并先手动声明第一天的状态。

从第二天开始循环，分别更新当天的 3 个状态：

• f[i][0]：第 i 天持有一只股票时，累计的最大资产为，f[i-1][0]，与f[i-1][2]减去今天买下当天股票后的值，取两个值中的最大值。
• f[i][1]：第 i 天处于冷冻期时，累计的最大资产为，前一天持有一只股票时，累计的最大资产加上今天卖掉股票后的资产。
• f[i][2]：第 i 天卖出一只股票时，累计的最大资产为，前一天处于冷冻期时累计的最大资产与前一天卖出一只股票时累计的最大资产两个值的最大值。

返回最后一天处于冷冻期时和处于卖出一只股票时，两个值中的最大值。

Leetcode 187. 重复的DNA序列

题目描述

DNA序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。

例如，“ACGAATTCCG” 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”,“CCCCCAAAAA”]

示例 2：

输入：s = “AAAAAAAAAAAAA”
输出：[“AAAAAAAAAA”]

提示：

• 0 <= s.length <= 105
• s[i]==‘A’、‘C’、‘G’ or ‘T’

C语言题解和思路

/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct HASH{char key[11];int val;UT_hash_handle hh;}HASH;
void getstr(char *str, char *s, int left, int right)
{for (int i = left; i < right; i++) {str[i - left] = s[i];}str[10] = '\0';
}
char** findRepeatedDnaSequences(char* s, int* returnSize) {HASH *table = NULL;int i, n = strlen(s);char *s1 = (char *)malloc(sizeof(char) * 11);char **ret = (char **)malloc(sizeof(char *) * n);*returnSize = 0;int left = 0, right = 10;if(n <= 10){return NULL;}while(right <= n){getstr(s1, s, left, right);HASH *tmp = NULL;HASH_FIND_STR(table, s1, tmp);if(tmp == NULL){tmp = malloc(sizeof(HASH));memcpy(tmp->key, s1, 10*sizeof(char));tmp->key[10] = '\0';tmp->val = 1;HASH_ADD_STR(table, key, tmp);}else{(tmp->val)++;}left++;right++;}HASH *p;for(p = table; p != NULL; p = p->hh.next) {if(p->val > 1){ret[*returnSize] = p->key;(*returnSize)++;}}return ret;
}

解题思路

哈希表：uthash函数

判断字符串 s 的长度，如果小于或等于10，直接返回NULL。

定义变量 left 和 right 记录子字符串的左右下标，遍历字符串，将子字符串通过自定义函数getstr转移到另一个字符指针中。将该字符指针放进哈希表中查找，如果哈希表中没有该值，将该字符串添加进哈希表中， val 值初始化为1；如果哈希表中存在该值，则 val 值加1。

循环结束后，遍历哈希表，将 va l值大于1的字符串添加进二维数组 ret ，返回数组 ret 。

Leetcode 2517. 礼盒的最大甜蜜度

题目描述

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类不同糖果打包成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。

返回礼盒的最大甜蜜度。

示例 1：

输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。

示例 2：

输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。

示例 3：

输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

提示：

• 2 <= k <= price.length <= 105
• 1 <= price[i] <= 109

C语言题解和思路

int check(int* price, int priceSize,int k, int tastiness) {int prev = price[0];int cnt = 1;for (int i = 1; i < priceSize; i++) {if (price[i] - prev >= tastiness) {cnt++;prev = price[i];}}return cnt >= k ? 1 : 0;
}
int cmp(int *a, int *b)
{return *(int *)a - *(int *)b;
}
int maximumTastiness(int* price, int priceSize, int k) {qsort(price, priceSize, sizeof(int), cmp);int left = 0, right = price[priceSize - 1] - price[0];while(left < right){int mid = (left + right + 1) / 2;if(check(price, priceSize, k, mid) == 1){left = mid;}else{right = mid - 1;}}return left;
}

解题思路

贪心算法 + 二分查找

首先将数组进行升序排序，定义并初始化 left 为 0 ，作为商品的最小差价， right 为商品的最大差价，也就是最贵的商品减去最便宜的商品。

当最小差价小于最大差价时，进行循环，取最大差价和最小差价的平均数，设置一个函数 check 来检查是否存在足够的商品差价大于中间值，如果存在，将中间站赋给最小差价，否则将中间值减一赋给最大差价。

check函数：将变量prev初始化为数组第一个数，将用于计算满足条件的数量的变量cnt初始化为1。从第2个数开始遍历数组，碰上与prev的差大于或等于 tastiness （也就是传进来的中间值）的数，cnt加1，并将该数赋给 prev ，用来寻找下一个数。最后循环结束，如果 cnt 的 值大于等于 k 返回 1 ，否则返回 0 。

最后当最小差价和最大差价相等时，返回这个值。

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

题目描述

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1：

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2：

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶： 你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

C语言题解和思路

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int *ans = (int *)malloc(sizeof(int) * numsSize);*returnSize = numsSize;int i, s = 1, flag = 0;for(i = 0; i < numsSize; i++){if(nums[i] != 0){s *= nums[i];}else{flag++;}}for(i = 0; i < numsSize; i++){if(flag == 0){ans[i] = s / nums[i];}else if(flag == 1){if(nums[i] == 0){ans[i] = s;}else{ans[i] = 0;}}else{ans[i] = 0;}}return ans;
}

解题思路

遍历数组，将数组中不为0的数相乘，如果碰上0， flag 加一。

创建一个数组 ans 存储需要返回的值。

再次遍历数组，如果 flag 等于0，将总乘积除以数组 nums 该下标的值并赋予数组 ans 。如果 flag 等于1，说明数组中有一个元素是0，除了这个值为0的下标的乘积为总乘积外，其他位置的总乘积都为0。如果 flag 大于1，说明数组中有两个及以上的值为0，所以数组所有位置的乘积都为0。

返回数组 ans 。

Leetcode 394. 字符串解码

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = “3[a]2[bc]”
输出：“aaabcbc”

示例 2：

输入：s = “3[a2[c]]”
输出：“accaccacc”

示例 3：

输入：s = “2[abc]3[cd]ef”
输出：“abcabccdcdcdef”

示例 4：

输入：s = “abc3[cd]xyz”
输出：“abccdcdcdxyz”

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 ‘[]’ 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300]

C语言题解和思路

typedef struct Stack{int data[30];;int top;
} Stack;
void push(Stack *obj, int k) 
{ obj->data[(obj->top)++] = k; 
}
int pop(Stack *s) 
{ return s->data[--(s->top)]; 
}
int strToInt(char *s)
{char *val = (char*)malloc(sizeof(char) * 4);int result = 0;int i ,tmp;for(i = 0; s[i] >='0' && s[i] <= '9'; i++){val[i] = s[i];}val[i] = '\0';for(i = strlen(val) - 1, tmp = 1; i >= 0; --i, tmp *= 10){result += ((val[i] - '0') * tmp);}return result;
}
char* decodeString(char *s)
{Stack map; map.top = 0;Stack p;p.top = 0;char *result = (char*)malloc(sizeof(char) * 2000);char *rear = result;for(int i = 0; s[i] != '\0'; ) {if(s[i] >= '0' && s[i] <= '9') {push(&map, strToInt(&s[i]));while(s[i] >= '0' && s[i] <= '9'){i++;}}else if(s[i] == '['){push(&p, rear - result);i++;}else if(s[i] == ']'){char *q = result + pop(&p);int count = (rear - q) * (pop(&map) - 1);while(count > 0){*(rear++) = *(q++);count--;}i++;}else{*(rear++) = s[i++];}}*rear = '\0';return result;
}

解题思路

栈和队列

首先定义了一个结构体 Stack，其中包含一个数组 data 和一个变量 top，用于表示栈的数据结构。

定义一个 push 函数用于将元素推入栈中。

定义一个 pop 函数用于从栈中弹出栈顶的元素。

定义一个 strToInt 函数用于将字符串转换为整数。

首先，创建一个字符数组 result ，用于存放解码后的字符串，再创建一个指向字符数组 result 的指针 rear，用于标记每次解码后字符串的末尾。

通过循环遍历输入字符串 s，对每个字符进行处理：

• 如果是数字，则调用 strToInt 函数将连续的数字字符转换为对应的整数，并将其压入 map 栈中。
• 如果是左括号，则将当前 rear 与 result 的差值（即当前解码字符串的长度）压入栈 p 中。
• 如果是右括号，则将 p 栈顶元素指向的位置作为起点，复制相应数量的字符到 rear 指向的位置，直到复制完成。复制完成后，将相应数量的重复次数从 map 栈中弹出，并将结果添加到字符串 result 的末尾。
• 如果是其他字符，则直接将其添加到字符串 result 的末尾。

循环结束后，在字符串 result 末尾添加上 ‘\0’ 。

返回 result 。

Leetcode 23. 合并 K 个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

C语言题解和思路

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));head->next = NULL;struct ListNode *move = head;int i;for(i = 0; i < listsSize; i++){while(lists[i] != NULL){move->next = lists[i];move = move->next;lists[i] = lists[i]->next;}}struct ListNode *x, *y;for(x = head->next; x != NULL; x = x->next){for(y = head->next; y->next != NULL; y = y->next){if(y->val > y->next->val){int tmp;tmp = y->val;y->val = y->next->val;y->next->val = tmp;}}}return head->next;
}

解题思路

先将所有链表结点链接在一个新创建的链表上，然后通过交换数据的方式，给链表重新排序，最后返回链表的第一个有效结点，也就是头节点的下一个结点。

Leetcode 232. 用栈实现队列

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

C语言题解和思路

typedef struct {int head, tail;int stackIn[100];
} MyQueue;MyQueue* myQueueCreate() {MyQueue *head = (MyQueue *)malloc(sizeof(MyQueue));head->tail = 0;head->head = 0;return head;
}void myQueuePush(MyQueue* obj, int x) {obj->stackIn[(obj->tail)++] = x;
}int myQueuePop(MyQueue* obj) {int t = obj->stackIn[obj->head++];return t;
}int myQueuePeek(MyQueue* obj) {return obj->stackIn[obj->head];
}bool myQueueEmpty(MyQueue* obj) {return obj->head == obj->tail;
}void myQueueFree(MyQueue* obj) {free(obj);
}
/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

解题思路

定义队列的结构体，数组 stackIn 用于存放，变量 head 和 tail 分别存放队列头和尾的坐标。

将元素 x 推到队列的末尾时：将元素存入下标为 tail 的位置， tail 加一。

从队列的开头移除并返回元素：返回数组下标为 head 的值， head 加一。

返回队列开头的元素：返回数组下标为 head 的值， head 不变。

判断队列是否为空：判断 head 是否等于 tail 。

Leetcode 61. 旋转链表

题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9

C语言题解和思路

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* rotateRight(struct ListNode* head, int k) {if(k == 0 || head == NULL || head->next == NULL){return head;}int n = 1;struct ListNode* move = head;  while(move->next != NULL){move = move->next;n++;}int c =n - k % n;if(c == n){return head;}move->next = head;while(c--){move = move->next;}struct ListNode* ret = move->next;move->next = NULL;return ret;
}

解题思路

当 k 等于 0 时，或链表只有一个结点或没有结点时，直接返回链表头节点。

遍历链表至最后一个有效结点停下，并记录链表结点的个数。

如果链表结点个数是 k 的倍数，直接返回头节点。

否则，将链表连接成环，链表从头节点往后移动 n-k%n 个结点，记录后一个结点并让该结点与后一个结点断开。

最后返回记录下的结点。

Leetcode 392. 判断子序列

题目描述

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = “abc”, t = “ahbgdc”
输出：true

示例 2：

输入：s = “axc”, t = “ahbgdc”
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

C语言题解和思路

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

解题思路

首先求出两个字符串的长度，通过变量 i 遍历字符串 t ，通过变量 k 变量字符串 s 。

遍历字符串 t ，如果 i 位置上的字符与字符串 s 中 k 位置上的字符相等， k 加一。

如果遍历结束后， k 等于字符串 s 的长度，说明字符串 s 是字符串 t 的子序列，返回 true ，否则返回 false 。