龙泉驿区建设局网站,引流推广平台软件,成都专业做网站公司哪家好,wordpress centos 7安装什么是双指针#xff08;对撞指针、快慢指针#xff09;双指针#xff0c;指的是在遍历对象的过程中#xff0c;不是普通的使用单个指针进行访问#xff0c;而是使用两个相同方向#xff08;快慢指针#xff09;或者相反方向#xff08;对撞指针#xff09;的指针进行…什么是双指针对撞指针、快慢指针双指针指的是在遍历对象的过程中不是普通的使用单个指针进行访问而是使用两个相同方向快慢指针或者相反方向对撞指针的指针进行扫描从而达到相应的目的。换言之双指针法充分使用了数组有序这一特征从而在某些情况下能够简化一些运算。在LeetCode题库中关于双指针的问题还是挺多的。双指针截图来之LeetCode中文官网用法对撞指针对撞指针是指在有序数组中将指向最左侧的索引定义为左指针(left)最右侧的定义为右指针(right)然后从两头向中间进行数组遍历。对撞数组适用于有序数组也就是说当你遇到题目给定有序数组时应该第一时间想到用对撞指针解题。伪代码大致如下function fn (list) {var left 0;var right list.length - 1;//遍历数组while (left right) {left;// 一些条件判断 和处理... ...right--;}
}
举个LeetCode上的例子以LeetCode 881救生艇问题为例由于本题只要求计算出最小船数所以原数组是否被改变和元素索引位置都不考虑在内所以可以先对于给定数组进行排序再从数组两侧向中间遍历。所以解题思路如下对给定数组进行升序排序初始化左右指针每次都用一个”最重的“和一个”最轻的“进行配对如果二人重量小于Limit则此时的”最轻的“上船即left。不管”最轻的“是否上船”最重的“都要上船即right--并且所需船数量加一即num代码如下var numRescueBoats function(people, limit) {people.sort((a, b) (a - b));var num 0let left 0let right people.length - 1while (left right) {if ((people[left] people[right]) limit) {left}right--num}return num
};
快慢指针快慢指针也是双指针但是两个指针从同一侧开始遍历数组将这两个指针分别定义为快指针fast和慢指针slow两个指针以不同的策略移动直到两个指针的值相等或其他特殊条件为止如fast每次增长两个slow每次增长一个。以LeetCode 141.环形链表为例,判断给定链表中是否存在环可以定义快慢两个指针快指针每次增长一个而慢指针每次增长两个最后两个指针指向节点的值相等则说明有环。就好像一个环形跑道上有一快一慢两个运动员赛跑如果时间足够长跑地快的运动员一定会赶上慢的运动员。解题代码如下/*** Definition for singly-linked list.* function ListNode(val) {* this.val val;* this.next null;* }*//*** param {ListNode} head* return {boolean}*/
var hasCycle function(head) {if (head null || head.next null) {return false}let slow headlet fast head.nextwhile (slow ! fast) {if (fast null || fast.next null) {return false}slow slow.nextfast fast.next.next}return true
};
再比如LeetCode 26 删除排序数组中的重复项这里还是定义快慢两个指针。快指针每次增长一个慢指针只有当快慢指针上的值不同时才增长一个由于是有序数组快慢指针值不等说明找到了新值。真实代码var removeDuplicates function (nums) {if (nums.length 0) {return 0;}let slow 0;for (let fast 0; fast nums.length; fast) {if (nums[fast] ! nums[slow]) {slow;nums[slow] nums[fast];}}return slow 1;
};
总结当遇到有序数组时应该优先想到双指针来解决问题因两个指针的同时遍历会减少空间复杂度和时间复杂度。欢迎关注微信公众号——【较真的前端相关题目LeetCode.141.环形链表 LeetCode.026.删除数组中重复的项LeetCode.881.救生艇参考文献《LeetBook》双指针【算法总结--数组相关】双指针法的常见应用。1.4.2 双指针技巧二
