1. 为什么LeetCode热题100的技巧篇值得深挖作为算法面试的黄金标准LeetCode热题100中的技巧篇题目往往隐藏着算法设计的精髓。这些题目看似简单却蕴含着巧妙的解题思路能够帮助我们突破常规思维局限。以只出现一次的数字为例大多数人第一反应是用哈希表统计频率但最优解其实只需要一行位运算代码——这种思维跃迁正是技巧篇的价值所在。我在面试候选人和带队刷题时发现掌握这些技巧性解法的人往往在系统设计环节也表现更出色。因为他们已经养成了寻找问题本质特征的思维习惯而不仅仅是套用模板。比如多数元素问题摩尔投票法的精妙之处在于用O(1)空间解决问题这种优化思路同样适用于分布式系统中的Leader选举场景。2. 位运算的魔法只出现一次的数字2.1 问题描述与常规解法给定一个非空整数数组其中某个元素只出现一次其余每个元素均出现两次。找出那个只出现一次的元素。最直观的解法是使用哈希表统计元素出现次数def singleNumber(nums): freq {} for num in nums: freq[num] freq.get(num, 0) 1 for num, count in freq.items(): if count 1: return num这种方法时间复杂度O(n)空间复杂度O(n)。面试官接下来必然会问能否用O(1)空间解决2.2 位运算的降维打击关键在于发现出现两次这个条件的特殊性质——两个相同数字的异或结果为0。因此只需要将所有数字异或起来最终结果就是只出现一次的数字def singleNumber(nums): res 0 for num in nums: res ^ num return res实战经验这个解法对数字出现的顺序没有要求因为异或满足交换律和结合律。我在实际面试中遇到过这个问题的变种——当其他数字出现三次时怎么办这时需要设计更复杂的位操作状态机。3. 摩尔投票法的精妙多数元素问题3.1 问题定义与常规思路找出数组中出现次数超过⌊n/2⌋的元素。直接统计频率的方法虽然可行但需要O(n)空间。排序后取中位数的方法需要O(nlogn)时间。3.2 摩尔投票法的核心思想维护一个候选人和计数器遍历数组时相同数字则计数器1不同数字则计数器-1计数器归零时更换候选人def majorityElement(nums): candidate None count 0 for num in nums: if count 0: candidate num count (1 if num candidate else -1) return candidate避坑指南这个方法的前提是多数元素确实存在。实际工程中应该增加验证步骤比如再遍历一次统计该候选人的真实出现次数。我在处理实时投票系统时曾因此踩过坑——当没有绝对多数时算法会返回错误结果。4. 荷兰国旗问题颜色分类的原地排序4.1 问题背景给定包含红、白、蓝三种颜色的数组要求原地排序红-白-蓝。常规排序算法不满足原地要求而计数排序需要两次遍历。4.2 三指针分区法维护三个指针left、curr、rightcurr遍历数组遇到0红就与left交换left和curr都右移遇到1白就curr右移遇到2蓝就与right交换right左移def sortColors(nums): left, curr, right 0, 0, len(nums)-1 while curr right: if nums[curr] 0: nums[left], nums[curr] nums[curr], nums[left] left 1 curr 1 elif nums[curr] 2: nums[curr], nums[right] nums[right], nums[curr] right - 1 else: curr 1调试技巧这个算法的边界条件很容易出错。建议在纸上模拟[2,0,1]这样的边缘用例。我在第一次实现时忘记处理currright的终止条件导致数组越界。5. 排列的数学规律下一个排列5.1 字典序排列的定义给定数字序列找出其字典序中下一个更大的排列。例如[1,2,3]的下一个是[1,3,2]。5.2 四步解决法从后向前找第一个下降点inums[i] nums[i1]在i右侧找最小的大于nums[i]的数nums[j]交换nums[i]和nums[j]反转i1到末尾的部分def nextPermutation(nums): n len(nums) # 第一步找下降点 i n - 2 while i 0 and nums[i] nums[i1]: i - 1 if i 0: # 第二步找交换点 j n - 1 while j 0 and nums[j] nums[i]: j - 1 # 第三步交换 nums[i], nums[j] nums[j], nums[i] # 第四步反转 left, right i1, n-1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1优化心得这个算法的时间复杂度是O(n)但实际编码时容易在第二步混淆大于和小于的条件。我建议用[1,3,2]作为测试用例逐步验证每步操作。6. 环形链表检测思想寻找重复数6.1 问题转化给定包含n1个1到n之间整数的数组必有至少一个重复数。要求找出这个重复数不能修改数组且只能用O(1)空间。6.2 Floyd判圈算法应用将数组视为链表i→nums[i]重复数意味着存在环的入口快慢指针找到相遇点新指针从头出发与慢指针同步移动直到相遇def findDuplicate(nums): # 阶段一找相遇点 slow fast nums[0] while True: slow nums[slow] fast nums[nums[fast]] if slow fast: break # 阶段二找入口 ptr nums[0] while ptr ! slow: ptr nums[ptr] slow nums[slow] return ptr扩展思考这个方法实际上找到了所有重复数中的某一个。如果需要找出所有重复数可以参考位图法的变种。我在处理数据库索引优化时曾应用过类似思路来检测重复键。7. 技巧篇的通用解题框架通过分析这五个典型问题可以总结出技巧性算法的通用解题模式问题特征提取寻找题目中的特殊约束条件如出现两次、多数、原地等数学性质挖掘异或的消去律、排列的字典序性质等经典算法迁移将链表检测算法应用于数组场景边界条件验证特别是涉及指针移动和交换的操作在实际面试中当遇到陌生题目时我会建议按照以下步骤思考先考虑暴力解法分析暴力解法中哪些信息是被浪费的寻找问题中的不变量或特殊性质尝试用数学方法或经典算法框架进行优化例如在颜色分类问题中我们浪费了只有三种颜色这个关键信息在多数元素问题中我们浪费了出现次数超过一半这个强约束条件。发现并利用这些隐藏信息正是算法设计的艺术所在。 
长河君 · 2026/11/3 11:28:27 · 阅读 1.2k LeetCode热题100技巧篇：位运算与算法优化实战
1. 为什么LeetCode热题100的技巧篇值得深挖作为算法面试的黄金标准LeetCode热题100中的技巧篇题目往往隐藏着算法设计的精髓。这些题目看似简单却蕴含着巧妙的解题思路能够帮助我们突破常规思维局限。以只出现一次的数字为例大多数人第一反应是用哈希表统计频率但最优解其实只需要一行位运算代码——这种思维跃迁正是技巧篇的价值所在。我在面试候选人和带队刷题时发现掌握这些技巧性解法的人往往在系统设计环节也表现更出色。因为他们已经养成了寻找问题本质特征的思维习惯而不仅仅是套用模板。比如多数元素问题摩尔投票法的精妙之处在于用O(1)空间解决问题这种优化思路同样适用于分布式系统中的Leader选举场景。2. 位运算的魔法只出现一次的数字2.1 问题描述与常规解法给定一个非空整数数组其中某个元素只出现一次其余每个元素均出现两次。找出那个只出现一次的元素。最直观的解法是使用哈希表统计元素出现次数def singleNumber(nums): freq {} for num in nums: freq[num] freq.get(num, 0) 1 for num, count in freq.items(): if count 1: return num这种方法时间复杂度O(n)空间复杂度O(n)。面试官接下来必然会问能否用O(1)空间解决2.2 位运算的降维打击关键在于发现出现两次这个条件的特殊性质——两个相同数字的异或结果为0。因此只需要将所有数字异或起来最终结果就是只出现一次的数字def singleNumber(nums): res 0 for num in nums: res ^ num return res实战经验这个解法对数字出现的顺序没有要求因为异或满足交换律和结合律。我在实际面试中遇到过这个问题的变种——当其他数字出现三次时怎么办这时需要设计更复杂的位操作状态机。3. 摩尔投票法的精妙多数元素问题3.1 问题定义与常规思路找出数组中出现次数超过⌊n/2⌋的元素。直接统计频率的方法虽然可行但需要O(n)空间。排序后取中位数的方法需要O(nlogn)时间。3.2 摩尔投票法的核心思想维护一个候选人和计数器遍历数组时相同数字则计数器1不同数字则计数器-1计数器归零时更换候选人def majorityElement(nums): candidate None count 0 for num in nums: if count 0: candidate num count (1 if num candidate else -1) return candidate避坑指南这个方法的前提是多数元素确实存在。实际工程中应该增加验证步骤比如再遍历一次统计该候选人的真实出现次数。我在处理实时投票系统时曾因此踩过坑——当没有绝对多数时算法会返回错误结果。4. 荷兰国旗问题颜色分类的原地排序4.1 问题背景给定包含红、白、蓝三种颜色的数组要求原地排序红-白-蓝。常规排序算法不满足原地要求而计数排序需要两次遍历。4.2 三指针分区法维护三个指针left、curr、rightcurr遍历数组遇到0红就与left交换left和curr都右移遇到1白就curr右移遇到2蓝就与right交换right左移def sortColors(nums): left, curr, right 0, 0, len(nums)-1 while curr right: if nums[curr] 0: nums[left], nums[curr] nums[curr], nums[left] left 1 curr 1 elif nums[curr] 2: nums[curr], nums[right] nums[right], nums[curr] right - 1 else: curr 1调试技巧这个算法的边界条件很容易出错。建议在纸上模拟[2,0,1]这样的边缘用例。我在第一次实现时忘记处理currright的终止条件导致数组越界。5. 排列的数学规律下一个排列5.1 字典序排列的定义给定数字序列找出其字典序中下一个更大的排列。例如[1,2,3]的下一个是[1,3,2]。5.2 四步解决法从后向前找第一个下降点inums[i] nums[i1]在i右侧找最小的大于nums[i]的数nums[j]交换nums[i]和nums[j]反转i1到末尾的部分def nextPermutation(nums): n len(nums) # 第一步找下降点 i n - 2 while i 0 and nums[i] nums[i1]: i - 1 if i 0: # 第二步找交换点 j n - 1 while j 0 and nums[j] nums[i]: j - 1 # 第三步交换 nums[i], nums[j] nums[j], nums[i] # 第四步反转 left, right i1, n-1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1优化心得这个算法的时间复杂度是O(n)但实际编码时容易在第二步混淆大于和小于的条件。我建议用[1,3,2]作为测试用例逐步验证每步操作。6. 环形链表检测思想寻找重复数6.1 问题转化给定包含n1个1到n之间整数的数组必有至少一个重复数。要求找出这个重复数不能修改数组且只能用O(1)空间。6.2 Floyd判圈算法应用将数组视为链表i→nums[i]重复数意味着存在环的入口快慢指针找到相遇点新指针从头出发与慢指针同步移动直到相遇def findDuplicate(nums): # 阶段一找相遇点 slow fast nums[0] while True: slow nums[slow] fast nums[nums[fast]] if slow fast: break # 阶段二找入口 ptr nums[0] while ptr ! slow: ptr nums[ptr] slow nums[slow] return ptr扩展思考这个方法实际上找到了所有重复数中的某一个。如果需要找出所有重复数可以参考位图法的变种。我在处理数据库索引优化时曾应用过类似思路来检测重复键。7. 技巧篇的通用解题框架通过分析这五个典型问题可以总结出技巧性算法的通用解题模式问题特征提取寻找题目中的特殊约束条件如出现两次、多数、原地等数学性质挖掘异或的消去律、排列的字典序性质等经典算法迁移将链表检测算法应用于数组场景边界条件验证特别是涉及指针移动和交换的操作在实际面试中当遇到陌生题目时我会建议按照以下步骤思考先考虑暴力解法分析暴力解法中哪些信息是被浪费的寻找问题中的不变量或特殊性质尝试用数学方法或经典算法框架进行优化例如在颜色分类问题中我们浪费了只有三种颜色这个关键信息在多数元素问题中我们浪费了出现次数超过一半这个强约束条件。发现并利用这些隐藏信息正是算法设计的艺术所在。