高频面试题

LeetCode 难度： 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...

LeetCode 难度： 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...

LeetCode 难度： 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...

LeetCode 208 https://leetcode.cn/problems/implement-trie-prefix-tree/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 前缀树其实就是一棵 26 叉树，对于 26 叉树的每个节点，可以用哈希表，或者长为 26 的数组来存储子节点。 初始化： 创建一棵 26 叉树，一开始只有一个根节点 root。26 叉树的每个节点包含一个长为 26 的儿子节点列表 son，以及一个布尔值 end，表示是否为终止节点。 insert： 遍历字符串 word，同时用一个变量 cur 表示当前在 26 叉树的哪个节点，初始值为 root。 如果 word[i] 不是 cur 的儿子，那么创建一个新的节点 node 作为 cur 的儿子。如果 word[i]=a，那么把 node 记录到 cur 的 son[0] 中。如果 word[i]=b，那么把 node 记录到 cur 的 son[1] 中。依此类推。 更新 cur 为儿子列表中的相应节点。 遍历结束，把 cur 的 end 标记为 true。 search 和 startsWith 可以复用同一个函数 find： 遍历字符串 word，同时用一个变量 cur 表示当前在 26 叉树的哪个节点，初始值为 root。 如果 word[i] 不是 cur 的儿子，返回 0。search 和 startsWith 收到 0 之后返回 false。 更新 cur 为儿子列表中的相应节点。 遍历结束，如果 cur 的 end 是 false，返回 1，否则返回 2。search 如果收到的是 2，返回 true，否则返回 false。startsWith 如果收到的是非 0 数字，返回 true，否则返回 false。 时间复杂度：初始化为 O(1)，insert 为 O(n∣Σ∣)，其余为 O(n)，其中 n 是 word 的长度，∣Σ∣=26 是字符集合的大小。注意创建一个节点需要 O(∣Σ∣) 的时间（如果用的是数组）。 空间复杂度：O(qn∣Σ∣)。其中 q 是 insert 的调用次数。 ...

LeetCode 347 https://leetcode.cn/problems/top-k-frequent-elements/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 桶排序。 第一步 答案与元素的出现次数有关，我们首先用一个哈希表 cnt 统计每个元素的出现次数。哈希表的 key 是元素值，value 是 key 在数组中的出现次数。 第二步 设出现次数最大值为 maxCnt，由于 maxCnt≤n，我们可以用桶排序，把出现次数相同的元素，放到同一个桶中。 创建一个大小为 maxCnt+1 的列表 buckets，其中 buckets[c] 存储出现次数为 c 的元素。（每个 buckets[c] 都是一个列表） 遍历 cnt，把出现次数为 c 的元素 x 添加到 buckets[c] 中。 第三步 倒序遍历 buckets，把 buckets[c] 中的元素加到答案中。 一旦答案的长度等于 k，就立刻返回答案。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(n)。 ...

LeetCode 328 https://leetcode.cn/problems/odd-even-linked-list/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 维护两个指针 odd 和 even 分别指向奇数节点和偶数节点，初始时 odd = head，even = evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点。 更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点，因此令 odd.next = even.next，然后令 odd = odd.next，此时 odd 变成 even 的后一个节点。 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点，因此令 even.next = odd.next，然后令 even = even.next，此时 even 变成 odd 的后一个节点。 在上述操作之后，即完成了对一个奇数节点和一个偶数节点的分离。重复上述操作，直到全部节点分离完毕。全部节点分离完毕的条件是 even 为空节点或者 even.next 为空节点，此时 odd 指向最后一个奇数节点（即奇数链表的最后一个节点）。 最后令 odd.next = evenHead，将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并，结果链表的头节点仍然是 head。 时间复杂度：O(n)，其中 n 是链表的节点数。需要遍历链表中的每个节点，并更新指针。 空间复杂度：O(1)。只需要维护有限的指针。 ...

NowCoder 311 https://www.nowcoder.com/practice/16409dd00ab24a408ddd0c46e49ddcf8?tpId=196&tqId=40267&rp=1&sourceUrl=%2Fexam%2Foj%3FtopicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=%E5%9C%86%E7%8E%AF 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ​ 问题分析 ​：圆环有 10 个点（0 到 9），从点 0 出发，每次移动可以到相邻的点（顺时针或逆时针）。要求恰好 n 步后回到点 0 的方法数。 动态规划设置 ​：使用一个数组 curr 来保存当前步数下到达每个点的方案数。初始时，curr[0] = 1，表示 0 步时在原点。 ​ 状态转移 ​：对于每一步，计算下一步到达每个点的方案数。每个点可以从其相邻的两个点转移过来，即 next[j] = curr[left] + curr[right]，其中 left 和 right 是 j 的相邻点。 模数处理 ​：由于结果可能非常大，每次加法后对 MOD 取模。 结果提取 ​：经过 n 步后，curr[0]即为回到原点的方法数。 ...

LCR 126 https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ ...

LCR 121 https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 时间复杂度：O(m + n) 空间复杂度：O(1) ...

LeetCode 45 https://leetcode.cn/problems/jump-game-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 不是在无路可走的那个位置造桥，而是当发现无路可走的时候，时光倒流到能跳到最远点的那个位置造桥。换句话说，在无路可走之前，我们只是在默默地收集信息，没有实际造桥。当发现无路可走的时候，才从收集到的信息中，选择最远点造桥。所建造的这座桥的左端点（起跳位置）在我们当前走的这座桥的中间，而不是桥的末尾。 时间复杂度：O(n)。其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...