力扣Hot100：位运算与双指针技巧精解

1. 项目概述最近在整理力扣Hot100系列的第18组题目时我发现这组题目特别有意思——它们都涉及到一些巧妙的解题技巧而不是单纯的暴力解法。作为一名Java开发者我花了些时间深入研究这些题目总结出了一些实用的解题思路和代码实现。这组题目包括只出现一次的数字Single Number多数元素Majority Element颜色分类Sort Colors下一个排列Next Permutation寻找重复数Find the Duplicate Number这些题目看似简单但要想在O(n)时间复杂度和O(1)空间复杂度下解决就需要一些巧妙的技巧。下面我将逐一分析每道题目的解题思路和Java实现。2. 核心技巧解析2.1 只出现一次的数字这道题要求找出数组中唯一一个只出现一次的数字其他数字都出现两次。最直观的解法是用哈希表统计次数但这样空间复杂度是O(n)。位运算技巧 利用异或运算的性质a ^ a 0a ^ 0 a异或满足交换律和结合律因此我们可以将所有数字异或起来最终结果就是那个只出现一次的数字。public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; }注意这种方法只适用于其他数字都出现两次的情况。如果其他数字出现三次或更多次就需要其他方法了。2.2 多数元素这道题要求找出出现次数超过⌊n/2⌋的元素。同样哈希表统计是最直观的解法但需要O(n)空间。摩尔投票法 这是一个非常巧妙的算法可以在O(1)空间内解决问题初始化候选人和计数器遍历数组如果计数器为0选择当前元素作为候选人如果当前元素等于候选人计数器加1否则计数器减1最后的候选人就是多数元素public int majorityElement(int[] nums) { int count 0; Integer candidate null; for (int num : nums) { if (count 0) { candidate num; } count (num candidate) ? 1 : -1; } return candidate; }注意这个方法的前提是多数元素一定存在。如果可能不存在需要最后再验证一次。2.3 颜色分类这道题要求将只包含0、1、2的数组原地排序。不能使用排序函数且要一趟扫描完成。三指针法left指针指向0的右边界right指针指向2的左边界curr指针用于遍历public void sortColors(int[] nums) { int left 0, right nums.length - 1; int curr 0; while (curr right) { if (nums[curr] 0) { swap(nums, left, curr); } else if (nums[curr] 2) { swap(nums, curr, right--); } else { curr; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }注意当nums[curr]2时curr不能自增因为交换过来的元素可能是0或1需要再次检查。2.4 下一个排列这道题要求找到给定数字序列的下一个更大的排列。如果没有更大的排列就返回最小的排列。算法步骤从后向前找第一个降序的位置i如果找到从后向前找第一个大于nums[i]的数nums[j]交换nums[i]和nums[j]反转i1到末尾的部分public void nextPermutation(int[] nums) { int i nums.length - 2; while (i 0 nums[i] nums[i 1]) { i--; } if (i 0) { int j nums.length - 1; while (j 0 nums[j] nums[i]) { j--; } swap(nums, i, j); } reverse(nums, i 1); } private void reverse(int[] nums, int start) { int i start, j nums.length - 1; while (i j) { swap(nums, i, j); i; j--; } }注意这个算法的时间复杂度是O(n)空间复杂度是O(1)非常高效。2.5 寻找重复数这道题给定一个包含n1个整数的数组数字在1到n之间有且只有一个重复的数字找出它。快慢指针法 将数组视为链表数组值表示下一个节点的索引。因为有重复数字所以链表一定有环。public int findDuplicate(int[] nums) { int slow nums[0]; int fast nums[0]; do { slow nums[slow]; fast nums[nums[fast]]; } while (slow ! fast); slow nums[0]; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; }注意这个方法修改了Floyd判圈算法非常巧妙。时间复杂度O(n)空间复杂度O(1)。3. 解题技巧总结3.1 位运算的妙用位运算在算法题中经常能带来意想不到的简洁解法。除了异或运算其他位运算也很有用与运算()判断奇偶、取特定位或运算(|)设置特定位非运算(~)取反左移()、右移()快速乘除23.2 双指针技巧双指针是解决数组/链表问题的利器常见模式有同向双指针快慢指针对向双指针从两端向中间移动分离双指针一个指针遍历一个指针记录位置3.3 原地算法当题目要求O(1)空间复杂度时考虑利用输入数据本身存储中间结果交换元素位置而不是使用额外空间使用位运算压缩信息3.4 数学思维很多算法题本质上是数学问题比如排列组合问题数论问题质数、公约数等几何问题概率问题培养数学思维能帮助发现更优解法。4. Java实现注意事项4.1 边界条件处理在实现这些算法时要特别注意边界条件空数组或单元素数组所有元素相同的情况最大值/最小值边界整数溢出问题4.2 代码优化技巧尽量减少不必要的变量使用位运算代替算术运算避免重复计算合理使用循环和递归4.3 测试用例设计好的测试用例应该包括常规情况边界情况极端情况特殊输入例如对于只出现一次的数字正常情况[2,2,1]边界情况[1]特殊情况[4,1,2,1,2]5. 常见错误与调试技巧5.1 位运算常见错误忘记初始化结果变量混淆位运算符优先级忽略整数溢出错误处理负数5.2 双指针常见错误指针移动条件错误边界处理不当循环终止条件错误指针越界5.3 调试技巧打印中间变量值使用小规模测试数据逐步验证算法步骤画图辅助理解6. 性能优化建议6.1 时间复杂度优化分析问题特性寻找数学规律使用更高效的数据结构减少不必要的计算利用问题约束条件6.2 空间复杂度优化原地修改输入数据重用变量使用位运算压缩信息避免创建不必要的数据结构6.3 Java特定优化使用基本类型而非包装类避免自动装箱/拆箱合理使用StringBuilder注意对象创建开销7. 扩展思考7.1 相关题目推荐只出现一次的数字II其他数字出现三次多数元素II找出所有出现超过⌊n/3⌋的元素荷兰国旗问题颜色分类的变种上一个排列寻找所有重复数7.2 实际应用场景位运算加密算法、压缩算法、位图处理摩尔投票大数据流中的频繁项挖掘双指针字符串处理、图像处理排列生成密码破解、组合优化7.3 进阶学习资源《算法导论》中的位运算和排列组合章节LeetCode上的类似题目计算机程序设计艺术中的相关算法在线算法竞赛平台的练习题8. 个人实战心得在实际刷题过程中我发现这些技巧类题目有几个共同特点表面简单但暗藏玄机乍一看可能觉得很简单但要达到最优解需要深入思考。数学思维是关键很多最优解法都基于数学原理而不仅仅是编程技巧。模式识别很重要一旦掌握了几种常见技巧类似题目就能快速识别并解决。边界条件容易出错即使算法正确边界条件处理不当也会导致失败。我建议在练习这类题目时先自己思考不要急于看答案理解而不仅是记住解法多做变种题目巩固理解记录自己的错误和心得最后这些技巧不仅在面试中有用在实际开发中遇到类似问题时也能帮助我们写出更高效的代码。