网站建设开发费会计分录,企业后缀邮箱申请,游戏网站开发实验报告,大量word发布wordpress双指针算法
常见的双指针有对撞指针#xff0c;快慢指针以及前后指针#xff08;这个前后指针是指两个指针都是从从一个方向出发#xff0c;去往另一个方法#xff0c;也可以认为是小学学习过的两车并行#xff0c;我也会叫做同向指针#xff09;#xff0c;在前后指针…双指针算法
常见的双指针有对撞指针快慢指针以及前后指针这个前后指针是指两个指针都是从从一个方向出发去往另一个方法也可以认为是小学学习过的两车并行我也会叫做同向指针在前后指针这里还有一个经典的算法叫做滑动窗口滑动窗口会在下一篇算法文章中提到
对撞指针可以叫做左右指针就是一个指针在最左端另一个指针在最右端然后两个指针开始向中间逼近。
快慢指针相信大家在链表的时候就已经学到过就是一个指针每次走一步这就是慢指针另一个指针每次走两步这是快指针。一般快慢指针是用来处理处理环形链表或数组。
前后指针在不涉及到滑动窗口的使用的时候我们一般会用于数组的分区。
如果大家学过排序想必对双指针应该十分了解正好在学习双指针算法的时候可以回顾一下排序内容。
题目实战
下面题目讨论的时间复杂度没有进行化简目的是让大家更好地感受算法对性能的优化。
移动零
https://leetcode.cn/problems/move-zeroes/description/ 解法前后指针 题目要求我们将数组前面的零移动到后面将非零的元素按照原本的相对位置存放到数组的前面。 这时候这个数组显而易见地被分成了两个部分一个是非零区域一个是零区域
我们可以使用前后指针法第一个指针从下标0开始遍历数组第二个指针初始值设置为-1当第一个指针遇到非零元素时第二个指针向后移动一步然后交换两个指针所对应的数组的元素否则第二个指针原地不动。 通过前后指针我们可以将数组分成上述的区域这就是为什么前后指针一般用于数组的分区。
class Solution {public void moveZeroes(int[] nums) {int len nums.length;int j -1;for(int i 0; i len; i) {if(nums[i] ! 0) {j;int tmp nums[i];nums[i] nums[j];nums[j] tmp;}}}
}如果可以使用额外的空间的话还是使用两个指针一个指针指向一个数组时间复杂度为O(2N)空间复杂度为O(N)但是直接使用双指针算法时间复杂度O(2N)空间复杂度为O(1) 快乐数
https://leetcode.cn/problems/happy-number/ 解法快慢指针 在快乐数的循环中我们知道循环最后的结果要么是无限循环要么是 1那无限循环是为什么
以 n 2 为例2 ^ 2 44 ^ 2 161 ^ 2 6 ^ 2 373 ^ 2 7 ^ 2 585 ^ 2 8 ^ 2 898 ^ 2 9 ^ 2 145, 1 ^ 2 4 ^ 2 5 ^ 2 424 ^ 2 2 ^ 2 202 ^ 2 0 2最后你会发现这个数它又回去了也就是意味着这个循环形成了一个环
最后循环的结果还有一种可能就是出现1如果出现 1 的时候我们不停止循环的话那么这个循环将会一直得到1这也是一个环。
相信大家到这里想到了使用快慢指针当两个指针相遇时如果指针对应的是1 的话那么就是快乐数否则就不是快乐数。
class Solution {public boolean isHappy(int n) {int slow n;int fast sum(sum(n));while(slow ! fast) {slow sum(slow);fast sum(sum(fast));}if(slow 1) {return true;} else {return false;}}private int sum(int n) {int sum 0;while(n ! 0) {sum (n % 10) * (n % 10);n / 10;}return sum;}
}盛最多水的容器
https://leetcode.cn/problems/container-with-most-water/description/ 解法对撞指针
分析题意数组的每一个元素是该下标的高而容器的底长为两个下标之间的差值题目要求我们找到容器的最大值这个数值等于 高 x 底长
我们使用对撞指针一个在最左端一个在最右端然后两个指针开始向中间遍历首先由于两个指针是向中间靠拢所以对应的宽度就会减少指针移动的目的是为了获取容器的最大值所以我们现在要思考指针如何移动
因为容器的高度是由最小的高度决定的所以这时候我们可以从两个指针获取到最小的元素我们让对应最小的高度的指针向中间移动看看能不能找到更大的高度以此来进行遍历然后通过 Math.max 这个函数就可以获取到最大值。
class Solution {public int maxArea(int[] height) {int left 0;int right height.length - 1;int maxV Math.min(height[left],height[right]) * (right - left);while(left right) {int index (height[left] height[right] ? right : left);if(index left) {left;} else {right--;}int tmp Math.min(height[left],height[right]) * (right - left);maxV Math.max(maxV,tmp);}return maxV; }
}这道题的对撞指针算法的时间复杂度为O(N) 性能十分地好
两数之和
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/ 解法排序 双指针
由于我们只要返回两个数两数之和为 target 即可。如果我们直接使用两个指针的话就是使用暴力枚举使用了两层循环实践复杂度为O(N^2)但是这里是算法篇目我们应该尽量优化我们的算法将算法的效率提高。
如果数组本身就是有序的话我们再这个基础上使用双指针就会好写很多因为就三种情况要么两数之和小于taregt 两数之和如果等于 tareget 的话直接返回即可如果两个数大于 target 。
也就是我们要处理指针的移动就是大于和小于的情况如果是大于的话我们可以将指针左移减小两数之和如果是小于的话可以将指针右移扩大两数之和那这就意味着我们要使用的是对撞指针。
class Solution {public int[] twoSum(int[] price, int target) {Arrays.sort(price);int left 0;int right price.length - 1;while(left right) {if(price[left] price[right] target) {break;} else if(price[left] price[right] target) {right--;} else {left;}}int[] ans {price[left],price[right]};return ans;}
}时间复杂度分析使用Arrays.sort 这个底层是快速排序时间复杂度为O(N * logN)对撞指针时间复杂度为 O(N), 整体时间复杂度为 O(N N * logN)比暴力枚举好多了。
三数之和
https://leetcode.cn/problems/3sum/ 解法双指针
在做这道题目的时候我们一开始想到的就是直接暴力求解使用三个循环时间复杂度为 O(N ^ 3) 作为一个算法题我们需要优化它的性能我们可以使用双指针来代替两个循环这样最多只需要遍历 2N 个元素加上一个循环时间复杂度就可以变为 O(N ^ 2)
我们可以借助两数之和这道题目的算法思路通过对撞指针找到 两数之和为 taregt 而target 可以由 0 - 第三个数字获得使用这个思路的时候需要先对数组排好序。 这里有一个方法 能将一串数字转化为 链表 —— Arrays.asList(…)这样就不用这么麻烦添加元素到链表上了 这里要避免重复的三元组的出现再取完三元组后双指针各自向中间靠拢一步然后进行去重操作避免和上回的元素相同。 在每次执行完双指针算法的时候可以再对 最外层循环的变量先 再去重因为这个元素的三元组已经找过了。 为什么去重之后三元组就不会重复 因为数组是有序的双指针是向中间靠拢的左指针所对应的数值一定的大于上回的数值右指针对应的数值一定的小于上回的数值并且左指针一定小于右指针所以右指针不可能去到左指针上回的数值这就保证有一个数字是一定不重复的也就保证三元组的不重复性 经过双指针的优化时间复杂度为O(N^2 N * logN)
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger list new ArrayList();int len nums.length;for(int i 0; i len - 2;) {int target 0 - nums[i];for(int left i 1, right len - 1; left right;) {if(nums[left] nums[right] target) {ListInteger l new ArrayList(Arrays.asList(nums[i],nums[left],nums[right]));list.add(l);left;right--;while(left right nums[right1] nums[right]) {right--;}while(left right nums[left-1] nums[left]) {left;}} else if (nums[left] nums[right] target) {right--;} else {left;}}//去重i;while(i len nums[i-1] nums[i]) {i;}}return list;}
}
