乐趣区

关于leetcode:前端leetcde算法面试套路之双指针

前言

上一 part 刚写完二分和滑窗,他们都属于非凡的双指针办法,所以这一 part 间接汇总一下除了非凡的二分和滑窗外的其余双指针写法

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

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

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

注释

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

所以 双指针 是一个解决问题的思路,当设置一个指针遍历不足以造成对照的时候,能够设置更多的参照指针来服务本人,只是个别状况两个指针足以,所以这种解决思路称为 双指针

快慢指针

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

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

左右端点指针

最常见的就是二分法,都是设置 l r 指针,而后向两头合拢;所以所有的二分法的应用也是双指针的应用

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

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

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

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

题目汇总

题目

142. 环形链表 II

剖析

  1. 典型的快慢指针写法,在链表专题写过相应的题解了
    1. 环形链表 II
  2. 做一下这个题,是为了下一题的前置
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;
};
退出移动版