力扣热题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)操作还有精准搜索searchword和前缀匹配startWithprefix在这里我就不一一指出了。287.寻找重复数组这道题的题目要求不修改数组且O1额外空间那这道题目的经典解法就是利用快慢指针Floyd判圈算法将数组视为一个隐式的链表重复数就是环的入口。数组长度为n1所有数字在[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 cntvoid 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_queueListNode*, vectorListNode*, decltype(cmp) pq(cmp);ok,到这里力扣的热题100部分就结束了有错误欢迎提出感谢观看。