LeetCode Hot 100 题解 · 技巧篇

LeetCode Hot 100 题解 · 技巧篇本专题收录 LeetCode Hot 100 中所有 技巧篇 相关题目。每道题提供最直接、最容易理解的解题思路包含详细注释的代码实现方便笔试和面试复习。 目录题号题目难度核心思路136136.只出现一次的数字简单除了一个数只出现一次其余都出现两次那我们想的就是怎么把成对的抵消掉剩那个单独的。异或刚好满足a ^ a 0、a ^ 0 a把所有数依次异或起来成对的全抵消成 0最后剩下的就是只出现一次的那个数。169169.多数元素中等要找出现次数超过n/2的元素。既然它比一半还多那思路就是抵消选一个候选遇到相同的1、不同的-1cnt归零就换候选遍历完剩下的必然是多数元素这就是摩尔投票法。7575.颜色分类中等只有 0、1、2 三种数要原地排序经典荷兰国旗问题三指针搞定l维护 0 的右边界、r维护 2 的左边界、i扫描遇到 0 换到l那边、遇到 2 换到r那边、遇到 1 直接跳过关键是和r换来的数还没看过i不能前进。3131.下一个排列中等找字典序里刚好比当前大的最小排列。从右往左找第一个nums[i] nums[i1]的i说明i后面这段是降序、已是局部最大再从右往左找第一个大于nums[i]的j交换i、j然后把i后面反转成升序若找不到i说明整个数组已是最大排列直接整体反转。287287.寻找重复数中等n1个数范围[1,n]有且只有一个重复又限制不能改数组、空间O(1)。把nums[i]看成指针i - nums[i]由于值域和下标都在[0,n]重复数必然导致链表成环那就用 Floyd 快慢指针找环入口入口就是重复数。136.只出现一次的数字题目链接136.只出现一次的数字题目描述给你一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。要求线性时间、常数空间。思路一异或把成对的数抵消为 0剩下的就是答案核心思想想把成对的数抵消掉只留那个单独的异或运算刚好满足这个性质a ^ a 0、a ^ 0 a并且满足交换律和结合律。所以把数组里所有数依次异或起来出现两次的互相抵消为 0最后的结果就是只出现一次的那个数。时间复杂度O ( n ) O(n)O(n)其中 n 为数组长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicintsingleNumber(int[]nums){intans0;// 0 ^ a a所以累加异或从 0 开始for(intnum:nums)// 遍历 nums 执行异或运算ans^num;// 成对的抵消为 0最后只剩出现一次的那个returnans;// 返回出现一次的数字 ans}}思路二哈希计数核心思想遍历nums把所有数字的出现次数统计在哈希表中最后查询哈希表次数为1的就是所要找的数时间复杂度O ( n ) O(n)O(n)其中 n 为数组长度。空间复杂度O ( n ) O(n)O(n)。169.多数元素题目链接169.多数元素题目描述给你一个大小为n的数组找出其中出现次数超过n/2的元素多数元素。题目保证多数元素一定存在。思路一摩尔投票法候选 计数靠抵消把多数元素逼出来核心思想多数元素数量超过一半所以它和别的元素一一抵消最后一定还有剩——这就是摩尔投票法的本质。维护候选ans和计数score遇到等于ans的就score不等于就score--score减到 0 就把ans换成当前数。遍历一遍后ans就是多数元素。时间复杂度O ( n ) O(n)O(n)其中 n 为数组长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicintmajorityElement(int[]nums){/* * 摩尔投票遇到相同的就加票遇到不同的就抵消票数为 0 就换候选人 */intscore0,ans-1;// score表示当前票数净票数ans表示候选人for(intnum:nums){if(score0){// 票数耗尽换候选人ansnum;}scorenumans?1:-1;// 相同就加票不同就就抵消}returnans;// 多数元素票数过半抵消到最后必为它}}75.颜色分类题目链接75.颜色分类题目描述给你一个只包含 0、1、2 三种数的数组分别代表红、白、蓝。要你原地排序使相同颜色相邻且按 0、1、2 顺序排列。思路一三指针 / 荷兰国旗l 放 0、r 放 2、i 扫中间核心思想经典荷兰国旗问题三指针l指向已排好的 0 的右边界下一个放 0 的位置r指向已排好的 2 的左边界下一个放 2 的位置i从左往右扫描。扫到nums[i] 0和l交换l、i。因为l il位置的元素早被i扫过了换过来的数一定是 1 或已处理过的可以放心前进。扫到nums[i] 2和r交换r--但i不动。因为r位置的元素还没被i扫到换过来的可能是 0/1/2 任意一个要原地再看一次。扫到nums[i] 1本就该在中间直接i。时间复杂度O ( n ) O(n)O(n)其中 n 为数组长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicvoidsortColors(int[]nums){intl0,rnums.length-1,i0;while(ir){// r 右边已是排好的 2i 不能越过 rif(nums[i]0){swap(nums,i,l);// 换到左边换来的 nums[l] 已被扫过i 前进}elseif(nums[i]2){swap(nums,i,r--);// 换到右边换来的 nums[r] 还没看过i 不动再看一次}else{i;// nums[i] 1本就该在中间跳过}}}voidswap(int[]a,intx,inty){intta[x];a[x]a[y];a[y]t;}}思路二化1为2核心思想其实就是吸取283.移动零这道题双指针的做法这个题实现了维护一个循环不变量最终让数组分为两部分0区域|非零区域从而在这个题那就可以代入到此题这种思路之中无非是在该题的基础上又需要把非零区域再分成1区域2区域。将数组分为0区域非0区域将非0区域分为1区域2区域时间复杂度O ( n ) O(n)O(n)其中 n 为数组长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicvoidsortColors(int[]nums){intnnums.length;intptr0;// 不变量保证ptr左边都是0// 1. 将数组分为0区域非0区域for(inti0;in;i){if(nums[i]0){// 只要是0 就进行交换inttmpnums[i];nums[i]nums[ptr];nums[ptr]tmp;}}// 此时pt不变量含义保证[旧ptr,新pt) 都是1for(intiptr;in;i){if(nums[i]1){// 只要是1 就进行交换inttmpnums[i];nums[i]nums[ptr];nums[ptr]tmp;}}}}31.下一个排列题目链接31.下一个排列题目描述给你一个整数数组的一个排列找出它的下一个排列字典序中刚好比它大的最小排列原地修改。如果它已经是最大排列就改成升序最小排列。思路一两次从后往前找 反转找升序对、换稍大的数、后缀转升序核心思想从后向前查找第一个相邻升序的元素对(r,r1)满足nums[r] nums[r1]此时[r1,end)必然是降序。在(r,end)从后向前查找第一个满足nums[k] nums[r]的k。将nums[r]与nums[k]交换可以断定这时[r1,end)必然是降序逆置 [r1,end)使其升序如果在步骤 1 找不到符合的相邻元素对说明当前 [begin,end) 为一个降序顺序则直接跳到步骤 4 【也就完成了最大的排列-》最小的排列的转换】时间复杂度O ( n ) O(n)O(n)其中 n 为数组长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicvoidnextPermutation(int[]nums){intnnums.length;// 1. 从后往前找相邻升序对[r,r1]intrn-2;while(r0){if(nums[r]nums[r1]){break;}--r;}// 此时找到了相邻升序对[r,r1]// 2. 从后往前找第一次大于nums[r]的数nums[k]if(r!-1){intk;for(kn-1;krnums[k]nums[r];--k){}// 从右到左找到第一个大于nums[r]的数// 3. 调换 nums[r], nums[k]inttmpnums[r];nums[r]nums[k];nums[k]tmp;}// 4. 接下来将[r1,n-1]按升序排列Arrays.sort(nums,r1,n);}}287.寻找重复数题目链接287.寻找重复数题目描述给你一个长度为n1的数组元素都在[1, n]范围内只有一个数重复了可能重复多次。找出这个重复数。要求不能修改数组、额外空间O(1)。思路一快慢指针 / Floyd 判圈把数组当链表环入口即重复数核心思想把nums[i]当成指针i - nums[i]数组就变成一条隐式链表。下标范围[0, n]、值域[1, n]所以指针不会越界一定一直在数组里转。有重复数t意味着至少有两个位置i, j都指向t即nums[i] nums[j] t也就是有两个不同的入边指向同一个节点链表必然成环且环入口就是重复数t。用Floyd 判圈法快慢指针先找相遇点再让一个指针回到起点、两个同步走第二次相遇即为环入口。时间复杂度O ( n ) O(n)O(n)其中 n 为数组长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicintfindDuplicate(int[]nums){// 把 nums[i] 当作指针 i - nums[i]数组变成隐式链表intslow0,fast0;do{slownums[slow];// 慢指针走一步fastnums[nums[fast]];// 快指针走两步}while(slow!fast);// 相遇后一个从起点、一个从相遇点同步走再次相遇处即环入口重复数slow0;while(slow!fast){slownums[slow];fastnums[fast];}returnslow;}}思路二二分核心思想找一条关键线索计算数组中mid的元素数量cnt若cntmid说明mid左边的数都不是说明所求数字在(mid,r)若cntmid说明所求数字在(l,mid)最后相当于我们维护了循环不变量(l,r)为审视区间,l]满足cntmid[r,)满足cntmid最后l1r而我们要找的数字就是cntmid的第一个数。时间复杂度O ( n l o g n ) O(nlogn)O(nlogn)其中 n 为数组长度。空间复杂度O ( 1 ) O(1)O(1)。classSolution{publicintfindDuplicate(int[]nums){// 你要用哈希表那肯定就是O(n) O(n)// 用二分的话那就是O(logn) O(1)// 1.为啥能用二分// 考虑单调性若 mid不是则mid-1也不是,mid1也不是// 怎么证明不是看mid的计数如果mid那说明答案在里面// 否则说明答案不在里面// 定义二段性 左边全是mid的右边全是mid的 那就应该返回l// 左边全是mid的右边全是mid的那就应该返回r// 2.check怎么写右边的全是的个数左边的全是的个数// 3.边界// 一开始理解错意思了人家不一定只重复一次Arrays.sort(nums);intl0,rnums.length;// 答案在[1,n]之间while(l1r){intmidl(r-l)/2;intcnt0;for(intnum:nums){if(nummid){cnt;}}if(cntmid){// 说明必有重复rmid;}else{lmid;}}returnr;// 我这里最终返回的是编号的第一个位置}}思路三哈希计数核心思想开桶记录每个数字是否出现过遍历数组如果桶内已出现过该数直接返回结果若遍历过程中都没有return那就说明没有重复的数字。时间复杂度O ( n ) O(n)O(n)其中 n 为数组长度。空间复杂度O ( n ) O(n)O(n)。classSolution{staticbooleanvis[]newboolean[100001];publicintfindDuplicate(int[]nums){Arrays.fill(vis,false);for(intnum:nums){if(vis[num]){returnnum;}vis[num]true;}return-1;}}面试总结技巧篇的共性是用极简的位运算 / 指针操作换掉额外空间。136 用异或的抵消性质、169 用摩尔投票的抵消、75 用三指针原地划分、31 用两遍扫描 反转、287 用 Floyd 判圈——核心都是把O(n)的空间压到O(1)靠抵消或成环这两个性质破题。