上一 part 刚写完二分和滑窗,他们都属于特殊的双指针方法,所以这一 part 直接汇总一下除了特殊的二分和滑窗外的其他双指针写法
这里主要是快慢指针
和端点指针
, 解决一些一次遍历搞不掂,多个指针协商干活不累的题目,基本上觉得属于一种解题上的思路,一次不行,我就两次的样子;
所以刷完基础双指针,然后滑窗和二分后,这种思路在今后解题上应该会不定期能冒出来吧;
所以下期学习另外一种解题思路,回溯吧;
双指针在很多常用的数据结构和算法中,都已经用到,比方说链表遍历
过程中,就可以用双指针找中位数,找环
;在二分法
中用到的也是双指针;滑动窗口
,以及双滑动窗口
等
所以双指针
是一个解决问题的思路,当设置一个指针遍历不足以形成对照的时候,可以设置更多的参照指针来服务自己,只是一般情况两个指针足以,所以这种解决思路称为双指针
比较常见的双指针形式,一般是快指针走 2 步,慢指针走 1 步,达到一种对照的作用;
解决了形如链表的中位数
,链表有环
等问题;
还有一种是读写指针
,这种也是一个指针 read 先走,然后触发某个条件之后,才会让 write 走,也就形成了快慢的效果;
最常见的就是二分法,都是设置 l r 指针,然后向中间合拢;所以所有的二分法的使用也是双指针的使用
还有一种就是排好序之后,根据最大值和最小值之间的运算来求值的,这个时候也需要端点指针
在做快慢指针的题目的时候,咋一看题目和快慢指针没有一毛线关系,但是一般都是迭代啊,或者重复值啊什么的,反正就是需要进行相同的运算
,需要判断是否曾经出现过相同的值
, 这个时候,要不就用 hashMap 缓存一波,要不就用快慢指针,将原题转成类型链表的结构,next 指针就是对应的迭代函数
,然后求是否有环(202. 快乐数), 或者求环的入口位置(287. 寻找重复数)
当然上面这种属于特殊题目的特殊做法,比方说 287. 寻找重复数 那是因为这里的下标和值刚好没法完全重合,且有重复数,要是值也是从 0,n-1,那就没法子用值当下标的写法了
模板1
参考视频:传送门
分析
var detectCycle = function(head) {
const emptyNode = new ListNode()
emptyNode.next = head;
if(!head) return null
let slow = fast = emptyNode
while(fast && fast.next){
slow = slow.next
fast = fast.next.next
if(slow === fast){
// 相交了,证明相交了
let next = emptyNode
while(next!== slow){
next = next.next
slow = slow.next
}
// 相交的时候,就是环入口
return slow
}
}
return null
}
分析 -- 双指针法(快慢指针)
var findDuplicate = function (nums) {
let slow = fast = 0 // 初始节点
while(fast && nums[fast]){
slow = nums[slow]
fast = nums[nums[fast]]
if(slow === fast){
let next = 0
while(next !== slow) {
slow = nums[slow]
next = nums[next]
}
return slow
}
}
}
分析
var findDuplicate = function (nums) {
let left = 1,
right = nums.length - 1; // 值是 1 - n
while (left < right) {
const mid = ((right - left) >> 1) + left;
const count = nums.reduce((prev, cur) => (cur <= mid ? prev + 1 : prev), 0); // 小于等于 count 的值
if (count > mid) {
// 如果 [1,mid] 这个数组满值的情况才只有 mid 个,现在 count 如果比这个还大,证明重复的值在这里面
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
读写指针也算是快慢指针的一种,读指针一般会先走,触发某种条件之后,才会移动写指针
分析 -- 读写指针
var removeDuplicates = function(nums) {
let write = read = 0
while(read <nums.length){
while(nums[write] === nums[read] && read <nums.length ){
if(right-left+1 > 2){
nums.splice(read,1) //删除读指针当前的下标
} else{
read++
}
}
// 一轮相同值走完,写指针和读指针指向同一个值
write = read
}
};
分析
var isHappy = function (n) {
const set = new Set()
let result
const dfs = n => {
let ret = 0;
while (n) {
ret += Math.pow(n % 10, 2);
n = Math.floor(n / 10);
}
if(ret === 1) {
result = true
return
}
if(set.has(ret)){
result = false
return
}
set.add(ret)
// 迭代写法,如果用 return 就是递归的写法了
dfs(ret);
}
dfs(n)
return result
};
分析
var isHappy = function (n) {
function getNext(n) {
let ret = 0;
while (n) {
ret += Math.pow(n % 10, 2);
n = Math.floor(n / 10);
}
return ret
}
let s = f = n // 初始化的值都是 n
while(f !== 1 && getNext(f) !== 1){
s = getNext(s)
f = getNext(getNext(f))
if(s === f) return false
}
return true
}
分析
var threeSumClosest = function(nums, target) {
const len = nums.length
let ret;
let temp = Infinity // sum 与 target 的相差值
for(let i =0;i<len-2;i++){
for(let j = len-1;j>1;j--){
for(let k = i+1;k<j;k++){
const sum=nums[i]+nums[j]+nums[k]
const bet = Math.abs(sum-target)
if(bet<temp){
// 这一组的和比之前的更接近 target
ret = sum;
temp = bet
}
}
}
}
return ret
};
分析
var numSubarrayProductLessThanK = function (nums, k) {
let l = (r = 0);
let product = 1; // 默认最小为 1
let ret = 0; // 最大长度
while (r < nums.length) {
const rr = nums[r];
product *= rr;
while (product >= k && l <= r) {
// 超出了 k
ll = nums[l];
product = product / ll;
l++;
}
// 这个时候 [l,r] 之间的值的乘积是小于 k 的
ret += r - l + 1;
r++;
}
return ret;
};
分析
var sortedSquares = function(nums) {
let l = 0,r = nums.length- 1
let ret = []
while(l<=r){
if(nums[r]>Math.abs(nums[l])){
ret.unshift(Math.pow(nums[r],2))
r--
}else{
ret.unshift(Math.pow(nums[l],2))
l++
}
}
return ret
};
分析 -- 二分
var minEatingSpeed = function (piles, h) {
let l = 1,
r = piles.reduce((prev, cur) => (prev >= cur ? prev : cur), 1);
while (l <= r) {
const mid = ((r - l) >> 1) + l;
if (getHours(mid) > h) {
// 需要的时间超出了 h, 证明速度不够
l = mid + 1;
} else {
r = mid - 1;
}
}
// 速度为 v 的时候,需要多久吃完
function getHours(v) {
let ret = 0;
for (let i = 0; i < piles.length; i++) {
ret += Math.ceil(piles[i] / v);
}
return ret;
}
return l;
};
分析
var numRescueBoats = function (people, limit) {
let l = 0,
r = people.length - 1;
people.sort((a, b) => a - b);
let count = 0; // 需要的船的数量
while (l <= r) {
const sum = people[l] + people[r];
if (sum > limit) {
r--;
} else {
l++;
r--;
}
count++;
}
return count;
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。