文章目录
- 11.滑动窗口最大值
- 题目描述
- 思路：滑动窗口+单调队列
- code
- 12.最小覆盖子串
- 题目描述
- 思路：双指针/滑动窗口+哈希
- code Ⅰ
- code Ⅱ
- 13.最大子数组和
- 题目描述
- 思路：dp/贪心
- code
- 14.合并区间
- 题目描述
- 思路：贪心
- code
- 15.轮转数组
- 题目描述
- 思路：反转法
- code
- 16.除自身以外数组的乘积
- 题目描述
- 思路：前缀积+后缀积
- code
- 17.缺失的第一个正数
- 题目描述
- 思路：哈希
- code
- 18.矩阵置零
- 题目描述
- 思路：哈希
- code
- code(优化)
- 19.螺旋矩阵
- 题目描述
- 思路：模拟/螺旋矩阵
- code
- 20.旋转图像
- 题目描述
- 思路一：水平翻转+转置
- code
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]
思路：滑动窗口+单调队列
- 单调队列：
- 使用一个双端队列（Deque）来存储数组的索引。
- 队列中的元素按从大到小的顺序排列，队头元素是当前窗口的最大值。
- 滑动窗口：
- 遍历数组，维护一个大小为
k的滑动窗口。 - 在遍历过程中，动态更新队列，确保队列中的元素始终在窗口内，并且按从大到小的顺序排列。
- 遍历数组，维护一个大小为
- 队列更新规则：
- 移除不在窗口内的元素：如果队头元素已经不在当前窗口内，则将其从队列中移除。
- 移除小于当前元素的元素：从队尾开始，移除所有小于当前元素的元素，确保队列的单调性。
- 将当前元素加入队列：将当前元素的索引加入队尾。
- 记录结果：
- 当窗口形成时（
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 的末尾。
具体代码思路：
- 初始化哈希表：
hasht[128]：记录t中每个字符的出现次数。hashs[128]：记录当前窗口内字符的出现次数。
- 滑动窗口双指针：
left和right指针分别表示窗口的左右边界。right向右扩展窗口，直到窗口包含t的所有字符。- 当窗口有效时，
left向右收缩以寻找更小的窗口。
- 计数器
count的作用：- 统计当前窗口中恰好满足
t字符需求的字符数量。 - 当
count == strlen(t)时，说明窗口已覆盖t的所有字符。
- 统计当前窗口中恰好满足
- 更新最小窗口：
- 每次窗口有效时，记录窗口的起始位置和长度。
- 最终返回最小窗口对应的子串。
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/贪心
-
定义状态：
- 定义
dp[i]表示以nums[i]结尾的最大子数组和。
- 定义
-
状态转移方程：
-
如果
dp[i-1]是正数，则将其加入当前元素nums[i]，形成更大的子数组和。 -
如果
dp[i-1]是负数，则以当前元素nums[i]作为新的子数组起点。 -
状态转移方程为：
dp[i] = max(nums[i], dp[i-1] + nums[i])
-
-
初始化：
dp[0] = nums[0]，因为以第一个元素结尾的最大子数组和就是它本身。
-
遍历数组：
- 从第二个元素开始，依次计算
dp[i]，并更新全局最大值ans。
- 从第二个元素开始，依次计算
-
返回结果：
- 返回全局最大值
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]
思路：反转法
- 反转整个数组。
- 反转前
k个元素。 - 反转剩余
n - k个元素。
证明：
-
初始数组：
- 数组
nums可以表示为：
n u m s = [ a 0 , a 1 , . . . , a n − k − 1 , a n − k , a n − k + 1 , . . . , a n − 1 ] nums = [a_{0}, a_{1}, ..., a_{n-k-1}, a_{n-k}, a_{n-k+1}, ..., a_{n-1}] nums=[a0,a1,...,an−k−1,an−k,an−k+1,...,an−1]
- 数组
-
第一次反转（反转整个数组）：
- 反转后，数组变为：
n u m s = [ a n − 1 , . . . , a n − k + 1 , a n − k , a n − k − 1 , . . . , a 0 ] nums = [a_{n-1}, ..., a_{n-k+1}, a_{n-k}, a_{n-k-1}, ..., a_{0}] nums=[an−1,...,an−k+1,an−k,an−k−1,...,a0]
- 反转后，数组变为：
-
第二次反转（反转前
k个元素）：- 反转前
k个元素后，数组变为：
n u m s = [ a n − k , . . . , a n − 1 , a n − k − 1 , . . . , a 0 ] nums = [a_{n-k}, ..., a_{n-1}, a_{n-k-1}, ..., a_{0}] nums=[an−k,...,an−1,an−k−1,...,a0]
- 反转前
-
第三次反转（反转剩下的
n - k个元素）：- 反转剩下的
n - k个元素后，数组变为：
n u m s = [ a n − k , . . . , a n − 1 , a 0 , . . . , a n − k − 1 ] nums = [a_{n-k}, ..., a_{n-1}, a_{0}, ..., a_{n-k-1}] nums=[an−k,...,an−1,a0,...,an−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]
思路：前缀积+后缀积
- 前缀积：
- 从左到右遍历数组，计算每个位置左侧所有元素的乘积。
- 后缀积：
- 从右到左遍历数组，计算每个位置右侧所有元素的乘积。
- 结果计算：
- 对于每个位置
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到numsSize之间，并且它不在正确的位置上，将它交换到正确的位置。
- 查找缺失的正整数：
- 最后遍历数组，找到第一个正数的位置
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]
思路：模拟/螺旋矩阵
-
边界初始化：
top和bottom分别表示当前遍历的上下边界。left和right分别表示当前遍历的左右边界。
-
螺旋遍历核心逻辑：
- 从左到右遍历上边界：将上边界的元素加入结果数组，然后上边界下移。
- 从上到下遍历右边界：将右边界的元素加入结果数组，然后右边界左移。
- 从右到左遍历下边界：将下边界的元素加入结果数组，然后下边界上移。
- 从下到上遍历左边界：将左边界的元素加入结果数组，然后左边界右移。
注：每次遍历完一个边界后修改边界值
-
终止条件：
- 当上边界超过下边界或左边界超过右边界时，遍历结束。
-
边界条件处理：
- 如果矩阵为空，直接返回
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]);}}}