jsp网站有哪些,广州协会网站建设,学做软件的网站,做网站需要多少钱呢文章目录 11.滑动窗口最大值题目描述思路#xff1a;滑动窗口单调队列code 12.最小覆盖子串题目描述思路#xff1a;双指针/滑动窗口哈希code Ⅰcode Ⅱ 13.最大子数组和题目描述思路#xff1a;dp/贪心code 14.合并区间题目描述思路#xff1a;贪心code 15.轮转数组题目描… 文章目录 11.滑动窗口最大值题目描述思路滑动窗口单调队列code 12.最小覆盖子串题目描述思路双指针/滑动窗口哈希code Ⅰcode Ⅱ 13.最大子数组和题目描述思路dp/贪心code 14.合并区间题目描述思路贪心code 15.轮转数组题目描述思路反转法code 16.除自身以外数组的乘积题目描述思路前缀积后缀积code 17.缺失的第一个正数题目描述思路哈希code 18.矩阵置零题目描述思路哈希codecode(优化) 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.hint* 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.hchar* 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.hchar* 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.hint 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-k1}, ..., a_{n-1}] nums[a0,a1,...,an−k−1,an−k,an−k1,...,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-k1}, a_{n-k}, a_{n-k-1}, ..., a_{0}] nums[an−1,...,an−k1,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.hint* 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之间并且它不在正确的位置上将它交换到正确的位置。 查找缺失的正整数 最后遍历数组找到第一个正数的位置 ii 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;*btemp;
}
void rotate(int** matrix, int matrixSize, int* matrixColSize) {//水平翻转for(int i0;imatrixSize/2;i){for(int j0;jmatrixSize;j){swap(matrix[i][j],matrix[matrixSize-1-i][j]);}}//主对角线翻转for(int i0;imatrixSize;i){for(int ji1;jmatrixSize;j){swap(matrix[i][j],matrix[j][i]);}}}
