当前位置：首页 > backend >正文

240422 leetcode exercises

backend 2025/5/18 12:55:31

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/)
- - 🔁直接遍历
  - 🔁动归预处理

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|)。