240422 leetcode exercises

@jarringslee

文章目錄

240422 leetcode exercises
- [237. 刪除鏈表中的節點](https://leetcode.cn/problems/delete-node-in-a-linked-list/)
- - 🔁節點覆蓋法
- [392. 判斷子序列](https://leetcode.cn/problems/is-subsequence/)
- - 🔁直接遍歷
  - 🔁動歸預處理
- [LCR 136. 刪除鏈表的節點](https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/)
- - 🔁直接遍歷

237. 刪除鏈表中的節點

有一個單鏈表的 head，我們想刪除它其中的一個節點 node。

給你一個需要刪除的節點 node 。你將 無法訪問 第一個節點 head。

鏈表的所有值都是 唯一的，并且保證給定的節點 node 不是鏈表中的最后一個節點。

刪除給定的節點。注意，刪除節點并不是指從內存中刪除它。這里的意思是：

給定節點的值不應該存在于鏈表中。
鏈表中的節點數應該減少 1。
node 前面的所有值順序相同。
node 后面的所有值順序相同。

? 他是想說什么意思呢，就是在不給你整個鏈表的情況下，讓你根據這個值來將這個節點刪除。

? 題目要求我們的函數被調用后輸出整個鏈表，而我們又注意到所寫函數是void類型，所以我們只需要執行刪除該節點的操作即可。

? 如果毫無思路，我們可以回憶一下刪除鏈表的原理：

讓上一個結點的next指針直接指向下一個節點。

? 由于我們需要對鏈表進行遍歷，才能獲得前驅指針并執行上述操作。但是這里我們根本無法獲取前驅指針。但是我們寫的函數又不需要我們返回鏈表，所以如果讓當前節點的值直接變成下一結點的值，也就是覆蓋下一個節點，是不是就等價于刪除了當前節點呢？

🔁節點覆蓋法

假設鏈表在內存中是這樣的（箭頭表示 next 指針）：

 → [ A | * ] → [ B | * ] → [ C | * ] → …↑題目給出的node

[A|*] 表示當前節點的 val = A，next 指向下一個節點。
node 指針正指向值為 A 的節點，我們刪掉它。

void deleteNode(struct ListNode* node) {*node = *node -> next; //哈哈就一行。
}

這一行等價于同時做了兩件事：

node->val  = node->next->val;    // 把后繼節點的值 B 復制到當前節點
node->next = node->next->next;   // 把后繼節點的 next 指針復制過來

我們看看這個操作帶來了什么樣的影響：

操作前
```
[ A | -> X ]   [ B | -> Y ]node           next_node
```
- node->val = A
- node->next 指向下一個節點（值 B）
執行 *node = *node->next;
- node->val 變成了 B
- node->next 變成了 node->next->next（即原來 B 的 next，指向 C）
操作后
```
[ B | -> Y ]   [ B | -> Y ]  node         (原 B 節點，已被孤立)
```
現在的鏈表里，從 …→node 開始
```
… → [ B | * ] → [ C | * ] → …
```
——等價于把原來的 B 節點直接「搬到」A 的位置，然后把原 B 節點從鏈表里跳過去了。

? 這道題通過 復制后繼節點 到當前節點，再跳過后繼，實現了在不知道前驅的情況下刪除節點的目標。關鍵一句 *node = *node->next;，相當于同時做了賦值 val 和重連 next，從鏈表邏輯上刪掉了下一節點。

? 我簡直是天才。

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

? 乍一看以為是包含字符串的問題，結果仔細一看，發現如果子序列的所有字符能被給出序列順序地包含就符合條件。那么單次遍歷的話就會簡單很多。

🔁直接遍歷

直接建立循環直接進行比較。

bool isSubsequence(char* s, char* t) {if (s[0] == '\0') return true;//排除空字符串情況int i = 0;for (int j = 0; t[j] != '\0'; j++){ //外循環移動大串if (s[i] == t[j]) i++;//如果發現該位置與小串相等，小串移動if (s[i] == '\0') return true;//循環內移動完了就成功}return false;
}

? 但是題目又說， “當 t 很長、要對它執行大量（10億）子序列判斷查詢”，在這種變態情況下，我們想剛才那樣愚蠢地遍歷好像是有點笨拙了。但倘若我預處理目標串 t，一次性記錄好從每個位置往后字符 a…z 下次出現的位置，然后再用這個表快速「跳躍式」地在 t 中定位每個要匹配的 s[j]，閣下又該如何應對？

🔁動歸預處理

1. What is nxt?

? 我們使用 (n+1)×26 的二維整型數組，用來存儲 “從位置 i 開始，字母 'a'+c 下一次出現的位置”（其中 0 ≤ i ≤ n，0 ≤ c < 26）。

? nxt[i][c] 的含義是，在字符串 t 中，從下標 i（包含）往后，第一個字符等于 'a'+c 的位置索引；
如果再也不出現，即t 中再也沒有字符 ('a'+c)，我們就把它設為 n（一個「越界」值）。

int (*nxt)[SIGMA] = malloc((n + 1) * sizeof(int[SIGMA]));

? 如果 t 中再也沒有字符 ('a'+c)，我們就把它設為 n（一個「越界」值）。

? 這樣，查找 “從位置 i 往后，‘x’ 下次出現在哪里” 就只需要讀 nxt[i]['x'-'a'] 一次，時間 O(1)。

2. 構造 nxt 表

初始化末尾行
```
for (int j = 0; j < SIGMA; j++) {nxt[n][j] = n;
}
```
位置 n 之后沒有任何字符，所有字母的「下次出現」都標記為 n。
自底向上填表
```
for (int i = n - 1; i >= 0; i--) {// 先拷貝后一行：默認后續出現位置和 i+1 一樣memcpy(nxt[i], nxt[i + 1], SIGMA * sizeof(int));// 然后把 t[i] 這一個字符的“下次出現”位置修正為 i 自己nxt[i][t[i] - 'a'] = i;
}
```
- “如果我在 i+1 后面第一次見到 c，位置是誰？” → nxt[i+1][c]
- “但如果 t[i] 本身就是 c，就應該最近出現的位置是 i” → 覆蓋 nxt[i][c] = i
- 最終，nxt[0][c] 恰好告訴我們「整個串中第一次出現 c 的位置」。

3. 用 nxt 快速匹配子序列

int i = -1;
for (int j = 0; s[j] && i < n; j++) {// 在 t 中，從 i+1 開始，尋找 s[j] 下一個出現的位置i = nxt[i + 1][s[j] - 'a'];
}
return i < n;

我們用 i 記錄上一次匹配到 t 的哪個位置。若初始 i = -1，表示還沒匹配過任何字符；要找下一個，就從 i+1 = 0 開始搜。對于對每個 s[j]，我們先計算 c = s[j]-'a'，再讀 pos = nxt[i+1][c]。

如果 pos < n，說明在 t 中找到了，就把 i = pos，繼續下一個 s[j+1]。

如果 pos == n，說明找不到，就會讓 i >= n ，循環后自然跳出，最后 return false。

整個過程只做了 |s| 步 O(1) 的跳躍查詢，匹配結束后檢查 i < n 即可判斷 s 是否完全匹配為子序列。

時間和空間復雜度

預處理
時間：構造 nxt 需要做 n+1 行，每行拷貝 26 個整數 → O(26·n) ≈ O(n)。
空間：存 (n+1)×26 個 int → O(n·Σ)，這里 Σ=26。

匹配階段
時間：遍歷 s 一次，每步 O(1) 查表 → O(|s|)。

對于極多次查詢同一個 t 是否包含不同 s 的變態情況，這種預處理 + 跳表的方法尤其高效。

LCR 136. 刪除鏈表的節點

給定單向鏈表的頭指針和一個要刪除的節點的值，定義一個函數刪除該節點。

返回刪除后的鏈表的頭節點。

示例 1：
輸入：head = [4,5,1,9], val = 5
輸出：[4,1,9]
解釋：給定你鏈表中值為 5 的第二個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 1 -> 9.
示例 2：
輸入：head = [4,5,1,9], val = 1
輸出：[4,5,9]
解釋：給定你鏈表中值為 1 的第三個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 5 -> 9.

? 我們使用前去節點遍歷的方法來找到需要刪除的值。

🔁直接遍歷

? 首先去掉目標只在頭結點的情況。

? 我們讓前驅指針在下個節點的指針不指向空和下個節點的值不等于目標值的情況下向前移動，在題目保證數據的情況下，一定會在指針走向盡頭之前因為找到目標值而跳出這個循環。這時候我們讓前驅指針所在的節點的next指針直接指向下一個節點的next指針，也就是下下一個節點的地址。

struct ListNode* deleteNode(struct ListNode* head, int val) {if (head -> val == val) return head -> next;struct ListNode* prev = head;
//不滿足條件就遍歷while( (prev -> next != NULL) && (prev -> next -> val != val)) prev = prev -> next;
//找到目標值就刪if (prev -> next != NULL) prev -> next = prev -> next -> next; return head;
}