11.滑動(dòng)窗口最大值

題目描述

239. 滑動(dòng)窗口最大值

給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。

返回 滑動(dòng)窗口中的最大值 。

示例 1：

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動(dòng)窗口的位置                最大值
---------------               -----
[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]

思路：滑動(dòng)窗口+單調(diào)隊(duì)列

1. 單調(diào)隊(duì)列：
   • 使用一個(gè)雙端隊(duì)列（Deque）來(lái)存儲(chǔ)數(shù)組的索引。
   • 隊(duì)列中的元素按從大到小的順序排列，隊(duì)頭元素是當(dāng)前窗口的最大值。
2. 滑動(dòng)窗口：
   • 遍歷數(shù)組，維護(hù)一個(gè)大小為 k 的滑動(dòng)窗口。
   • 在遍歷過(guò)程中，動(dòng)態(tài)更新隊(duì)列，確保隊(duì)列中的元素始終在窗口內(nèi)，并且按從大到小的順序排列。
3. 隊(duì)列更新規(guī)則：
   • 移除不在窗口內(nèi)的元素：如果隊(duì)頭元素已經(jīng)不在當(dāng)前窗口內(nèi)，則將其從隊(duì)列中移除。
   • 移除小于當(dāng)前元素的元素：從隊(duì)尾開(kāi)始，移除所有小于當(dāng)前元素的元素，確保隊(duì)列的單調(diào)性。
   • 將當(dāng)前元素加入隊(duì)列：將當(dāng)前元素的索引加入隊(duì)尾。
4. 記錄結(jié)果：
   • 當(dāng)窗口形成時(shí)（i >= k - 1），將隊(duì)頭元素（當(dāng)前窗口的最大值）加入結(jié)果數(shù)組。

我認(rèn)為本題真的很難，第一次不懂的話可以過(guò)段時(shí)間再看。

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; // 計(jì)算結(jié)果數(shù)組的大小int* result = (int*)malloc(sizeof(int) * (*returnSize)); // 分配結(jié)果數(shù)組int queue[numsSize]; // 使用數(shù)組模擬雙端隊(duì)列int head = 0, tail = -1; // 隊(duì)列的頭和尾for (int i = 0; i < numsSize; i++) {// 移除隊(duì)列中不在當(dāng)前窗口內(nèi)的元素if (head <= tail && queue[head] < i - k + 1) {head++;}// 移除隊(duì)列中所有小于當(dāng)前元素的元素while (head <= tail && nums[queue[tail]] < nums[i]) {tail--;}// 將當(dāng)前元素的索引加入隊(duì)列queue[++tail] = i;// 如果窗口已經(jīng)形成，將隊(duì)列頭部的元素加入結(jié)果數(shù)組if (i >= k - 1) {result[i - k + 1] = nums[queue[head]];}}return result; // 返回結(jié)果數(shù)組
}

12.最小覆蓋子串

題目描述

76. 最小覆蓋子串

給你一個(gè)字符串 s 、一個(gè)字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。

注意：

• 對(duì)于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
• 如果 s 中存在這樣的子串，我們保證它是唯一的答案。

示例 1：

輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"
解釋：最小覆蓋子串 "BANC" 包含來(lái)自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

輸入：s = "a", t = "a"
輸出："a"
解釋：整個(gè)字符串 s 是最小覆蓋子串。

示例 3:

輸入: s = "a", t = "aa"
輸出: ""
解釋: t 中兩個(gè)字符 'a' 均應(yīng)包含在 s 的子串中，
因此沒(méi)有符合條件的子字符串，返回空字符串。

思路：雙指針/滑動(dòng)窗口+哈希

題目中的4個(gè)提示已經(jīng)給出了本題思路：

• Use two pointers to create a window of letters in s, which would have all the characters from t.
  使用兩個(gè)指針在 s 中創(chuàng)建一個(gè)字母窗口，該窗口將包含 t 中的所有字符。
• Expand the right pointer until all the characters of t are covered.
  展開(kāi)右指針，直到覆蓋 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.
  覆蓋所有字符后，移動(dòng)左指針并確保仍覆蓋所有字符，以最小化子數(shù)組大小。
• Continue expanding the right and left pointers until you reach the end of s.
  繼續(xù)展開(kāi)左右指針，直到到達(dá) s 的末尾。

具體代碼思路：

1. 初始化哈希表：
   • hasht[128]：記錄 t 中每個(gè)字符的出現(xiàn)次數(shù)。
   • hashs[128]：記錄當(dāng)前窗口內(nèi)字符的出現(xiàn)次數(shù)。
2. 滑動(dòng)窗口雙指針：
   • left 和 right 指針?lè)謩e表示窗口的左右邊界。
   • right 向右擴(kuò)展窗口，直到窗口包含 t 的所有字符。
   • 當(dāng)窗口有效時(shí)，left 向右收縮以尋找更小的窗口。
3. 計(jì)數(shù)器 count 的作用：
   • 統(tǒng)計(jì)當(dāng)前窗口中恰好滿(mǎn)足 t 字符需求的字符數(shù)量。
   • 當(dāng) count == strlen(t) 時(shí)，說(shuō)明窗口已覆蓋 t 的所有字符。
4. 更新最小窗口：
   • 每次窗口有效時(shí)，記錄窗口的起始位置和長(zhǎng)度。
   • 最終返回最小窗口對(duì)應(yīng)的子串。

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 的長(zhǎng)度char* ans = malloc(sizeof(char) * (m + 1)); // 分配結(jié)果數(shù)組if (m < n) return ""; // 如果 s 的長(zhǎng)度小于 t，直接返回空字符串int hashs[130] = {0}; // 記錄 s 中當(dāng)前窗口的字符頻率int hasht[130] = {0}; // 記錄 t 中字符的頻率// 統(tǒng)計(jì) t 中字符的頻率for (int i = 0; i < n; i++) {hasht[t[i]]++;}int l = 0, r = 0; // 滑動(dòng)窗口的左右指針int indexl = 0, indexr = 0; // 最小窗口的左右索引int minlen = m + 1; // 最小窗口長(zhǎng)度// 初始化窗口while (r < n) {hashs[s[r]]++; // 更新 s 中當(dāng)前窗口的字符頻率r++; // 右指針右移}// 滑動(dòng)窗口while (r < m) {bool flag = true;// 檢查當(dāng)前窗口是否滿(mǎn)足 t 中字符的頻率要求for (int i = 0; i <= 128; i++) {if (hashs[i] < hasht[i]) {flag = false; // 如果不滿(mǎn)足，設(shè)置 flag 為 falsebreak;}}if (flag) {// 如果滿(mǎn)足條件，更新最小窗口if (r - l < minlen) {minlen = r - l;indexl = l;indexr = r;}// 移動(dòng)左指針，縮小窗口hashs[s[l]]--;l++;} else {// 如果不滿(mǎn)足條件，移動(dòng)右指針，擴(kuò)展窗口hashs[s[r]]++;r++;}}// 最后檢查一次窗口bool flag = true;while (flag) {for (int i = 0; i <= 128; i++) {if (hashs[i] < hasht[i]) {flag = false; // 如果不滿(mǎn)足，設(shè)置 flag 為 falsebreak;}}if (!flag) break; // 如果不滿(mǎn)足條件，退出循環(huán)// 如果滿(mǎn)足條件，更新最小窗口if (r - l < minlen) {minlen = r - l;indexl = l;indexr = m;}// 移動(dòng)左指針，縮小窗口hashs[s[l]]--;l++;}// 如果最小窗口長(zhǎng)度未更新，說(shuō)明沒(méi)有符合條件的子串if (minlen == m + 1) return "";// 將結(jié)果復(fù)制到 ans 中for (int i = indexl; i < indexr; i++) {ans[i - indexl] = s[i];}ans[minlen] = '\0'; // 添加字符串結(jié)束符return ans; // 返回結(jié)果
}

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 的長(zhǎng)度小于 t，直接返回空字符串char* ans = malloc(sizeof(char) * (m + 1)); // 分配結(jié)果數(shù)組int hashs[128] = {0}; // 記錄 s 中當(dāng)前窗口的字符頻率int hasht[128] = {0}; // 記錄 t 中字符的頻率// 統(tǒng)計(jì) t 中字符的頻率for (int i = 0; i < n; i++) {hasht[t[i]]++;}int l = 0, r = 0; // 滑動(dòng)窗口的左右指針int minlen = m + 1; // 最小窗口長(zhǎng)度int indexl = 0, indexr = 0; // 最小窗口的左右索引int count = 0; // 記錄當(dāng)前窗口中滿(mǎn)足 t 中字符頻率的字符數(shù)量while (r < m) {// 如果當(dāng)前字符在 t 中出現(xiàn)過(guò)，則更新 hashs 和 countif (hasht[s[r]] > 0) {hashs[s[r]]++;if (hashs[s[r]] <= hasht[s[r]]) {count++;}}r++;// 如果當(dāng)前窗口滿(mǎn)足 t 中字符的頻率要求while (count == n) {// 更新最小窗口if (r - l < minlen) {minlen = r - l;indexl = l;indexr = r;}// 移動(dòng)左指針，縮小窗口if (hasht[s[l]] > 0) {hashs[s[l]]--;if (hashs[s[l]] < hasht[s[l]]) {count--;}}l++;}}// 如果最小窗口長(zhǎng)度未更新，說(shuō)明沒(méi)有符合條件的子串if (minlen == m + 1) return "";// 將結(jié)果復(fù)制到 ans 中strncpy(ans, s + indexl, minlen);ans[minlen] = '\0'; // 添加字符串結(jié)束符return ans; // 返回結(jié)果
}

13.最大子數(shù)組和

題目描述

53. 最大子數(shù)組和

給你一個(gè)整數(shù)數(shù)組 nums ，請(qǐng)你找出一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

子數(shù)組是數(shù)組中的一個(gè)連續(xù)部分。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。

示例 2：

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

示例 3：

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

思路：dp/貪心

1. 定義狀態(tài)：

   • 定義 dp[i] 表示以 nums[i] 結(jié)尾的最大子數(shù)組和。

2. 狀態(tài)轉(zhuǎn)移方程：

   • 如果 dp[i-1] 是正數(shù)，則將其加入當(dāng)前元素 nums[i]，形成更大的子數(shù)組和。

   • 如果 dp[i-1] 是負(fù)數(shù)，則以當(dāng)前元素 nums[i] 作為新的子數(shù)組起點(diǎn)。

   • 狀態(tài)轉(zhuǎn)移方程為：

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

3. 初始化：

   • dp[0] = nums[0]，因?yàn)橐缘谝粋€(gè)元素結(jié)尾的最大子數(shù)組和就是它本身。

4. 遍歷數(shù)組：

   • 從第二個(gè)元素開(kāi)始，依次計(jì)算 dp[i]，并更新全局最大值 ans。

5. 返回結(jié)果：

   • 返回全局最大值 ans。

code

#include <stdio.h>
#include <stdlib.h>int maxSubArray(int* nums, int numsSize) {if (nums == NULL || numsSize == 0) return 0; // 如果數(shù)組為空，直接返回 0int dp[numsSize]; // 定義 dp 數(shù)組，dp[i] 表示以 nums[i] 結(jié)尾的最大子數(shù)組和dp[0] = nums[0]; // 初始化 dp[0]int ans = dp[0]; // 初始化全局最大值for (int i = 1; i < numsSize; i++) {// 狀態(tài)轉(zhuǎn)移方程：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.合并區(qū)間

題目描述

56. 合并區(qū)間

以數(shù)組 intervals 表示若干個(gè)區(qū)間的集合，其中單個(gè)區(qū)間為 intervals[i] = [starti, endi] 。請(qǐng)你合并所有重疊的區(qū)間，并返回 一個(gè)不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 。

示例 1：

輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

示例 2：

輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋：區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。

思路：貪心

本題比較簡(jiǎn)單，直接拷貝之前的文章

代碼隨想錄——貪心

• 按區(qū)間的起始位置排序。
• 遍歷區(qū)間，如果當(dāng)前區(qū)間與前一個(gè)區(qū)間重疊，則合并它們；否則，將前一個(gè)區(qū)間加入結(jié)果列表。

個(gè)人感覺(jué)比較簡(jiǎn)單~~

code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>// 比較函數(shù)，用于按區(qū)間的起始位置從小到大排序
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) {// 按區(qū)間的起始位置排序qsort(intervals, intervalsSize, sizeof(int*), cmp);// 分配結(jié)果數(shù)組的內(nèi)存int** res = malloc(sizeof(int*) * intervalsSize);// 初始化返回的區(qū)間數(shù)量為 0*returnSize = 0;// 初始化當(dāng)前區(qū)間的起始和結(jié)束位置int start = intervals[0][0];int end = intervals[0][1];// 遍歷所有區(qū)間for (int i = 1; i < intervalsSize; i++) {// 如果當(dāng)前區(qū)間與前一個(gè)區(qū)間重疊if (intervals[i][0] <= end) {// 合并區(qū)間，更新結(jié)束位置end = fmax(end, intervals[i][1]);} else {// 如果不重疊，將前一個(gè)區(qū)間加入結(jié)果列表res[*returnSize] = malloc(sizeof(int) * 2);res[*returnSize][0] = start;res[*returnSize][1] = end;(*returnSize)++;// 更新當(dāng)前區(qū)間的起始和結(jié)束位置start = intervals[i][0];end = intervals[i][1];}}// 將最后一個(gè)區(qū)間加入結(jié)果列表res[*returnSize] = malloc(sizeof(int) * 2);res[*returnSize][0] = start;res[*returnSize][1] = end;(*returnSize)++;// 分配列大小數(shù)組的內(nèi)存*returnColumnSizes = malloc(sizeof(int) * (*returnSize));// 設(shè)置每個(gè)區(qū)間的列大小為 2for (int i = 0; i < *returnSize; i++) {(*returnColumnSizes)[i] = 2;}// 返回結(jié)果數(shù)組return res;
}

15.輪轉(zhuǎn)數(shù)組

題目描述

189. 輪轉(zhuǎn)數(shù)組

給定一個(gè)整數(shù)數(shù)組 nums，將數(shù)組中的元素向右輪轉(zhuǎn) k 個(gè)位置，其中 k 是非負(fù)數(shù)。

示例 1:

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

示例 2:

輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋: 
向右輪轉(zhuǎn) 1 步: [99,-1,-100,3]
向右輪轉(zhuǎn) 2 步: [3,99,-1,-100]

思路：反轉(zhuǎn)法

1. 反轉(zhuǎn)整個(gè)數(shù)組。
2. 反轉(zhuǎn)前 k 個(gè)元素。
3. 反轉(zhuǎn)剩余 n - k 個(gè)元素。

證明：

1. 初始數(shù)組：

   • 數(shù)組 nums 可以表示為：
     $$nums=[a_0,a_1,...,a_{n?k?1},a_{n?k},a_{n?k+1},...,a_{n?1}]$$

2. 第一次反轉(zhuǎn)（反轉(zhuǎn)整個(gè)數(shù)組）：

   • 反轉(zhuǎn)后，數(shù)組變?yōu)?#xff1a;
     $$nums=[a_{n?1},...,a_{n?k+1},a_{n?k},a_{n?k?1},...,a_0]$$

3. 第二次反轉(zhuǎn)（反轉(zhuǎn)前 k 個(gè)元素）：

   • 反轉(zhuǎn)前 k 個(gè)元素后，數(shù)組變?yōu)?#xff1a;
     $$nums=[a_{n?k},...,a_{n?1},a_{n?k?1},...,a_0]$$

4. 第三次反轉(zhuǎn)（反轉(zhuǎn)剩下的 n - k 個(gè)元素）：

   • 反轉(zhuǎn)剩下的 n - k 個(gè)元素后，數(shù)組變?yōu)?#xff1a;
     $$nums=[a_{n?k},...,a_{n?1},a_0,...,a_{n?k?1}]$$

網(wǎng)上有很多種證明，我覺(jué)得這樣是最直觀的

code

#include <stdio.h>// 反轉(zhuǎn)數(shù)組的輔助函數(shù)
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 大于數(shù)組長(zhǎng)度的情況if (k == 0) return; // 如果 k 為 0，直接返回// 反轉(zhuǎn)整個(gè)數(shù)組reverse(nums, 0, numsSize - 1);// 反轉(zhuǎn)前 k 個(gè)元素reverse(nums, 0, k - 1);// 反轉(zhuǎn)剩下的 n - k 個(gè)元素reverse(nums, k, numsSize - 1);
}

16.除自身以外數(shù)組的乘積

題目描述

238. 除自身以外數(shù)組的乘積

給你一個(gè)整數(shù)數(shù)組 nums，返回 數(shù)組 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積 。

題目數(shù)據(jù) 保證 數(shù)組 nums之中任意元素的全部前綴元素和后綴的乘積都在 32 位 整數(shù)范圍內(nèi)。

請(qǐng) **不要使用除法，**且在 O(n) 時(shí)間復(fù)雜度內(nèi)完成此題。

示例 1:

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

示例 2:

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

思路：前綴積+后綴積

1. 前綴積：
   • 從左到右遍歷數(shù)組，計(jì)算每個(gè)位置左側(cè)所有元素的乘積。
2. 后綴積：
   • 從右到左遍歷數(shù)組，計(jì)算每個(gè)位置右側(cè)所有元素的乘積。
3. 結(jié)果計(jì)算：
   • 對(duì)于每個(gè)位置 i，結(jié)果 ans[i] 等于前綴積 left[i] 乘以后綴積 right[i]。

code

#include <stdio.h>
#include <stdlib.h>int* productExceptSelf(int* nums, int numsSize, int* returnSize) {// 分配結(jié)果數(shù)組的內(nèi)存int* ans = malloc(sizeof(int) * numsSize);*returnSize = numsSize; // 設(shè)置返回?cái)?shù)組的大小// 定義前綴積數(shù)組 left 和后綴積數(shù)組 rightint left[numsSize];  // 存儲(chǔ)每個(gè)位置左側(cè)所有元素的乘積int right[numsSize]; // 存儲(chǔ)每個(gè)位置右側(cè)所有元素的乘積// 計(jì)算前綴積left[0] = 1; // 第一個(gè)元素左側(cè)沒(méi)有元素，前綴積為 1for (int i = 1; i < numsSize; i++) {left[i] = left[i - 1] * nums[i - 1]; // 前綴積 = 前一個(gè)前綴積 * 前一個(gè)元素}// 計(jì)算后綴積right[numsSize - 1] = 1; // 最后一個(gè)元素右側(cè)沒(méi)有元素，后綴積為 1for (int i = numsSize - 2; i >= 0; i--) {right[i] = right[i + 1] * nums[i + 1]; // 后綴積 = 后一個(gè)后綴積 * 后一個(gè)元素}// 計(jì)算結(jié)果數(shù)組for (int i = 0; i < numsSize; i++) {ans[i] = left[i] * right[i]; // 結(jié)果 = 前綴積 * 后綴積}return ans; // 返回結(jié)果數(shù)組
}

17.缺失的第一個(gè)正數(shù)

題目描述

41. 缺失的第一個(gè)正數(shù)

給你一個(gè)未排序的整數(shù)數(shù)組 nums ，請(qǐng)你找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)。

請(qǐng)你實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 并且只使用常數(shù)級(jí)別額外空間的解決方案。

示例 1：

輸入：nums = [1,2,0]
輸出：3
解釋：范圍 [1,2] 中的數(shù)字都在數(shù)組中。

示例 2：

輸入：nums = [3,4,-1,1]
輸出：2
解釋：1 在數(shù)組中，但 2 沒(méi)有。

示例 3：

輸入：nums = [7,8,9,11,12]
輸出：1
解釋：最小的正數(shù) 1 沒(méi)有出現(xiàn)。

思路：哈希

本題如果拋棄時(shí)間和空間的限制是蠻簡(jiǎn)單的。

有兩種思路：

1.開(kāi)辟額外空間建立哈希表，記錄1~numSize的數(shù)是否出現(xiàn)。空間復(fù)雜度O(N)

2.先對(duì)原數(shù)組排序，再尋找沒(méi)有出現(xiàn)的最小正整整。時(shí)間復(fù)雜度O(NlogN)。

雖然上面兩種方法都可以解決，但是不能滿(mǎn)足題目的要求。這里的思路是：原地哈希。

具體步驟：

1. 原地哈希：
   • 將數(shù)組中的每個(gè)正整數(shù)放到它應(yīng)該在的位置
   • 如果當(dāng)前數(shù)在 1 到 numsSize之間，并且它不在正確的位置上，將它交換到正確的位置。
2. 查找缺失的正整數(shù)：
   • 最后遍歷數(shù)組，找到第一個(gè)正數(shù)的位置 i，i + 1 就是缺失的最小正整數(shù)。
   • 如果所有位置都是負(fù)數(shù)，則缺失的最小正整數(shù)是 n + 1。

code

#include <stdio.h>// 交換兩個(gè)整數(shù)的值
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}int firstMissingPositive(int* nums, int numsSize) {// 第一步：將數(shù)組中的每個(gè)正整數(shù)放到它應(yīng)該在的位置for (int i = 0; i < numsSize; i++) {// 如果當(dāng)前數(shù)在 1 到 numsSize 之間，并且它不在正確的位置上while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {// 將它交換到正確的位置swap(&nums[i], &nums[nums[i] - 1]);}}// 第二步：遍歷數(shù)組，找到第一個(gè)不滿(mǎn)足 nums[i] == i + 1 的位置for (int i = 0; i < numsSize; i++) {if (nums[i] != i + 1) {return i + 1;}}// 如果所有位置都滿(mǎn)足條件，返回 numsSize + 1return numsSize + 1;
}

18.矩陣置零

題目描述

73. 矩陣置零

給定一個(gè) *m* x *n* 的矩陣，如果一個(gè)元素為 0 ，則將其所在行和列的所有元素都設(shè)為 0 。請(qǐng)使用 原地 算法**。**

示例 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.問(wèn)題分析：

• 我們需要將矩陣中所有 0 所在的行和列都置為 0。
• 直接修改矩陣會(huì)導(dǎo)致后續(xù)的 0 被誤判，因此需要先記錄哪些行和列需要置零。

2.核心思想：

• 使用兩個(gè)輔助數(shù)組 row 和 col，分別記錄哪些行和列需要置零。
• 遍歷矩陣，如果發(fā)現(xiàn) matrix[i][j] == 0，則標(biāo)記 row[i] 和 col[j] 為 true。
• 再次遍歷矩陣，根據(jù) row 和 col 的標(biāo)記，將對(duì)應(yīng)的行和列置零。

3.優(yōu)化：

• 可以使用矩陣的第一行和第一列來(lái)替代輔助數(shù)組，從而將空間復(fù)雜度優(yōu)化為 O(1)。

code

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {// 定義兩個(gè)輔助數(shù)組，用于記錄哪些行和列需要置零bool col[200]; // 記錄列是否需要置零bool row[200]; // 記錄行是否需要置零memset(col, false, sizeof(col)); // 初始化 col 數(shù)組為 falsememset(row, false, sizeof(row)); // 初始化 row 數(shù)組為 false// 遍歷矩陣，標(biāo)記需要置零的行和列for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < matrixColSize[i]; j++) {if (matrix[i][j] == 0) { // 如果當(dāng)前元素為 0if (!col[j]) col[j] = true; // 標(biāo)記列 j 需要置零if (!row[i]) row[i] = true; // 標(biāo)記行 i 需要置零}}}// 遍歷矩陣，將標(biāo)記的行置零for (int i = 0; i < matrixSize; i++) {if (row[i]) { // 如果行 i 需要置零for (int j = 0; j < matrixColSize[i]; j++) {matrix[i][j] = 0; // 將行 i 的所有元素置零}}}// 遍歷矩陣，將標(biāo)記的列置零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(優(yōu)化)

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;}}// 遍歷矩陣，標(biāo)記需要置零的行和列for (int i = 1; i < matrixSize; i++) {for (int j = 1; j < matrixColSize[i]; j++) {if (matrix[i][j] == 0) {matrix[i][0] = 0; // 標(biāo)記第 i 行需要置零matrix[0][j] = 0; // 標(biāo)記第 j 列需要置零}}}// 根據(jù)標(biāo)記置零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. 螺旋矩陣

給你一個(gè) m 行 n 列的矩陣 matrix ，請(qǐng)按照 順時(shí)針螺旋順序 ，返回矩陣中的所有元素。

示例 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 分別表示當(dāng)前遍歷的上下邊界。
   • left 和 right 分別表示當(dāng)前遍歷的左右邊界。

2. 螺旋遍歷核心邏輯：

   • 從左到右遍歷上邊界：將上邊界的元素加入結(jié)果數(shù)組，然后上邊界下移。
   • 從上到下遍歷右邊界：將右邊界的元素加入結(jié)果數(shù)組，然后右邊界左移。
   • 從右到左遍歷下邊界：將下邊界的元素加入結(jié)果數(shù)組，然后下邊界上移。
   • 從下到上遍歷左邊界：將左邊界的元素加入結(jié)果數(shù)組，然后左邊界右移。

   注：每次遍歷完一個(gè)邊界后修改邊界值

3. 終止條件：

   • 當(dāng)上邊界超過(guò)下邊界或左邊界超過(guò)右邊界時(shí)，遍歷結(jié)束。

4. 邊界條件處理：

   • 如果矩陣為空，直接返回 NULL 并設(shè)置 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;          // 矩陣的行數(shù)int n = matrixColSize[0];    // 矩陣的列數(shù)int* ans = malloc(sizeof(int) * m * n); // 結(jié)果數(shù)組*returnSize = 0;             // 初始化返回?cái)?shù)組的大小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--; // 右邊界左移// 如果上邊界超過(guò)下邊界，說(shuō)明已經(jīng)遍歷完if (top > bottom) break;// 從右到左遍歷下邊界for (int j = right; j >= left; j--) {ans[(*returnSize)++] = matrix[bottom][j];}bottom--; // 下邊界上移// 如果左邊界超過(guò)右邊界，說(shuō)明已經(jīng)遍歷完if (left > right) break;// 從下到上遍歷左邊界for (int i = bottom; i >= top; i--) {ans[(*returnSize)++] = matrix[i][left];}left++; // 左邊界右移}return ans;
}

20.旋轉(zhuǎn)圖像

題目描述

48. 旋轉(zhuǎn)圖像

給定一個(gè) n × n 的二維矩陣 matrix 表示一個(gè)圖像。請(qǐng)你將圖像順時(shí)針旋轉(zhuǎn) 90 度。

你必須在** 原地** 旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請(qǐng)不要 使用另一個(gè)矩陣來(lái)旋轉(zhuǎn)圖像。

示例 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]]

思路一：水平翻轉(zhuǎn)+轉(zhuǎn)置

證明略。。。(后面再補(bǔ))

code

//主對(duì)角線翻轉(zhuǎn)+水平翻轉(zhuǎn)
void swap(int *a,int *b){int temp=*a;*a=*b;*b=temp;
}
void rotate(int** matrix, int matrixSize, int* matrixColSize) {//水平翻轉(zhuǎn)for(int i=0;i<matrixSize/2;i++){for(int j=0;j<matrixSize;j++){swap(&matrix[i][j],&matrix[matrixSize-1-i][j]);}}//主對(duì)角線翻轉(zhuǎn)for(int i=0;i<matrixSize;i++){for(int j=i+1;j<matrixSize;j++){swap(&matrix[i][j],&matrix[j][i]);}}}