乐趣区

关于leetcode:刷完这19道leetcode二分查找算法不信进不了大厂

对于二分题,其实就是设定一个两头值 mid, 而后通过这个值进行一个判断 check(mid),通过这个函数的返回值,判断将不可能的一半剪切掉;

在刷题的时候须要留神次要是两局部,check 函数的定义以及边界的抉择(等号的抉择,以及最初是 return left 还是 right)

这次次要是 LC 的二分专题,外面的简略题根本都是比拟显性的提醒了 check 函数的构建,比方说间接找出某个值,而难题个别都是 check 函数比拟难想的,这个时候就须要教训了;

狭义上只有是排好序(部分排序),只有是找某个值,大部分都能够思考用二分,这样复杂度能够升高很多;

对于边界,我的循环完结条件是 left <= right,因为如果要多记很多模板,怕会出问题,所以退出条件根本都按这个,而后无论是那种模块,都基于这个完结条件来判断,这样能够把问题膨胀都循环里的断定的 check 函数,多做了就会发现端倪;

而后对于退出之后 left 还是 right,这个是具体问题具体分析;因为我的完结断定条件是 left<=right,所以如果没用两头返回,那么必然存在 left === right 的时候,这个时候依据断定条件,就晓得 right 在 left 的后面,而到底是左迫近,还是右迫近,都比拟好判断了,因为这个时候曾经退出去了,left 和 right 所代表的 check 的状态也是不言而喻的,那么看题目要求什么,给什么即可;

对于二分,我感觉这个专题就根本足够了,简略居多,难题也有两个;如果是第一次学习二分,那么依照专栏的三个模板去记忆也 ok,他人的教训终归是适宜他人本人,做题最重要是把握住本人的节奏,记忆本人最相熟的那个点,强行模拟他人反而落了下乘;

当然那个男人那么强,我的做题就是模拟的他,缓缓大佬的解法就是我本人的节奏了,毕竟模拟多了,其实就是本人的了,除了算法,其余的工程化学习也是一样的;

那么,周末高兴,下周开 dp 吧,毕竟这个听有意思的。

模板 1

  • 目标值是一个固定的 target,在二分过程中须要一直的判断,如果胜利就返回对应的值,否则间接返回失败的值
  • 返回值如果是向下取,返回 right,如果向上取,则返回 left,还有可能返回一个特定给的失败值;
var search = function (fn, target) {
  let left = 最小值,
    right = 最大值;
  while (left <= right) {
    // 取 mid 值
    const mid = ((right - left) >> 1) + left;
    // 这里的 fn 可能是函数,也可能只是数组取值,反正就是能够获得一个值去跟 target 比拟
    const temp = fn(mid);
    if (temp === target) return mid;
    if (temp < target) {left = mid + 1;} else {right = mid - 1;}
  }
  return 没有准确匹配后的值;
};

704. 二分查找

var search = function (nums, target) {
  const len = nums.length;
  if (!len) return -1;
  let left = 0,
    right = len - 1;
  while (left <= right) {const mid = ((right - left) >> 1) + left;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}
  }
  return -1;
};

69. x 的平方根

// 69. x 的平方根
var mySqrt = function (x) {
  let left = 0,
    right = x;
  while (left <= right) {const mid = ((right - left) >> 1) + left;
    const sqrt = mid * mid;
    if (sqrt === x) return mid;
    if (sqrt < x) {left = mid + 1;} else {right = mid - 1;}
  }
  // 向下取整
  return right;
};

374. 猜数字大小

剖析

  1. 这里内置一个函数 guess(n), 返回值是 -1 0 1, -1 是 targt 值更小
var guessNumber = function (n) {
  let left = 1,
    right = n;
  while (left <= right) {const mid = ((right - left) >> 1) + left;

    if (guess(mid) === 0) return mid;
    if (guess(mid) > 0) {
      // 这个时候 mid < pick
      left = mid + 1;
    } else {right = mid - 1;}
  }
};

// 本人模仿一下这个 guess 函数吧 -- 假设第二个参数就是指标猜的数字,咱们能够用它来初始化,默认是 5
function guess(num, pick = 5) {if (num === pick) return 0;
  if (pick < num) return -1;
  if (pick > num) return 1;
}

441. 排列硬币

剖析

  1. 这里求的是一个左侧极值的二分法,是向右迫近的二分
  2. 累计值算法是小学数学题 sum = (first+end)*count/2
  3. 每次取中间层数,求出到这个层数须要的币数 sum,而后和目标值 n 比拟
  4. 如果刚好合乎,间接返回(这里能够膨胀到左侧断定条件中);如果 count 比拟少,则 left 要提到 mid+1, 否则 right 要提到 mid-1
  5. 因为最初要返回的是最迫近 n 的层数,所以判断一下当 left === right 状况,如果小于 n,则 left = mid+1,这个时候 right 符合要求,所以跳出循环后,返回的是 right
  6. 工夫复杂度 O(logN)
var arrangeCoins = function (n) {
  let left = 0,
    right = n;
  while (left <= right) {const mid = left + ((right - left) >> 1);
    // mid 层的时候满的硬币数
    const sum = ((1 + mid) * mid) / 2;
    if (sum === n) return mid;
    if (sum < n) {left = mid + 1;} else {right = mid - 1;}
  }
  return right;
};

33. 搜寻旋转排序数组

剖析

  1. 已知:原始数组 nums 是生序排序的,且数组中的值不一样的
  2. 入参的 nums 是在某个下标 k 的作用下产生了重置,使得 nums 当初是先升序数组 [k,len-1]而后断裂后,再一个升序数组[0,k-1]
  3. 这是一个部分排好序的数组,所以能够用二分解决, 返回的是 target 值的下标或者 -1
  4. 所以每次都用排好序的一半来作为判断根据,如果在排好序这边,则删除另外,反之亦然
  5. 工夫复杂度 O(logn)

参考视频:传送门

var search = function (nums, target) {
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {const mid = ((right - left) >> 1) + left;
    if (nums[mid] === target) return mid;
    if (nums[mid] >= nums[left]) {// [left,mid] 是有序的
      if (nums[left] <= target && target < nums[mid]) {// target 在[left , mid) 中
        right = mid - 1;
      } else {left = mid + 1;}
    } else {// [mid,right] 是有序的
      if (nums[mid] < target && target <= nums[right]) {// target 在(mid , right] 中
        left = mid + 1;
      } else {right = mid - 1;}
    }
  }
  return -1;
};

模板 2 — 须要用到街坊值判断

相比于模板 1,模板 2 中不是仅有一个符合条件值,而是一系列值,咱们须要找到符合要求的那个 极值 ,比方说是 符合条件的最大值 / 第一个值 等;

var search = function (fn) {
  let left = 最小值,
    right = 最大值;
  while (left <= right) {
    // 取 mid 值
    const mid = ((right - left) >> 1) + left;
    // 这里的 fn 可能是函数,也可能只是数组取值,反正就是能够获得一个值去跟 target 比拟
    const bool = fn(mid);
    if (bool) {
      // 胜利了,要向还没胜利的中央寻找
      right = mid - 1;
    } else {left = mid + 1;}
  }
  return 特定的值;
};

278. 第一个谬误的版本

剖析

  1. 这里要找出的是第一个谬误版本,而整顿版本排列是 失常 -> 谬误,所以这里是依据谬误向左迫近
  2. 如果是谬误版本,right 指针一直往左,如果是失常版本,left 指针一直往右,当左右指针相交时,如果是谬误版本,right 持续往左,达到失常区,这个时候 left 就是第一个谬误版本了
  3. 工夫复杂度 O(logn)
var solution = function (isBadVersion) {return function (n) {
    let left = 1,
      right = n;
    while (left <= right) {const mid = ((right - left) >> 1) + left;
      if (isBadVersion(mid)) {
        // 如果是谬误版本
        right = mid - 1;
      } else {left = mid + 1;}
    }

    return left;
  };
};

162. 寻找峰值

剖析

  1. 已知多峰的时候只需返回一个即可,那么就是间接做二分判断即可;
  2. 两侧边缘值也能够是峰值, 因为题目给了两侧是 -Infinity;
  3. 犹豫曾经存在整体区域外的最低点,所以只有找到一个部分降落区域,那么部分回升区域中必定存在峰值;
var findPeakElement = function (nums) {nums[-1] = nums[nums.length] = -Infinity; // 设置边界值,这样保障在边缘的时候也只须要两个值就能判极值
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {const mid = ((right - left) >> 1) + left;
    // 找出一个有峰值的区间
    if (nums[mid] > nums[mid + 1]) {// [mid,right] 部分降落,而[-1,mid] 是部分回升的,比拟有一个最低值
      right = mid - 1;
    } else {left = mid + 1;}
  }
  return left;
};

153. 寻找旋转排序数组中的最小值

剖析

  1. 这里其实就是找谷值,留神的是,这里的值互不相等且部分单增,所以能够加一个辅助条件 nums[-1] = nums[len] = infinite, 这样能保障谷值在边缘也能间接找到
  2. 留神:这里返回的是最小值,而不是最小坐标
  3. 留神获得 mid 值之后,将 mid 与 right 的值比拟,只会呈现两种状况,
  4. 如果 nums[mid]<=nums[right],则 mid 和 right 重合或 mid 在 right 之后且单增,这个时候无论是在第一个单增区间还是第二个,谷点都在 mid 之钱,所以 right = mid-1
var findMin = function (nums) {
  let len = nums.length;
  nums[-1] = nums[len] = Infinity;
  let left = 0,
    right = len - 1;

  while (left <= right) {const mid = ((right - left) >> 1) + left;

    if (nums[mid - 1] > nums[mid] && nums[mid] < nums[mid + 1])
      return nums[mid]; // 谷值

    if(nums[mid]<=nums[right]){// [mid,right] 单增
        // 留神这个等号为啥要加,能够考虑一下如果 left 和 right 相等时,对应的 mid 也是这个点,那么是让 right 走,还是让 left 走;这里咱们最初返回值是 left, 所以让 right 走一步结束战斗
        right = mid-1
    }else{left = mid+1}
  }

  return nums[left];
};

154. 寻找旋转排序数组中的最小值 II

  • 和 153. 寻找旋转排序数组中的最小值 相似,然而因为值能够反复,无奈直接判断单增区间
  • 所以想方法将右侧与 mid 相等的值先删除掉,这个时候剩下的不同值能够与 153 题一样做解决了
var findMin = function(nums) {
    const len  = nums.length
    nums[-1] = nums[len] = Infinity
    let left = 0,right = len-1
    while(left<=right){const mid = ((right-left)>>1) + left

        // 将右侧与 mid 同值的值删掉
        while(nums[right] === nums[mid] && right>mid){right --}
        // 因为存在反复值,所以拐点值右侧能够是直线,而不肯定是单增
        if(nums[mid-1]>nums[mid] && nums[mid]<=nums[mid+1]) return nums[mid]

        if(nums[mid]<=nums[right]){
            // 上一题这里的等号是当 left 和 right 重合时的非凡状况
            // 当初因为值可能反复,所以不能直接判断出 [mid,right] 是递增的区间了,所以要先为右侧雷同的值进行删减,而后再进行即可
            right = mid-1
        }else{left = mid+1}
    }
    return nums[left]
};

模板 3

在排序数组中查找元素的第一个和最初一个地位

剖析

  1. 失常查找 target 值,直到找到左侧第一个,
  2. 如果没有找到,则间接返回 [-1,-1]
  3. 如果找到了左侧的 target 值,这个时候以左侧 left 为终点,再进行一次二分,求右侧第一个 target 值,最初返回即可
  4. 工夫复杂度 O(logn)
var searchRange = function(nums, target) {if(!nums) return [-1,-1]
    let left = 0,right = nums.length-1
    let ret = []
    // 找左节点
    while(left<=right){const mid = ((right-left)>>1) + left
        if(nums[mid]<target){left = mid+1}else{right = mid-1}
    }
    if(nums[left]!== target) return [-1,-1]
    // 找右节点
    let l = left,r = nums.length-1
    while(l<=r){const mid = ((r-l)>>1) + l
        if(nums[mid]>target){r = mid-1}else{l = mid+1}
    }
    return [left,r]
};

658. 找到 K 个最靠近的元素

剖析

  1. 先找出 arr 中值最靠近 x 左侧的下标值 — 如果有等于 x 的就取 x 没有就取最靠近的前一个
  2. 而后开始向两边扩散找靠近 x 的前 k 个值
  3. 工夫复杂度 O(log(n))
var findClosestElements = function (arr, k, x) {
  let l = 0,
    r = arr.length - 1;
  while (l <= r) {const mid = ((r - l) >> 1) + l;
    if (arr[mid] > x) {r = mid - 1;} else {l = mid + 1;}
  }
  //   这个时候 r 是左侧最靠近 x 的值下标,l 是右侧最靠近 x 的值
  let lIndex = r,
    rIndex = l; // 避免混同
  let ret = [];
  while (k--) {
    let isLeft = true;
    if (lIndex >= 0 && rIndex < arr.length) {isLeft = x - arr[lIndex] <= arr[rIndex] - x;
    } else if (rIndex < arr.length) {isLeft = false;}
    if (isLeft) {ret.unshift(arr[lIndex]);
      lIndex--;
    } else {ret.push(arr[rIndex]);
      rIndex++;
    }
  }
  return ret;
};

其余练习题

50. Pow(x, n)

剖析

  1. 间接将 n 进行拆分,而后递归求值 — 而后超时了,因为很多值都是反复的,
  2. 而后就是疾速迭代咱们 2 – 4 -16
  3. 值得注意的是,这里 n 的取值是 [-2^31,2^31-1] 原本没啥事,然而吧,你将 n 转成负数再执行, 那么 n >> 1 就有事了,一旦 n 是 -2^31, 那么第一次递归的时候 recursion 的 n 就是正数了
  4. 所以要用 >>> 或者用数学的办法
  5. 工夫复杂度 O(logn)
var myPow = function (x, n) {const recursion = (n) => {if (n === 0) return 1;
    // const y = recursion(n >> 1);
    const y = recursion(Math.floor(n / 2));
    return n % 2 ? y * y * x : y * y;
  };
  return n < 0 ? 1 / recursion(-n) : recursion(n);
};

console.log(myPow(2.1, 3));
console.log(myPow(2, -2));

367. 无效的齐全平方数

/** * @剖析 * 1. 概念:若 x*x = y,则 y 是齐全平方数 */
var isPerfectSquare = function (num) {
  let left = 0,
    right = num;
  while (left <= right) {const mid = ((right - left) >> 1) + left;
    const temp = mid * mid;
    if (temp === num) return true;
    if (temp > num) {right = mid - 1;} else {left = mid + 1;}
  }

  return false;
};

744. 寻找比指标字母大的最小字母

剖析:

  1. 留神:这道题应该改成,给定一个排好序的字符数组,找出处 target 所在位置的下一个字母,且该数组首尾连接 — 即如果给定的 target 在数组最初,则下一个就是首字母;
  2. 字母先转成 UniCode 编码,而后用 编码大小来进行比拟,留神这里只有小写字母,所以 left right 值也是有了
  3. 这是个奇葩的设定,[‘a’,’c’],’z’ , 如果依照真正 charCode 比拟,数组中没有比 ‘z’ 大的,这里这能说是程序遍历数组后,在 target 之后的第一个元素
  4. 工夫复杂度: O(logN)
 var nextGreatestLetter = function(letters, target) {const targetIndex = target.charCodeAt()
    let left = 0,right = numbers.length-1

    while(left <= right){const mid = ((right-left) >> 1) + left

        if(letters[mid].charCodeAt()>targetIndex){
            // 只有是合乎的,都返回往左走,晓得走不了
            right = mid-1
        }else{left= mid+1}
    }
    if(left>=numbers.length) return letters[0]
    return letters[left]

};

349. 两个数组的交加

剖析:

  1. 先为 nums1 和 nums2 排序,而后遍历其中一个数组,另外一个数组做二分查找,最初失去后果
  2. 这里间接取 nums1 做遍历,理论能够找个长度少的遍历,长度大的做二分,这样查找过程的工夫复杂度即为 O(nlogm), 其中 n<=m
  3. 然而因为做了排序,理论的工夫复杂度是 mlogm m 是大的那个长度
var intersection = function (nums1, nums2) {
  const l1 = nums1.length,
    l2 = nums2.length;
  if (!l1 || !l2) return [];
  // 先排序
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  const ret = [];
  for (let i = 0;i<l1;i++) {if(i>0 && nums1[i-1] === nums1[i]) continue // 反复值跳过
      const n = nums1[i];
    let left = 0,
      right = l2-1;
    while (left <= right) {const mid = ((right - left) >> 1) + left;
      if (nums2[mid] === n) {ret.push(n);
        break;
      }
      if (nums2[mid] > n) {right = mid - 1;} else {left = mid + 1;}
    }
  }
  return ret
};

350. 两个数组的交加 II

  • 间接用 map 将其中一个数组的值映射保存起来
  • 而后遍历另外的数组,每一次匹配胜利,则 map 的值减一,ret 数组 push 上这个值
  • 直到 map 中的这个值为 0,则这个值在两个数组中的最大公约数达到,不再进行 push 咯
  • 工夫复杂度 O(n+m) , 空间复杂度 O(n) 其中 n 能够是小的那个数组的不同值长度
var intersect = function (nums1, nums2) {const map = new Map(); // 将长数组的值存储一份
  for (let item of nums2) {if (map.has(item)) {map.set(item, map.get(item) + 1);
    } else {map.set(item, 1);
    }
  }
  let ret = [];
  for(let item of nums1){if(!!map.get(item)){map.set(item,map.get(item)-1)
          ret.push(item)
      }
  }

  return ret;
};

167. 两数之和 II – 输出有序数组

剖析

  1. numbers 是升序数组,找出 n1+n2 = target , 返回 n1,n2 对应的下标值 [i1,i2] — 留神下标值从 1 开始
  2. 每个输出只有惟一的输入值
  3. 工夫复杂度 nlogn
var twoSum = function (numbers, target) {for (let i = 0; i < numbers.length-1; i++) {const temp = target - numbers[i];
    let l = i + 1,
      r = numbers.length - 1;
    while (l <= r) {const mid = ((r - l) >> 1) + l;
      if (numbers[mid] === temp) return [i + 1, mid + 1];
      if (numbers[mid] < temp) {left = mid + 1;} else {right = mid - 1;}
    }
  }
};

287. 寻找反复数

剖析

  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;
};

4. 寻找两个正序数组的中位数

剖析

  1. 已知两个有序数据,求中位数(和求第 k 小没啥区别)
  2. 依据两个数组的大小,将题转成求第 k 小的题目
  3. 这题应用二分没能间接过,断定条件边界很多,最初放弃间接用二分解决掉了
var findMedianSortedArrays = function (nums1, nums2) {
  const n = nums1.length,
    m = nums2.length;
  let sum = n + m; // 如果是偶数,取两个值 prev,cur , 取两头值
  let k = (sum + 1) / 2; // 能够是非整数
  let cur;
  while (k >= 1) {if (!nums1.length) {cur = nums2.shift();
    } else if (!nums2.length) {cur = nums1.shift();
    } else {if (nums1[0] <= nums2[0]) {cur = nums1.shift();
      } else {cur = nums2.shift();
      }
    }
    k--;
  }
  let next;
  if (k !== 0) {// 这里用 ?? 而不是用 || , 是因为判断 nums[0] 是否为 undefined,而如果是 0 的时候,取 0 而非切换到  Infinity;
    next = Math.min(nums1[0] ?? Infinity, nums2[0] ?? Infinity);
    return (cur + next) / 2;
  }
  return cur;
};

410. 宰割数组的最大值

剖析

  1. 切分数组 nums,使得切割后数组和最大的那个值最小 — 子数组是间断的;
  2. 也就是尽可能依照总和平均的将值调配到每一个数组中,且每个数组中起码有一个值, 所以最小值应该就是 max(nums[i]), 最大值是 sum(nums)
  3. 设计一个函数 check(max), 判断是否能切割出 m 个间断子数组,且值小于等于 max;如果能够,证实这个是一个较大值,能够持续向左侧迫近,找到一个更小的值;如果不能够,证实这个值 max 偏小了,需要求的值在右侧.
  4. 这里最须要留神的是,切割的子组件是间断的;同时每一个数组至多有一个值;
  5. 只有捋分明 check 这个函数,根本就能每次都切掉一半,间接拿到最初值了;
 var splitArray = function (nums, m) {
    //    先找到 left 和 right
    let left = 0,
      right = 0;
    for (let num of nums) {left = Math.max(num, left);
      right += num;
    }
      //  切割最大值不超过 max 的数组,如果切出来的数组数量少于 m,则证实能够切得更新,施展 true
    // 如果切除来的数组数量超出了 m, 证实只且 m 组的时候,最小值要超出 max 了,返回 false
    function check(max) {
      let ret = 0,
        sum = 0;
      let i = 0;
      while (i < nums.length) {sum += nums[i];
        if (sum >max) {// 一旦超出 max,则分组完结,sum 从新设置为 nums[i]
          ret++;
          sum = nums[i];
        }
        i++
      }
    //   如果最初还有剩,独自成团
      ret = sum ? ret + 1 : ret;
      return ret<=m
    }
    while (left <= right) {const mid = ((right - left) >> 1) + left;
      if (check(mid)) {
        //   如果能找到,向左迫近 -- right 最初失去的是一个不胜利的值,因为只有胜利它就要产生扭转
        right = mid - 1;
      } else {
        //  left 最终进来的时候,必定代表一个胜利的值
        left = mid + 1;
      }
    }

    return left;
  };

退出移动版