🔥刷题之探索最优解 WIP

DANGER

WIP

正在创作

绳子盖住的最多点 WIP

一、题目描述：给定一个有序数组arr 从左到右依次表示X轴上从左往右点的位置，给定一个正整数k，返回如果有一根长度为k的绳子，最多能盖住几个点，绳子的边缘点碰到X轴上的点，也算盖住。示例：示例 1：输入：arr = [1, 5, 13, 14, 15, 32, 43], k = 2 输出：3 示例 2：输入：arr = [1, 5, 13, 14, 15, 32, 43], k = 5 输出：3

// 方法一：
function rope(arr, k) {
  let res = 1
  for (let i = 0; i < arr.length; i++) {
    let near = Dichotomous(arr, i, arr[i] - k) // 求数组中大于等于arr[i]-k的最小数
    res = Math.max(res, i - near + 1)
  }
  return res
}

function Dichotomous(arr, r, value) {
  let index = r
  let l = 0
  while (l < r) {
    let mid = Math.floor((l + r) / 2)
    if (arr[mid] >= value) {
      r = mid - 1
      index = mid
    } else {
      l = mid + 1
    }
  }
  return index
}
// 方法二：
function rope(arr, k) {
  let l = 0,
    r = 0,
    n = arr.length
  max = 0
  while (l < n) {
    while (r < n && arr[r] - arr[l] <= k) r++
    max = Math.max(max, r - l++)
  }
  return max
}

// 方法一：
function rope(arr, k) {
  let res = 1
  for (let i = 0; i < arr.length; i++) {
    let near = Dichotomous(arr, i, arr[i] - k) // 求数组中大于等于arr[i]-k的最小数
    res = Math.max(res, i - near + 1)
  }
  return res
}

function Dichotomous(arr, r, value) {
  let index = r
  let l = 0
  while (l < r) {
    let mid = Math.floor((l + r) / 2)
    if (arr[mid] >= value) {
      r = mid - 1
      index = mid
    } else {
      l = mid + 1
    }
  }
  return index
}
// 方法二：
function rope(arr, k) {
  let l = 0,
    r = 0,
    n = arr.length
  max = 0
  while (l < n) {
    while (r < n && arr[r] - arr[l] <= k) r++
    max = Math.max(max, r - l++)
  }
  return max
}

总结：在解决问题的基础上，再进行优化。方法一使用二分复杂度为O(nlogn)，使用窗口法就可以将复杂度将为O(n)。

🔥刷题之探索最优解 WIP #

绳子盖住的最多点 WIP #

🔥刷题之探索最优解 WIP

绳子盖住的最多点 WIP