写点什么

前端 leetcde 算法面试套路之双指针

作者:js2030code
  • 2022-11-16
    浙江
  • 本文字数:5014 字

    阅读完需:约 16 分钟

前言

上一 part 刚写完二分和滑窗,他们都属于特殊的双指针方法,所以这一 part 直接汇总一下除了特殊的二分和滑窗外的其他双指针写法


这里主要是快慢指针端点指针, 解决一些一次遍历搞不掂,多个指针协商干活不累的题目,基本上觉得属于一种解题上的思路,一次不行,我就两次的样子;


所以刷完基础双指针,然后滑窗和二分后,这种思路在今后解题上应该会不定期能冒出来吧;


所以下期学习另外一种解题思路,回溯吧;

正文

双指针在很多常用的数据结构和算法中,都已经用到,比方说链表遍历过程中,就可以用双指针找中位数,找环;在二分法中用到的也是双指针;滑动窗口,以及双滑动窗口


所以双指针是一个解决问题的思路,当设置一个指针遍历不足以形成对照的时候,可以设置更多的参照指针来服务自己,只是一般情况两个指针足以,所以这种解决思路称为双指针

快慢指针

比较常见的双指针形式,一般是快指针走 2 步,慢指针走 1 步,达到一种对照的作用;解决了形如链表的中位数链表有环 等问题;


还有一种是读写指针,这种也是一个指针 read 先走,然后触发某个条件之后,才会让 write 走,也就形成了快慢的效果;

左右端点指针

最常见的就是二分法,都是设置 l r 指针,然后向中间合拢;所以所有的二分法的使用也是双指针的使用


还有一种就是排好序之后,根据最大值和最小值之间的运算来求值的,这个时候也需要端点指针

找重复值的时候,转换成链表找环 -- 快慢指针的变形

在做快慢指针的题目的时候,咋一看题目和快慢指针没有一毛线关系,但是一般都是迭代啊,或者重复值啊什么的,反正就是需要进行相同的运算,需要判断是否曾经出现过相同的值, 这个时候,要不就用 hashMap 缓存一波,要不就用快慢指针,将原题转成类型链表的结构,next 指针就是对应的迭代函数,然后求是否有环(202. 快乐数), 或者求环的入口位置(287. 寻找重复数)


当然上面这种属于特殊题目的特殊做法,比方说 287. 寻找重复数 那是因为这里的下标和值刚好没法完全重合,且有重复数,要是值也是从 [0,n-1],那就没法子用值当下标的写法了

题目汇总

题目

142. 环形链表 II

分析


  1. 典型的快慢指针写法,在链表专题写过相应的题解了

  2. 环形链表 II

  3. 做一下这个题,是为了下一题的前置


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}
复制代码

287. 寻找重复数

分析 -- 双指针法(快慢指针)


  1. 审题: 只有一个重复的整数,而这个重复的整数的出现次数不确定

  2. 可以用 map 用空间换时间,也可以排序之后直接找,但是这样都不符合题意

  3. 之前在二分法 tab 中做了一次: 287. 寻找重复数

  4. 这道题是可以用快慢指针做的,就是将数组中的值当成是指向数组下标的指针,然后将整个数组转成链表;而题目就转成了,一直一个环形链表(有重复的值,也就是在链表中有重复指向的指针),求环的入口;

  5. 参考寻找环形链表的入口 -- 142. 环形链表 II

  6. 时间复杂度 O(N)


参考视频:传送门


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        }    }}
复制代码


分析


  1. 给定长度为 n+1 的 nums,里面的值都是 1-n, 本题中只有一个值是重复的,找出这个值

  2. 注意这里只是表明重复的只有一个值,但是这个值重复多少次并没有说明,所以不能用简单的异或二进制处理

  3. 但是我们可以选定以 mid 值,然后判断小于等于 mid 值 count,如果 count 超出了 mid ,证明在 [1,mid] 中至少有一个值重复了,这个时候可以砍掉右侧部分

  4. 当 left 和 right 相等之后,即找到了唯一重复的值,因为这个时候左右两侧的值都不服要求,就只有这个了

  5. 时间复杂度 O(nlohn), 空间复杂度 1


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;};
复制代码

80. 删除有序数组中的重复项 II

读写指针也算是快慢指针的一种,读指针一般会先走,触发某种条件之后,才会移动写指针


分析 -- 读写指针


  1. 给定的数组是排好序的,然后需要删除多余节点,使得最多出现 2 次

  2. 设置读写指针 read 和 write, 遍历的每一步中,读写指针都指向相同的值,但是指向的下标可能不一样

  3. 当相同的值超过了 2, 即 [left,right] 的长度超出 2, 则原地删除 right 指针指向的值

  4. 时间复杂度 O(n)


 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    }};
复制代码

202. 快乐数

分析


  1. 这里盲猜是用迭代的写法来求,因为没次按要求改造一个 ret,如果不符合成功或者失败要求,就会继续迭代下去

  2. 因为是不断按十进制位取平方求和,所以截止条件应该是符合要求,得到的和 sum === 1

  3. 如果不符合条件,肯定就是遭遇到循环了,这里用 set 缓存所有迭代过程中的 ret,只有迭代过程中再次出现 set 中的值,就是导致循环了,直接返回 false 即可

  4. 时间复杂度,这个不太会求,但是会需要 set 来缓存数据


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
};
复制代码


分析


  1. 这是快慢指针专题,所以其实可以用快慢指针是否有环来处理

  2. 所以迭代的过程就和链表的 next 是差不多的,如果出现环,则返回 false,如果出现值 1,则返回 true

  3. 这样就不需要额外的 set 去缓存值了


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}
复制代码

16. 最接近的三数之和

分析


  1. 暴力解法,直接固定左右两个节点 i,j,然后设置第三个指针 k 在两个指针之间遍历求和,找出最接近 target 的值

  2. i 遍历一次 nums,j 和 k 每固定一次加起来遍历一次 nums,所以时间复杂度为 O(n2)


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}; 
复制代码

713. 乘积小于 K 的子数组

分析


  1. 求的是符合要求的,连续的子数组的最大个数,盲猜可以用不定大小的滑窗处理

  2. 移动 r 指针扩展窗口,然后当乘积超出 k 的时候,开始收缩 l 指针,最后得到一个符合要求的窗口 [l,r]

  3. 在这个窗口 [l,r] 中,任意的一种组合都符合要求,由于组合属于一种特性的判断,所以不需要用双窗口来求符合要求的数量,直接 r-l+1 即可

  4. 需要注意的时候,收缩 l 指针的时候,判定条件 l<=r 的原因是,当前 nums[r] 可能就比 k 大,这个情况应该收缩窗口为 0,并走到下一步

  5. 时间复杂度 O(n)


 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; };
复制代码

977. 有序数组的平方

分析


  1. 分发左右指针 l,r, 然后用一个额外的数组来存储平方后的数组即可

  2. 由于这是一个排好序的增序列,会存在负数,但是值的平方最大值就在数组的两侧,所以每次比较两侧的值,就能获取到相应的最大值,然后 unshift 到数组中即可

  3. 时间复杂度 O(n), 空间复杂度 O(n)


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};
复制代码

875. 爱吃香蕉的珂珂

分析 -- 二分


  1. l = 1 , r = piles[max],他们分别代表了最大和最小的速度; 这样找出中间值,然后判断是否能在 h 小时内吃完,能吃完则向左逼近,不能吃完则向右逼近,直到最小的速度出现

  2. 每一次二分取 mid 之后,都要遍历一次 piles, 所以时间复杂度是 nlogn


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;};
复制代码

881. 救生艇

分析


  1. 由于这里最多只能载人 2, 负重最多是 limit,所以选择载人的时候,尽量先选择最重的和最轻的进行匹配,尽量一船二人坐,可以减少数量,所以先给 people 排序

  2. l,r 指针指向最轻和最重的人

  3. 然后每次求出 2 人组合的最轻总量和 sum, 让它和 limit 进行比较,进而控制 l, r 的移动

  4. 时间复杂度 O(nlogn) 主要是排序问题


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;};
复制代码


用户头像

js2030code

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
前端leetcde算法面试套路之双指针_JavaScript_js2030code_InfoQ写作社区