算法知识-双指针

一.双指针设置两个指针的技巧说法很宽泛。(1)有时候所谓双指针技巧就是单纯代码过程用双指针的形式表达出来而已没有单调性(贪心)方面的考虑(例题1例题2(2)有时候双指针技巧包含单调性(贪心)方面的考虑牵扯到可能性的取舍对于分析能力的要求会变高其实是先有思考和优化然后代码变成了双指针的形式(3)所以双指针名词并不重要分析题目单调性(贪心)方面的特征这个能力才重要常见双指针类型同向双指针快慢双指针从两头往中间的双指针其他二.例题922. 按奇偶排序数组 II - 力扣LeetCode我们安排两个指针一个是奇数指针从下标1出发一个是偶数指针从下标0出发我们盯着数组最后一个位置不断看最后一个位置是奇数还是偶数如果是奇数就和奇数下标交换一下之后odd2,如果是偶数就和偶数下标交换一下之后even2循环结束条件是even或者odd越界说明有奇数/偶数位置已经安排妥当那么整体就已经安排妥当。总结以数组最后一位去发货不断让奇数位和偶数位去成长谁先成长越界就说明谁已经安排妥当class Solution { public: vectorint sortArrayByParityII(vectorint nums) { int nnums.size(); for(int even0,odd1;evennoddn;){ if(nums[n-1]1){ swap(nums[n-1],nums[odd]); odd2; }else{ swap(nums[n-1],nums[even]); even2; } } return nums; } };287. 寻找重复数 - 力扣LeetCode我们可以把数组想象成链表的形式那么i指向nums[i],如果有重复的数字那么链表一定成环可以使用快慢指针补充快慢指针(1)快指针一次跳两步慢指针一次跳一步(2)快慢指针相遇(3)快指针回到起点慢指针留在原处每人一次跳一步直到相遇就是环的入口class Solution { public: int findDuplicate(vectorint nums) { int nnums.size(); int slownums[0]; int fastnums[nums[0]]; while(slow!fast){ slownums[slow]; fastnums[nums[fast]]; } fast0; while(fast!slow){ fastnums[fast]; slownums[slow]; } return slow; } };42. 接雨水 - 力扣LeetCode首先我们分析题目对于任意一个位置i它所能承接的雨水由于木桶的短板效应所以水的高度加上自身高度不能超过左右两侧最大值的最小值即能承接min(lMax,rMax)-a[i]但是由于i位置可能比左右两侧最大值都高会计算出负数所以i位置能承接的雨水应该是max(min(lMax,rMax)-a[i],0)之后我们通过前缀最大值分别记录每个位置左侧和右侧的最大值class Solution { public: int trap(vectorint height) { int n height.size(); vectorint lMax(n); vectorint rMax(n); lMax[0] height[0]; for (int i 1; i n; i) { lMax[i] max(lMax[i-1], height[i]); } rMax[n - 1] height[n - 1]; for (int i n -2; i 1; i--) { rMax[i] max(rMax[i1], height[i]); } int ans 0; for (int i 1; i n-1; i) { ans max((min(lMax[i], rMax[i]) - height[i]), 0); } return ans; } };双指针优化我们可以设置两个指针lr从1和n-2出发之后维护一个lMax和一个rMax如果lMaxrMax,l左侧为lMax,而l右侧应该rMax那么l位置的短板一定是lMax否则lMaxrMax,r右侧为真实的rMax,而r左侧应该lMax,所以r位置的短板应该是rMax左指针l非严格单调递增仅右移、不回退右指针r非严格单调递减仅左移、不回退int trap(vectorint height) { int n height.size(); int l1,rn-2,lMaxheight[0],rMaxheight[n-1]; int ans0; while(lr){ if(lMaxrMax){ ansmax(lMax-height[l],0); lMaxmax(lMax,height[l]); }else{ ansmax(rMax-height[r],0); rMaxmax(rMax,height[r--]); } } return ans; }881. 救生艇 - 力扣LeetCode我们首先对原数组排序之后设置两个指针l,r分别在开头和结尾(1)a[l]a[r]limitl和r一船因为对于l来说已经是最值的选择了lr--(2)a[l]a[r]limit那么r自己一船因为l右侧都是比l大的不会有能和r一船的了r--class Solution { public: int numRescueBoats(vectorint people, int limit) { sort(people.begin(),people.end()); int l0,rpeople.size()-1; int ans0; int sum0; while(lr){ sumlr?people[l]:people[l]people[r]; if(sumlimit){ l; r--; }else{ r--; } ans; } return ans; } };11. 盛最多水的容器 - 力扣LeetCode题目分析设置两个指针l,r分别从开头和结尾出发如果h[l]h[r]以h[l]为开头的最好的情况就是现在当前边长最长并且以h[l]为开头一定要h[l]。所以更新一下答案l反之如果h[l]h[r],以h[r]作为结尾最好情况就是现在以h[r]作为结尾一定要h[r]并且现在边长最大所以就是谁小就以谁作边长并且移动谁class Solution { public: int maxArea(vectorint height) { int res 0; int l 0; int r height.size() - 1; while (l r) { int area (r - l) * min(height[l], height[r]); res max(res, area); if (height[l] height[r]) { l; } else { r--; } } return res; } };475. 供暖器 - 力扣LeetCode题目分析本道题目比较简单先对两个数组进行排序就是一个指针l1从房屋出发一个指针l2从供暖器出发之后我们循环比较l1房屋到l21供暖器的距离是否小于等于l1到l2的距离呢是的话说明l21更好,l2之后当l2移动到最后说明已经没有更大的供暖期进行选择了我们只能选择l2了。注意如果l2距房屋距离与l1距房屋距离相等l2一定要移动因为供暖器数组可能存在两个相等的值如果不移动将会永远无法移动l2导致后续计算错误class Solution { public: int findRadius(vectorint houses, vectorint heaters) { sort(houses.begin(),houses.end()); sort(heaters.begin(),heaters.end()); int nhouses.size(),mheaters.size(); int l10,l20; int diff10,diff20; int ans0; for(int l10;l1n;l1){ if(l2m-1){ ansmax(ans,abs(houses[l1]-heaters[l2])); continue; } while(l2m-1abs(houses[l1]-heaters[l21]) abs(houses[l1]-heaters[l2])){ l2; } ansmax(ans,abs(houses[l1]-heaters[l2])); } return ans; } };41. 缺失的第一个正数 - 力扣LeetCode该题目比较难想。题目分析如果正常的话就应该是a[l]l1,那么一开始我们假设每一个位置都是这样的那么我们能收集1~n都会存在所以我们一开始有一个左指针l从0出发代表l左侧是放好的r从下标n出发代表垃圾区域有一下几种情况(1)a[l]l1正常放置l(2)垃圾数据:a[l]r只能收集1~r,大于r一定是垃圾a[l]l,小于等于l在l左侧已经收集好了垃圾a[a[l]-1]a[l]如果a[l]在l1到r之间需要把a[l]放到对应的位置上但是发现该位置已经有相同的数字了垃圾把a[l]交换到垃圾区swap(nums[l],nums[--r])(3)不是垃圾也不是该位置的数字需要给他交换到它的位置上去swap(nums[l],nums[nums[l]-1])class Solution { public: int firstMissingPositive(vectorint nums) { int l0,rnums.size(); while(lr){ if(nums[l]l1){ l; }else if(nums[l]r||nums[l]l||nums[nums[l]-1]nums[l]){ swap(nums[l],nums[--r]); }else{ swap(nums[l],nums[nums[l]-1]); } } return l1; } };