医疗网站报价方案,网站设计与建设作业,网页设计与制作教程期末考试试题,中国商业网点建设开发中心官方网站#x1f490;个人主页#xff1a;初晴~
#x1f4da;相关专栏#xff1a;寻找one piece的刷题之路 什么是双指针算法 双指针算法是一种常用的编程技巧#xff0c;尤其在处理数组和字符串问题时非常有效。这种方法的核心思想是使用两个指针来遍历数据结构#xff0c;这两…
个人主页初晴~
相关专栏寻找one piece的刷题之路 什么是双指针算法 双指针算法是一种常用的编程技巧尤其在处理数组和字符串问题时非常有效。这种方法的核心思想是使用两个指针来遍历数据结构这两个指针通常分别位于数据结构的起始位置或某些特定位置通过移动这两个指针来达到解决问题的目的。双指针算法可以显著减少时间复杂度使其从O(n2)O(n2)降低到O(n)O(n)甚至在某些情况下可以达到O(logn)O(logn)。 常⻅的双指针有两种形式⼀种是对撞指针⼀种是左右指针。 对撞指针⼀般⽤于顺序结构中也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循 环也就是 left right 两个指针指向同⼀个位置 left right 两个指针错开 快慢指针⼜称为⻳兔赛跑算法其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。 这种⽅法对于处理环形链表或数组⾮常有⽤。 其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使⽤快慢指针的思想。 快慢指针的实现⽅式有很多种最常⽤的⼀种就是 • 在⼀次循环中每次让慢的指针向后移动⼀位⽽快的指针往后移动两位实现⼀快⼀慢 一、复写零
题目链接
题目描述 题目分析 题目的意思就是遍历原数组每遇到一次0就将后面所有的数水平向右移动一位并再插入一个0最后仍丢弃溢出的数据仍取原来的数组长度的数据。 分析 如果「从前向后」进⾏原地复写操作的话由于 0 的出现会复写两次导致没有复写的数「被覆 盖掉」。因此我们选择「从后往前」的复写策略。 但是「从后向前」复写的时候我们需要找到「最后⼀个复写的数」因此我们的⼤体流程分两 步 1. 先找到最后⼀个复写的数 我们先初始化两个指针 cur 0 dest -1 当 cur n 的时候⼀直执⾏下⾯循环 判断 cur 位置的元素: ◦ 如果是 0 的话 dest 往后移动两位 ◦ 否则 dest 往后移动⼀位。 • 判断 dest 时候已经到结束位置如果结束就终⽌循环 • 如果没有结束 cur 继续判断。 注意 要判断 dest 是否越界到 n 的位置 如果越界执⾏下⾯三步 n - 1 位置的值修改成 0 cur 向移动⼀步 dest 向前移动两步。 2.然后从后向前进⾏复写操作 从 cur 位置开始往前遍历原数组依次还原出复写后的结果数组 判断 cur 位置的值 1. 如果是 0 dest 以及 dest - 1 位置修改成 0 dest - 2 2. 如果⾮ 0 dest 位置修改成 0 dest - 1 cur-- 复写下⼀个位置 代码实现 class Solution {public void duplicateZeros(int[] arr) {int lenarr.length,cur0,dest-1;while(curlen){if(arr[cur]0){dest2;}else{dest;}if(destlen-1)break;if(destlen-1){arr[len-1]0;cur--;destlen-2;break;}cur;}if(destcur)return;while(cur0){if(arr[cur]!0){arr[dest--]arr[cur--];}else{arr[dest--]0;arr[dest--]0;cur--;}}}
} 二、盛⽔最多的容器
题目描述 题目分析 我们可以设两个指针 left right 分别指向容器的左右两个端点此时容器的容积 : v (right - left) * min( height[right], height[left]) 容器的左边界为 height[left] 右边界为 height[right] 。 为了⽅便叙述我们假设「左边边界」⼩于「右边边界」。 如果此时我们固定⼀个边界改变另⼀个边界⽔的容积会有如下变化形式 容器的宽度⼀定变⼩。 由于左边界较⼩决定了⽔的⾼度。如果改变左边界新的⽔⾯⾼度不确定但是可能会超过原来左边界的柱⼦⾼度因此容器的容积可能会增⼤。如果改变右边界⽆论右边界移动到哪⾥新的⽔⾯的⾼度⼀定不会超过左边界也就是不会超过现在的⽔⾯⾼度但是由于容器的宽度减⼩因此容器的容积⼀定会变⼩的。 由此可⻅左边界和其余边界的组合情况都可以舍去。所以我们可以 left 跳过这个边界继续去判断下⼀个左右边界。 当我们不断重复上述过程每次都可以舍去⼤量不必要的枚举过程直到 left 与 right 相遇。期间产⽣的所有的容积⾥⾯的最⼤值就是最终答案。
代码实现
class Solution {public int maxArea(int[] height) {int l0,rheight.length-1,max0,t;while(lr){if(height[l]height[r]){theight[l]*(r-l);l;}else{theight[r]*(r-l);r--;}if(maxt)maxt;}return max;}
} 三、有效三⻆形的个数
题目链接
题目描述 题目分析
首先我们得知道三条边能构成三角形的充要条件是任意两边之和大于第三边。 不过事实上我们只要保证两条短边和大于最长边即可。 因此我们可以先将数组从小到大进行排序接着用一个指针 j 固定一个「最⻓边」然后在⽐这条边⼩的有序数组中找出⼀个⼆元组使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的我们可以利⽤「对撞指针」来优化
设最⻓边枚举到 j 位置区间 [left, right] 是 j 位置左边的区间也就是⽐它⼩的区间
如果 nums[left] nums[right] nums[i] 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐ nums[j] ⼤的⼆元组 则满⾜条件的有 right - left 种 此时 right 位置的元素的所有情况相当于全部考虑完毕 right-- 进⼊下⼀轮判断 如果 nums[left] nums[right] nums[i] 说明 left 位置的元素是不可能与 [left 1, right] 位置上的元素构成满⾜条件的⼆元组 left 位置的元素可以舍去 left 进⼊下轮循环 代码实现
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int sum0;for(int jnums.length-1;j2;j--){int l0,rj-1;while(lr){if(nums[l]nums[r]nums[j]){sumsumr-l;r--;}else{l;}}}return sum;}
} 四、三数之和
题目链接
题目描述 题目分析
这题其实与上一题十分相似都是要找一个满足一定条件的三元组因此同样我们可以采用先排序接着用一个指针 j 固定一个数 a接着在之后的区间内利用双指针算法找到两数之和等于-a即可 需要注意的是题目要求进行「去重」操作 找到⼀个结果之后 left 和 right 指针要「跳过重复」的元素 当使⽤完⼀次双指针算法之后固定的 a 也要「跳过重复」的元素 代码实现
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger ans new ArrayListListInteger();int nnums.length;for(int j0;jn;){if(nums[j]0)break;int lj1,rn-1;int target-nums[j];while(lr){int sumnums[l]nums[r];if(sumtarget){ans.add(new ArrayListInteger(Arrays.asList(nums[l],nums[r], nums[j])));if(nums[r]nums[l])break;l;r--;while(lrnums[r1]nums[r])r--;while(lrnums[l-1]nums[l])l;}else if(sumtarget){r--;}else{l; } }j;while(jnnums[j]nums[j-1])j;}return ans;}
} 五、四数之和
题目链接
题目描述 题目描述
这题的思想其实也与三数之和类似我们只需要先排序再用一个指针 i 固定一个数 a在这个数 a 的后⾯区间上利⽤「三数之和」找到三个数使这三个数的和等于 target - a 即可
代码实现
class Solution {public ListListInteger fourSum(int[] nums, int target) {int nnums.length;long t,q;Arrays.sort(nums);ListListInteger ansnew ArrayListListInteger();for(int i0;in;){ttarget;t-nums[i];//if(t0)return ans;for(int ji1;jn;){qt;q-nums[j];int lj1,rn-1;while(lr){int sumnums[l]nums[r];if(sumq){ListInteger listnew ArrayListInteger();list.add(nums[i]);list.add(nums[j]);list.add(nums[l]);list.add(nums[r]);ans.add(list);l;r--;while(lrnums[l]nums[l-1])l;while(lrnums[r]nums[r1])r--;}else if(sumq)r--;else l;}j;while(jnnums[j]nums[j-1])j;}i;while(innums[i]nums[i-1])i;}return ans;}
} 总结
双指针技巧的关键点
初始化通常一个指针指向序列的开始位置另一个指针指向序列的结束位置或某个特定位置。移动规则根据问题的具体情况定义指针的移动规则如当条件不满足时向前或向后移动。更新状态在每次移动指针之后更新当前的状态如累加、记录最大值等。退出条件当两个指针相遇或某个指针超出界限时结束循环。
双指针算法是一种简单而有效的算法技巧通过维护两个指针的状态来简化问题的复杂度。合理地运用双指针法可以帮助我们在处理数组和字符串问题时更加高效地达成目标。 那么本篇文章就到此为止了如果觉得这篇文章对你有帮助的话可以点一下关注和点赞来支持作者哦。如果有什么讲的不对的地方欢迎在评论区指出希望能够和你们一起进步✊
