力扣热题100题第二部分

208.实现Trie（前缀树）

这道题目中要实现的Trie(前缀树）。它不光是一个数据结构，更是一种用空间换时间，按前缀组织字符串的思想。它的核心优势有：前缀查询极快、动态插入不影响已有结构、自动压缩公共前缀。它的应用也挺广泛的，例如：自动补全，拼写检查....而它在本题的核心操作代码是：

void insert(string word){ Node* cur = root; for(char c : word){ int idx = c - 'a'; if(!cur->children[idx]) cur->children[idx] = new Node(); cur = cur->children[idx]; } cur->isEnd = true; }

这里我举出的是它的插入insert(word)操作，还有精准搜索search（word）和前缀匹配startWith（prefix）在这里我就不一一指出了。

287.寻找重复数组

这道题的题目要求不修改数组且O（1）额外空间，那这道题目的经典解法就是利用快慢指针（Floyd判圈算法），将数组视为一个隐式的链表，重复数就是环的入口。

数组长度为n+1，所有数字在[1, n]内。我们可以构建一个映射：索引i→nums[i]。
从索引0开始，不断跳转i = nums[i]，由于存在重复数，这个跳转序列最终会进入一个环。

// 第一阶段：找到相遇点 do { slow = nums[slow]; // 慢指针走一步 fast = nums[nums[fast]]; // 快指针走两步 } while (slow != fast); // 第二阶段：找到环入口 slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; // 或 fast，两者相同 }

139.单词拆分

这个题目的代码中使用了C++中string的成员函数substr，来截取子串，从而来拆分单词。

for (int i = 1; i <= n; ++i) { // 外层：枚举要拼接的终点位置 for (int j = 0; j < i; ++j) { // 内层：枚举“最后一个单词”的起点 if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; } } }

其中substr这个内部：

• j是子串的起始索引。

• i是当前要判断的前缀长度（结束位置）。

• i - j就是子串的长度。

从索引j开始取i-j个字符。

2.两数相加

这个题目里使用了类似于虚拟头节点的哑节点dummy，用来简化结果链表的构建。

用指针cur指向结果链表的尾部，初始为dummy。

用变量carry记录进位（0或1）

同时遍历两个链表，知道两个链表都遍历完且没有进位。

返回dummy->next。

ListNode dummy(0); // 哑节点 ListNode* cur = &dummy; // 结果链表尾指针 int carry = 0; // 进位 while (l1 || l2 || carry) { int val1 = l1 ? l1->val : 0; int val2 = l2 ? l2->val : 0; int sum = val1 + val2 + carry; carry = sum / 10; // 进位 cur->next = new ListNode(sum % 10); // 当前位 cur = cur->next; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } return dummy.next; }

152.乘积最大子数组

这个题目中出现了转移方程这个工具，这个工具的核心就是考虑当前数怎么和前面连接，从而算出以当前数结尾的最大乘积和最小乘积。以当前数结尾的最大乘积，是“自己单干”，‘接在最大值后’还是“接在前面最小值后”，三者取最优。同时更新最小值，为后续的负负得正做准备。

int tempMax = max({nums[i], maxProd * nums[i], minProd * nums[i]}); int tempMin = min({nums[i], maxProd * nums[i], minProd * nums[i]}); maxProd = tempMax; minProd = tempMin;

230.二叉搜索树中第K小的元素

这个题目中用到了全局计数器（在递归函数中以引用方式传递，相当于全局作用），它正好放在“访问根节点”的代码位置，即中序遍历的中间步骤，符合“左，中，右”的顺序，确保找到的是第k小的元素。

inorder(node->left, k, cnt, ans); // 递归左子树 if (++cnt == k) { // ← 计数在这里增加，并检查是否到达第 k 个 ans = node->val; return; // 找到后提前返回，不再继续遍历 } inorder(node->right, k, cnt, ans); // 没找到才继续右子树

还有就是这个题目中也提到了为什么要引用int& cnt

void inorder(TreeNode* node, int k, int& cnt, int& ans)

如果不用引用，cnt的改变无法在递归调用之间共享，每一层递归会操作同一个cnt，这样所有节点的访问才能累加计数，ans同理，找到答案后需要被外层的调用者知晓。

148.排序链表

这道题目用到了归并排序（自顶向下归并）

归并排序分为三步：

1.分割：用快慢指针找到链表中点，将链表从中断开，分成左右两个子链表。

// 快慢指针找中点 ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } ListNode* mid = slow->next; slow->next = nullptr; // 从中间断开

2.递归排序：对左右子链表分别排序。

// 递归排序左右两部分 ListNode* left = sortList(head); ListNode* right = sortList(mid);

3.合并：将两个有序子链表合并成一个有序链表（复用“合并两个有序链表”的逻辑）。

// 合并两个有序链表 return merge(left, right);

递归终止条件：链表为空或只有一个节点时，已经有序，直接返回。

23.合并K个升序链表

这道题用的是优先队列（最小堆），其中使用到了decltype这一C++关键词，用来查询一个表达式或变量的类型，而不实际计算它。其中的cmp是一个lambda表达式（匿名函数），它的类型是由编辑器自动生成的，无法用常规语法写出来，（比如bool(*)(ListNode*, ListNode*)只能表示函数指针，不能表示捕获列表为空的 lambda 类型，虽然这里确实可以转为函数指针，但为了通用性用了decltype）。

auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

ok,到这里力扣的热题100部分就结束了，有错误欢迎提出，感谢观看。