1. 算法刷题实战Top Interview 150第二天精解今天我们来拆解LeetCode高频面试题集中的三道经典题目26. Remove Duplicates from Sorted Array删除有序数组中的重复项、169. Majority Element多数元素以及141. Linked List Cycle环形链表。这三道题分别代表了数组操作、数学技巧和链表处理的典型解法也是面试官最常考察的算法基本功。提示建议先自行尝试解题再看解析效果更佳。本文代码示例均使用Python但会解释通用解法思路其他语言可类似实现。2. 26. 删除有序数组中的重复项2.1 问题重述给定一个升序排列的数组nums你需要原地删除重复出现的元素使每个元素只出现一次并返回新数组的长度。要求空间复杂度为O(1)。示例 输入nums [0,0,1,1,1,2,2,3,3,4] 输出5, nums [0,1,2,3,4,...]2.2 双指针解法详解这是典型的双指针快慢指针应用场景。慢指针slow标记当前唯一元素的末尾位置快指针fast遍历整个数组def removeDuplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1操作原理初始化slow0fast从1开始遍历当nums[fast] ≠ nums[slow]时说明遇到新元素将slow右移一位并用nums[fast]更新该位置的值最终slow1就是不重复元素的数量2.3 边界情况处理空数组直接返回0全相同元素slow始终为0返回1已去重数组fast每次都会触发更新相当于复制原数组注意题目不要求保留超出新长度部分的元素但实际测试时建议保持原值避免某些在线判题系统检查整个数组。3. 169. 多数元素3.1 问题定义给定大小为n的数组找出出现次数超过⌊n/2⌋的元素假设总是存在。要求时间复杂度O(n)空间复杂度O(1)。示例 输入[2,2,1,1,1,2,2] 输出23.2 Boyer-Moore投票算法最优雅的解法是Boyer-Moore算法只需一次遍历def majorityElement(nums): count 0 candidate None for num in nums: if count 0: candidate num count (1 if num candidate else -1) return candidate算法本质把多数元素当作国家其他元素当作反对票遇到相同元素时国家实力1不同时-1实力归零时更换当前国家最终剩下的必然是真正的多数国家3.3 其他解法对比方法时间复杂度空间复杂度适用场景哈希统计O(n)O(n)通用解法排序取中O(nlogn)O(1)允许修改原数组分治法O(nlogn)O(logn)练习递归思维位运算O(nlogC)O(1)元素范围已知实操技巧面试时建议先提出哈希解法再优化到投票算法展示思维过程。4. 141. 环形链表4.1 问题描述给定链表头节点head判断链表中是否有环。要求空间复杂度O(1)。示例 输入head [3,2,0,-4], pos 1-4指向2 输出true4.2 快慢指针解法经典的龟兔赛跑算法def hasCycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False数学原理慢指针每次走1步快指针走2步若有环快指针最终会从后方追上慢指针相差整数倍环长若无环快指针会先到达终点4.3 常见变种问题找出环的入口节点相遇后将慢指针移回起点两个指针同速前进再次相遇点即为入口计算环的长度保持快指针不动慢指针继续走再次相遇时走过的步数即为环长判断环的位置结合前两个问题的解法5. 综合应用与面试技巧5.1 三道题的共同点都使用了双指针技巧同向/快慢都要求O(1)空间复杂度都是基础但高频的面试题5.2 面试应答策略先明确问题要求和边界条件给出暴力解法分析复杂度逐步优化解释每个优化点的考虑最后讨论可能的变种问题5.3 刷题建议同类题目集中练习如连续做所有双指针题每道题至少实现三种解法整理错题本记录错误原因定期复习已AC的题目我在实际面试辅导中发现很多候选人能写出正确代码但无法解释清楚算法原理。建议在练习时给自己录音讲解解题过程这对面试表达很有帮助。对于环形链表问题有个实用debug技巧在纸上画出前10步两个指针的位置能直观理解相遇原理。当遇到难以理解的算法时这种可视化方法往往比死记硬背更有效。