17 算法

// 1.1 new Set() 创建一个空的 Set
const set = new Set()

// 1.2 可以通过传递一个可迭代对象（如数组）来初始化 Set。
const set = new Set([1, 2, 3, 4])

// 2 唯一性: Set 只存储唯一的值。如果尝试添加已经存在的值，add 操作将被忽略。
set.add(5)

// 3 大小: 使用 size 属性可以获取 Set 中值的数量。
const setSize = set.size()

// 4 判断值是否存在: 使用 has 方法可以检查值是否存在于 Set 中。
const hasVal = set.has(2) // true

// 5 删除: 使用 delete 方法可以删除 Set 中的特定值。
set.delete(2)

// 6 清空: 使用 clear 方法可以清空整个 Set。
set.clear()

// 7 迭代: Set 是可迭代的，可以使用 for...of 循环或 forEach 方法进行迭代

for (const item of set) {
  console.log(item)
}

set.forEach((item) => {
  console.log(item)
})

// 8 转换为数组: 可以使用 Array.from 或者扩展运算符 ... 将 Set 转换为数组
const arrayFromSet = Array.from(set)
const arraySpread = [...set]

function binarySearch(nums, target) {
  let left = 0,
    right = nums.length - 1
  while (left <= right) {
    const mid = Math.floor((right - left) / 2) // 向下取整
    if (nums[mid] === target) {
      return true
    } else if (nums[mid] < target) {
      // 向右切
      left = mid + 1
    } else {
      // 向左切
      right = mid - 1
    }
  }
  return -1
}

function removeDuplicates(nums) {
  // 边界检测
  if (nums.length <= 1) return nums.length

  let slow = 0,
    fast = 0

  while (fast < nums.length) {
    // 检测快慢指针是否相同
    if (nums[slow] !== nums[fast]) {
      // 俩数不同, 慢指针开始移动
      nums[++slow] = nums[fast]
    }

    fast++
  }

  return slow + 1
}

const traverse = function (root) {
  if (root === null) {
    return
  }
  // 前序位置
  traverse(root.left)
  // 中序位置
  traverse(root.right)
  // 后序位置
}

function maxDepth(root) {
  if (root == null) return 0

  const leftDepth = maxDepth(root.left)
  const rightDepth = maxDepth(root.right)

  return Math.max(leftDepth, rightDepth) + 1
}

function levelTraverse(root) {
  if (root == null) return

  const queue = [] // 维护状态数组
  queue.push(root) // 初始化

  while(queue.length > 0) {
    const curLevelNodeSize = queue.length
    for (let ind = 0; ind < curLevelNodeSize, ind++) {
      const curNode = queue.shift() // 取出当前节点

      if (curNode.left) queue.push(curNode.left)
      if (curNode.right) queue.push(curNode.right)
    }
  }
}

function jump(n) {
  if (n === 1) return 1
  if (n === 2) return 2

  return jump(n - 1) + jump(n - 2)
}

function jump(n) {
  if (n === 1) return 1
  if (n === 2) return 2

  const arr = []
  arr[1] = 1
  arr[2] = 2

  for (let i = 3; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2]
  }

  return arr[n]
}

function multipleBackpack(n, V, w, v, s) {
  const dp = Array.from({ length: V + 1 }, () => 0)
  for (let i = 0; i < n; i++) {
    // 1. 遍历物品
    for (let j = V; j >= w[i]; j--) {
      // 2. 遍历容量（从大到小）
      for (let k = 0; k <= s[i]; k++) {
        // 3. 遍历个数(从 0 到 s[i], 多出这一步)
        if (j >= k * w[i]) {
          dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i])
        }
      }
    }
  }
  return dp[V]
}

// dp[i][j][0] 表示第 i 天【不持有】股票的最大利润
// dp[i][j][1] 表示第 i 天【持有】股票的最大利润

dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]) // 今天不持有 = 昨天不持有 or 今天卖出
dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]) // 今天持有 = 昨天持有 or 今天买入

// 注意, 买入时要消耗一次交易机会，所以买入状态依赖 dp[i-1][j-1][0]。
// 卖出时不增加交易次数，所以卖出状态依赖 dp[i-1][j][1]。

function maxProfit(prices) {
  const dp = Array.from({ length: prices.length }, () => [0, 0])
  dp[0][0] = -prices[0]
  for (let i = 1; i < prices.length; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], -prices[i])
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])
  }
  return dp[prices.length - 1][1]
}

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) // 今天不持有
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) // 今天持有

var maxProfit = function (prices) {
  // 两笔交易: 不操作 买入1 卖出1 买入2 卖出2
  const n = prices.length
  const dp = Array.from({ length: prices.length }, () => [0, 0, 0, 0, 0])
  dp[0][1] = -prices[0]
  dp[0][3] = -prices[0]
  for (let i = 1; i < n; i++) {
    dp[i][0] = dp[i - 1][0]
    // 只买一次
    dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1])
    // 只卖一次
    dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2])
    // 买俩次 卖一次
    dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3])
    // 卖俩次
    dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4])
  }
  // 返回俩次卖出结果
  return dp[n - 1][4]
}

var maxProfit = function (k, prices) {
  const n = prices.length
  if (n === 0) return 0

  const dp = Array.from({ length: n }, () => new Array(2 * k + 1).fill(0))

  // 初始化买入状态: 奇数 2k-1买入, 偶数2k卖出
  for (let j = 1; j <= k; j++) {
    dp[0][2 * j - 1] = -prices[0]
  }

  for (let i = 1; i < n; i++) {
    for (let j = 1; j <= k; j++) {
      // 买入
      dp[i][2 * j - 1] = Math.max(
        dp[i - 1][2 * j - 1],
        dp[i - 1][2 * j - 2] - prices[i]
      )
      // 卖出
      dp[i][2 * j] = Math.max(
        dp[i - 1][2 * j],
        dp[i - 1][2 * j - 1] + prices[i]
      )
    }
  }

  return dp[n - 1][2 * k]
}

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
  // 排列组合, 先物品后容量 dp完全背包, 从小到大
  const dp = Array.from({ length: amount + 1 }, () => 0)
  dp[0] = 1 // 凑成 0 元只有 1 种方法（什么都不选）
  for (let i = 0; i < coins.length; i++) {
    // 外层遍历物品
    for (let j = coins[i]; j < amount + 1; j++) {
      // 内层遍历容量
      dp[j] += dp[j - coins[i]] // dp[j] = 凑成 j 的方案数
    }
  }
  return dp[amount]
}

function combinationSum(nums, target) {
  const res = []
  nums.sort((a, b) => a - b) // 先排序，方便提前剪枝

  const backtrack = (start, currentCombination, currentSum) => {
    // 找到目标
    if (currentSum === target) {
      res.push([...currentCombination])
      return
    }

    // 回溯
    for (let i = start; i < nums.length; i++) {
      // 提前减枝
      if (currentSum + nums[i] > target) break
      currentCombination.push(nums[i])
      backtrack(i, currentCombination, currentSum + nums[i]) // 递归允许重复选当前数
      currentCombination.pop() // 撤销选择
    }
  }

  backtrack(0, [], 0)
  return res
}

// 示例用法
const nums = [2, 3, 6, 7]
const target = 7
console.log(combinationSum(nums, target))
// 输出: [[2, 2, 3], [7]]

function sortVersions(versions = []) {
  return versions.sort((a, b) => {
    const aArr = a.split('.').map(Number)
    const bArr = b.split('.').map(Number)
    const maxLen = Math.max(aArr.length, bArr.length)

    for (let i = 0; i < maxLen; i++) {
      const curA = aArr[i] ?? 0
      const curB = bArr[i] ?? 0
      if (curA !== curB) {
        return curA - curB
      }
    }
    // 相等
    return 0
  })
}

// 测试
const versions = ['1.5.1', '1.45.0', '1.5', '6', '3.3.3.3.3.3.3']
const sorted = sortVersions(versions)
console.log(sorted)

function runTask(taskArr = [], num = 2) {
  let index = 0
  let runningTask = 0
  const result = new Array(taskArr.length)

  return new Promise((resolve) => {
    const next = () => {
      if (index >= taskArr.length && runningTask === 0) {
        resolve(result)
        return
      }

      while (runningTask < num && index < taskArr.length) {
        const currentIndex = index++
        const curTask = taskArr[currentIndex]
        runningTask++

        curTask()
          .then((res) => {
            result[currentIndex] = res
          })
          .catch((err) => {
            result[currentIndex] = err
          })
          .finally(() => {
            runningTask--
            next()
          })
      }
    }

    next()
  })
}

const tasks = [
  () => new Promise((res) => setTimeout(() => res('A'), 1000)),
  () => new Promise((res) => setTimeout(() => res('B'), 2000)),
  () => new Promise((res) => setTimeout(() => res('C'), 500)),
  () => new Promise((res) => setTimeout(() => res('D'), 1500)),
]

runTask(tasks, 2).then(console.log) // ["A", "B", "C", "D"]

function chunks(ips, num) {
  const arr = []
  for (let i = 0; i < ips.length; i = i + num) {
    arr.push(ips.slice(i, i + num))
  }
  return arr
}

function raceChunk(chunk, maxTime) {
  return new Promise((resolve) => {
    const controller = new AbortController()
    const signal = controller.signal

    // 设定超时, 没有比当前时间短的
    const timeout = setTimeout(() => controller.abort(), maxTime)

    // 开始并发请求
    const startTime = new Date()
    const promises = chunk.map((ip) =>
      fetch(ip, { signal }).then(() => ({
        rttTime: new Date() - startTime,
        ip,
      }))
    )

    Promise.race(promises)
      .then((result) => {
        resolve(result)
        // 取消其它请求
        controller.abort()
        clearTimeout(timeout)
      })
      .catch(() => resolve(null)) // 处理所有 fetch 失败的情况
  })
}

async function findShortestRTT(ips, num = 5) {
  // 分组
  const ipChunks = chunks(ips, num)
  let result = {
    rttTime: Infinity,
    ip: '',
  }

  for (const chunk of ipChunks) {
    const temp = await raceChunk(chunk, result.rttTime)
    if (temp) {
      result = temp
    }
  }

  return result.ip
}