力扣hot100刷题——11~20

11.滑动窗口最大值

题目描述

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

思路：滑动窗口+单调队列

1. 单调队列：
   • 使用一个双端队列（Deque）来存储数组的索引。
   • 队列中的元素按从大到小的顺序排列，队头元素是当前窗口的最大值。
2. 滑动窗口：
   • 遍历数组，维护一个大小为 k 的滑动窗口。
   • 在遍历过程中，动态更新队列，确保队列中的元素始终在窗口内，并且按从大到小的顺序排列。
3. 队列更新规则：
   • 移除不在窗口内的元素：如果队头元素已经不在当前窗口内，则将其从队列中移除。
   • 移除小于当前元素的元素：从队尾开始，移除所有小于当前元素的元素，确保队列的单调性。
   • 将当前元素加入队列：将当前元素的索引加入队尾。
4. 记录结果：
   • 当窗口形成时（i >= k - 1），将队头元素（当前窗口的最大值）加入结果数组。

我认为本题真的很难，第一次不懂的话可以过段时间再看。

code

#include <stdio.h>
#include <stdlib.h>int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {if (nums == NULL || numsSize == 0 || k == 0) {*returnSize = 0;return NULL;}*returnSize = numsSize - k + 1; // 计算结果数组的大小int* result = (int*)malloc(sizeof(int) * (*returnSize)); // 分配结果数组int queue[numsSize]; // 使用数组模拟双端队列int head = 0, tail = -1; // 队列的头和尾for (int i = 0; i < numsSize; i++) {// 移除队列中不在当前窗口内的元素if (head <= tail && queue[head] < i - k + 1) {head++;}// 移除队列中所有小于当前元素的元素while (head <= tail && nums[queue[tail]] < nums[i]) {tail--;}// 将当前元素的索引加入队列queue[++tail] = i;// 如果窗口已经形成，将队列头部的元素加入结果数组if (i >= k - 1) {result[i - k + 1] = nums[queue[head]];}}return result; // 返回结果数组
}

12.最小覆盖子串

题目描述

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路：双指针/滑动窗口+哈希

题目中的4个提示已经给出了本题思路：

• Use two pointers to create a window of letters in s, which would have all the characters from t.
  使用两个指针在 s 中创建一个字母窗口，该窗口将包含 t 中的所有字符。
• Expand the right pointer until all the characters of t are covered.
  展开右指针，直到覆盖 t 的所有字符。
• Once all the characters are covered, move the left pointer and ensure that all the characters are still covered to minimize the subarray size.
  覆盖所有字符后，移动左指针并确保仍覆盖所有字符，以最小化子数组大小。
• Continue expanding the right and left pointers until you reach the end of s.
  继续展开左右指针，直到到达 s 的末尾。

具体代码思路：

1. 初始化哈希表：
   • hasht[128]：记录 t 中每个字符的出现次数。
   • hashs[128]：记录当前窗口内字符的出现次数。
2. 滑动窗口双指针：
   • left 和 right 指针分别表示窗口的左右边界。
   • right 向右扩展窗口，直到窗口包含 t 的所有字符。
   • 当窗口有效时，left 向右收缩以寻找更小的窗口。
3. 计数器 count 的作用：
   • 统计当前窗口中恰好满足 t 字符需求的字符数量。
   • 当 count == strlen(t) 时，说明窗口已覆盖 t 的所有字符。
4. 更新最小窗口：
   • 每次窗口有效时，记录窗口的起始位置和长度。
   • 最终返回最小窗口对应的子串。

code Ⅰ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>char* minWindow(char* s, char* t) {int m = strlen(s), n = strlen(t); // 获取 s 和 t 的长度char* ans = malloc(sizeof(char) * (m + 1)); // 分配结果数组if (m < n) return ""; // 如果 s 的长度小于 t，直接返回空字符串int hashs[130] = {0}; // 记录 s 中当前窗口的字符频率int hasht[130] = {0}; // 记录 t 中字符的频率// 统计 t 中字符的频率for (int i = 0; i < n; i++) {hasht[t[i]]++;}int l = 0, r = 0; // 滑动窗口的左右指针int indexl = 0, indexr = 0; // 最小窗口的左右索引int minlen = m + 1; // 最小窗口长度// 初始化窗口while (r < n) {hashs[s[r]]++; // 更新 s 中当前窗口的字符频率r++; // 右指针右移}// 滑动窗口while (r < m) {bool flag = true;// 检查当前窗口是否满足 t 中字符的频率要求for (int i = 0; i <= 128; i++) {if (hashs[i] < hasht[i]) {flag = false; // 如果不满足，设置 flag 为 falsebreak;}}if (flag) {// 如果满足条件，更新最小窗口if (r - l < minlen) {minlen = r - l;indexl = l;indexr = r;}// 移动左指针，缩小窗口hashs[s[l]]--;l++;} else {// 如果不满足条件，移动右指针，扩展窗口hashs[s[r]]++;r++;}}// 最后检查一次窗口bool flag = true;while (flag) {for (int i = 0; i <= 128; i++) {if (hashs[i] < hasht[i]) {flag = false; // 如果不满足，设置 flag 为 falsebreak;}}if (!flag) break; // 如果不满足条件，退出循环// 如果满足条件，更新最小窗口if (r - l < minlen) {minlen = r - l;indexl = l;indexr = m;}// 移动左指针，缩小窗口hashs[s[l]]--;l++;}// 如果最小窗口长度未更新，说明没有符合条件的子串if (minlen == m + 1) return "";// 将结果复制到 ans 中for (int i = indexl; i < indexr; i++) {ans[i - indexl] = s[i];}ans[minlen] = '\0'; // 添加字符串结束符return ans; // 返回结果
}

code Ⅱ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>char* minWindow(char* s, char* t) {int m = strlen(s), n = strlen(t);if (m == 0 || n == 0 || m < n) return ""; // 如果 s 或 t 为空，或者 s 的长度小于 t，直接返回空字符串char* ans = malloc(sizeof(char) * (m + 1)); // 分配结果数组int hashs[128] = {0}; // 记录 s 中当前窗口的字符频率int hasht[128] = {0}; // 记录 t 中字符的频率// 统计 t 中字符的频率for (int i = 0; i < n; i++) {hasht[t[i]]++;}int l = 0, r = 0; // 滑动窗口的左右指针int minlen = m + 1; // 最小窗口长度int indexl = 0, indexr = 0; // 最小窗口的左右索引int count = 0; // 记录当前窗口中满足 t 中字符频率的字符数量while (r < m) {// 如果当前字符在 t 中出现过，则更新 hashs 和 countif (hasht[s[r]] > 0) {hashs[s[r]]++;if (hashs[s[r]] <= hasht[s[r]]) {count++;}}r++;// 如果当前窗口满足 t 中字符的频率要求while (count == n) {// 更新最小窗口if (r - l < minlen) {minlen = r - l;indexl = l;indexr = r;}// 移动左指针，缩小窗口if (hasht[s[l]] > 0) {hashs[s[l]]--;if (hashs[s[l]] < hasht[s[l]]) {count--;}}l++;}}// 如果最小窗口长度未更新，说明没有符合条件的子串if (minlen == m + 1) return "";// 将结果复制到 ans 中strncpy(ans, s + indexl, minlen);ans[minlen] = '\0'; // 添加字符串结束符return ans; // 返回结果
}

13.最大子数组和

题目描述

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

思路：dp/贪心

1. 定义状态：

   • 定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。

2. 状态转移方程：

   • 如果 dp[i-1] 是正数，则将其加入当前元素 nums[i]，形成更大的子数组和。

   • 如果 dp[i-1] 是负数，则以当前元素 nums[i] 作为新的子数组起点。

   • 状态转移方程为：

     dp[i] = max(nums[i], dp[i-1] + nums[i])

3. 初始化：

   • dp[0] = nums[0]，因为以第一个元素结尾的最大子数组和就是它本身。

4. 遍历数组：

   • 从第二个元素开始，依次计算 dp[i]，并更新全局最大值 ans。

5. 返回结果：

   • 返回全局最大值 ans。

code

#include <stdio.h>
#include <stdlib.h>int maxSubArray(int* nums, int numsSize) {if (nums == NULL || numsSize == 0) return 0; // 如果数组为空，直接返回 0int dp[numsSize]; // 定义 dp 数组，dp[i] 表示以 nums[i] 结尾的最大子数组和dp[0] = nums[0]; // 初始化 dp[0]int ans = dp[0]; // 初始化全局最大值for (int i = 1; i < numsSize; i++) {// 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])dp[i] = fmax(nums[i], dp[i - 1] + nums[i]);// 更新全局最大值ans = fmax(ans, dp[i]);}return ans; // 返回全局最大值
}

14.合并区间

题目描述

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路：贪心

本题比较简单，直接拷贝之前的文章

代码随想录——贪心

• 按区间的起始位置排序。
• 遍历区间，如果当前区间与前一个区间重叠，则合并它们；否则，将前一个区间加入结果列表。

个人感觉比较简单~~

code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>// 比较函数，用于按区间的起始位置从小到大排序
int cmp(const void* a, const void* b) {int* intervala = *(int**)a;int* intervalb = *(int**)b;// 按起始位置从小到大排序if (intervala[0] - intervalb[0] < 0) return -1;return 1;
}int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {// 按区间的起始位置排序qsort(intervals, intervalsSize, sizeof(int*), cmp);// 分配结果数组的内存int** res = malloc(sizeof(int*) * intervalsSize);// 初始化返回的区间数量为 0*returnSize = 0;// 初始化当前区间的起始和结束位置int start = intervals[0][0];int end = intervals[0][1];// 遍历所有区间for (int i = 1; i < intervalsSize; i++) {// 如果当前区间与前一个区间重叠if (intervals[i][0] <= end) {// 合并区间，更新结束位置end = fmax(end, intervals[i][1]);} else {// 如果不重叠，将前一个区间加入结果列表res[*returnSize] = malloc(sizeof(int) * 2);res[*returnSize][0] = start;res[*returnSize][1] = end;(*returnSize)++;// 更新当前区间的起始和结束位置start = intervals[i][0];end = intervals[i][1];}}// 将最后一个区间加入结果列表res[*returnSize] = malloc(sizeof(int) * 2);res[*returnSize][0] = start;res[*returnSize][1] = end;(*returnSize)++;// 分配列大小数组的内存*returnColumnSizes = malloc(sizeof(int) * (*returnSize));// 设置每个区间的列大小为 2for (int i = 0; i < *returnSize; i++) {(*returnColumnSizes)[i] = 2;}// 返回结果数组return res;
}

15.轮转数组

题目描述

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

思路：反转法

1. 反转整个数组。
2. 反转前 k 个元素。
3. 反转剩余 n - k 个元素。

证明：

1. 初始数组：

   • 数组 nums 可以表示为：
     $$nums=[a_0,a_1,...,a_{n-k-1},a_{n-k},a_{n-k+1},...,a_{n-1}]$$

2. 第一次反转（反转整个数组）：

   • 反转后，数组变为：
     $$nums=[a_{n-1},...,a_{n-k+1},a_{n-k},a_{n-k-1},...,a_0]$$

3. 第二次反转（反转前 k 个元素）：

   • 反转前 k 个元素后，数组变为：
     $$nums=[a_{n-k},...,a_{n-1},a_{n-k-1},...,a_0]$$

4. 第三次反转（反转剩下的 n - k 个元素）：

   • 反转剩下的 n - k 个元素后，数组变为：
     $$nums=[a_{n-k},...,a_{n-1},a_0,...,a_{n-k-1}]$$

网上有很多种证明，我觉得这样是最直观的

code

#include <stdio.h>// 反转数组的辅助函数
void reverse(int* nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}
}void rotate(int* nums, int numsSize, int k) {k = k % numsSize; // 处理 k 大于数组长度的情况if (k == 0) return; // 如果 k 为 0，直接返回// 反转整个数组reverse(nums, 0, numsSize - 1);// 反转前 k 个元素reverse(nums, 0, k - 1);// 反转剩下的 n - k 个元素reverse(nums, k, numsSize - 1);
}

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

题目描述

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]

思路：前缀积+后缀积

1. 前缀积：
   • 从左到右遍历数组，计算每个位置左侧所有元素的乘积。
2. 后缀积：
   • 从右到左遍历数组，计算每个位置右侧所有元素的乘积。
3. 结果计算：
   • 对于每个位置 i，结果 ans[i] 等于前缀积 left[i] 乘以后缀积 right[i]。

code

#include <stdio.h>
#include <stdlib.h>int* productExceptSelf(int* nums, int numsSize, int* returnSize) {// 分配结果数组的内存int* ans = malloc(sizeof(int) * numsSize);*returnSize = numsSize; // 设置返回数组的大小// 定义前缀积数组 left 和后缀积数组 rightint left[numsSize];  // 存储每个位置左侧所有元素的乘积int right[numsSize]; // 存储每个位置右侧所有元素的乘积// 计算前缀积left[0] = 1; // 第一个元素左侧没有元素，前缀积为 1for (int i = 1; i < numsSize; i++) {left[i] = left[i - 1] * nums[i - 1]; // 前缀积 = 前一个前缀积 * 前一个元素}// 计算后缀积right[numsSize - 1] = 1; // 最后一个元素右侧没有元素，后缀积为 1for (int i = numsSize - 2; i >= 0; i--) {right[i] = right[i + 1] * nums[i + 1]; // 后缀积 = 后一个后缀积 * 后一个元素}// 计算结果数组for (int i = 0; i < numsSize; i++) {ans[i] = left[i] * right[i]; // 结果 = 前缀积 * 后缀积}return ans; // 返回结果数组
}

17.缺失的第一个正数

题目描述

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

思路：哈希

本题如果抛弃时间和空间的限制是蛮简单的。

有两种思路：

1.开辟额外空间建立哈希表，记录1~numSize的数是否出现。空间复杂度O(N)

2.先对原数组排序，再寻找没有出现的最小正整整。时间复杂度O(NlogN)。

虽然上面两种方法都可以解决，但是不能满足题目的要求。这里的思路是：原地哈希。

具体步骤：

1. 原地哈希：
   • 将数组中的每个正整数放到它应该在的位置
   • 如果当前数在 1 到 numsSize之间，并且它不在正确的位置上，将它交换到正确的位置。
2. 查找缺失的正整数：
   • 最后遍历数组，找到第一个正数的位置 i，i + 1 就是缺失的最小正整数。
   • 如果所有位置都是负数，则缺失的最小正整数是 n + 1。

code

#include <stdio.h>// 交换两个整数的值
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}int firstMissingPositive(int* nums, int numsSize) {// 第一步：将数组中的每个正整数放到它应该在的位置for (int i = 0; i < numsSize; i++) {// 如果当前数在 1 到 numsSize 之间，并且它不在正确的位置上while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {// 将它交换到正确的位置swap(&nums[i], &nums[nums[i] - 1]);}}// 第二步：遍历数组，找到第一个不满足 nums[i] == i + 1 的位置for (int i = 0; i < numsSize; i++) {if (nums[i] != i + 1) {return i + 1;}}// 如果所有位置都满足条件，返回 numsSize + 1return numsSize + 1;
}

18.矩阵置零

题目描述

73. 矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法**。**

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

思路：哈希

1.问题分析：

• 我们需要将矩阵中所有 0 所在的行和列都置为 0。
• 直接修改矩阵会导致后续的 0 被误判，因此需要先记录哪些行和列需要置零。

2.核心思想：

• 使用两个辅助数组 row 和 col，分别记录哪些行和列需要置零。
• 遍历矩阵，如果发现 matrix[i][j] == 0，则标记 row[i] 和 col[j] 为 true。
• 再次遍历矩阵，根据 row 和 col 的标记，将对应的行和列置零。

3.优化：

• 可以使用矩阵的第一行和第一列来替代辅助数组，从而将空间复杂度优化为 O(1)。

code

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {// 定义两个辅助数组，用于记录哪些行和列需要置零bool col[200]; // 记录列是否需要置零bool row[200]; // 记录行是否需要置零memset(col, false, sizeof(col)); // 初始化 col 数组为 falsememset(row, false, sizeof(row)); // 初始化 row 数组为 false// 遍历矩阵，标记需要置零的行和列for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < matrixColSize[i]; j++) {if (matrix[i][j] == 0) { // 如果当前元素为 0if (!col[j]) col[j] = true; // 标记列 j 需要置零if (!row[i]) row[i] = true; // 标记行 i 需要置零}}}// 遍历矩阵，将标记的行置零for (int i = 0; i < matrixSize; i++) {if (row[i]) { // 如果行 i 需要置零for (int j = 0; j < matrixColSize[i]; j++) {matrix[i][j] = 0; // 将行 i 的所有元素置零}}}// 遍历矩阵，将标记的列置零for (int j = 0; j < matrixColSize[0]; j++) {if (col[j]) { // 如果列 j 需要置零for (int i = 0; i < matrixSize; i++) {matrix[i][j] = 0; // 将列 j 的所有元素置零}}}
}

code(优化)

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {bool firstRowHasZero = false; // 记录第一行是否需要置零bool firstColHasZero = false; // 记录第一列是否需要置零// 检查第一行是否有 0for (int j = 0; j < matrixColSize[0]; j++) {if (matrix[0][j] == 0) {firstRowHasZero = true;break;}}// 检查第一列是否有 0for (int i = 0; i < matrixSize; i++) {if (matrix[i][0] == 0) {firstColHasZero = true;break;}}// 遍历矩阵，标记需要置零的行和列for (int i = 1; i < matrixSize; i++) {for (int j = 1; j < matrixColSize[i]; j++) {if (matrix[i][j] == 0) {matrix[i][0] = 0; // 标记第 i 行需要置零matrix[0][j] = 0; // 标记第 j 列需要置零}}}// 根据标记置零for (int i = 1; i < matrixSize; i++) {for (int j = 1; j < matrixColSize[i]; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}}// 处理第一行if (firstRowHasZero) {for (int j = 0; j < matrixColSize[0]; j++) {matrix[0][j] = 0;}}// 处理第一列if (firstColHasZero) {for (int i = 0; i < matrixSize; i++) {matrix[i][0] = 0;}}
}

19.螺旋矩阵

题目描述

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

思路：模拟/螺旋矩阵

1. 边界初始化：

   • top 和 bottom 分别表示当前遍历的上下边界。
   • left 和 right 分别表示当前遍历的左右边界。

2. 螺旋遍历核心逻辑：

   • 从左到右遍历上边界：将上边界的元素加入结果数组，然后上边界下移。
   • 从上到下遍历右边界：将右边界的元素加入结果数组，然后右边界左移。
   • 从右到左遍历下边界：将下边界的元素加入结果数组，然后下边界上移。
   • 从下到上遍历左边界：将左边界的元素加入结果数组，然后左边界右移。

   注：每次遍历完一个边界后修改边界值

3. 终止条件：

   • 当上边界超过下边界或左边界超过右边界时，遍历结束。

4. 边界条件处理：

   • 如果矩阵为空，直接返回 NULL 并设置 returnSize 为 0。

code

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {if (matrixSize == 0 || matrixColSize[0] == 0) {*returnSize = 0;return NULL;}int m = matrixSize;          // 矩阵的行数int n = matrixColSize[0];    // 矩阵的列数int* ans = malloc(sizeof(int) * m * n); // 结果数组*returnSize = 0;             // 初始化返回数组的大小int top = 0, bottom = m - 1; // 定义上下边界int left = 0, right = n - 1; // 定义左右边界while (top <= bottom && left <= right) {// 从左到右遍历上边界for (int j = left; j <= right; j++) {ans[(*returnSize)++] = matrix[top][j];}top++; // 上边界下移// 从上到下遍历右边界for (int i = top; i <= bottom; i++) {ans[(*returnSize)++] = matrix[i][right];}right--; // 右边界左移// 如果上边界超过下边界，说明已经遍历完if (top > bottom) break;// 从右到左遍历下边界for (int j = right; j >= left; j--) {ans[(*returnSize)++] = matrix[bottom][j];}bottom--; // 下边界上移// 如果左边界超过右边界，说明已经遍历完if (left > right) break;// 从下到上遍历左边界for (int i = bottom; i >= top; i--) {ans[(*returnSize)++] = matrix[i][left];}left++; // 左边界右移}return ans;
}

20.旋转图像

题目描述

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

思路一：水平翻转+转置

证明略。。。(后面再补)

code

//主对角线翻转+水平翻转
void swap(int *a,int *b){int temp=*a;*a=*b;*b=temp;
}
void rotate(int** matrix, int matrixSize, int* matrixColSize) {//水平翻转for(int i=0;i<matrixSize/2;i++){for(int j=0;j<matrixSize;j++){swap(&matrix[i][j],&matrix[matrixSize-1-i][j]);}}//主对角线翻转for(int i=0;i<matrixSize;i++){for(int j=i+1;j<matrixSize;j++){swap(&matrix[i][j],&matrix[j][i]);}}}