# 贪心

# 思想

在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，它所做出的是某种意义上的局部最优解。

# 题目

# 剪绳子 (opens new window)

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n 都是整数，n > 1 并且 m > 1），每段绳子的长度记为 k[i]，请问每段绳子可能的最大乘积是多少？

# 思路

力扣原题给出了提示：多试试几个例子，找出规律。下面说说我找到的规律。

前面提到：8 可以拆分成 3 + 3 + 2，此时乘积最大，以此推测出一个整数要拆成多个 2 和 3 的和，保证乘积最大。原理很容易理解，因为 2 和 3 可以合成任何数字，例如 5 = 3 + 2，但是 5 < 3 * 2；例如 6 = 3 + 3，但是 6 < 3 * 3。所以根据贪心算法，就尽量将原数拆成更多的 3，然后再拆成更多的 2，保证拆出来的整数的乘积结果最大。

但是上面的解法仍然有不足之处。如果整数是 3k + 1 的形式，例如 7，按照上面的规则会拆成 7 = 3 + 3 + 1，但是在乘法中，1 是不起作用的，此时应将最后一个 1 和 3 相加成 4，然后再对 4 进行 2 的拆分，得到的乘积最大。

综上所述，算法的整体思路为：

n 除以 3 的结果为 a，余数为 b；
当 b 为 0 时，直接将 a 个 3 相乘；
当 b 为 1 时，将 (a - 1) 个 3 相乘，再乘以 4；
当 b 为 2 时，将 a 个 3 相乘，再乘以 2。

空间复杂度为 O(1)，时间复杂度为 O(1)。

# 答案

function cuttingRope(n: number): number {
  if(n === 2) return 1
  if(n === 3) return 2
  
  const a = Math.floor(n / 3)
  const b = n % 3
  
  if(b === 0) return Math.pow(3, a)
  if(b === 1) return Math.pow(3, a - 1) * 4
  return Math.pow(3, a) * 2
}

# 跳跃游戏 (opens new window)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够达到最后一个位置。

# 思路

使用一个变量保存当前可到达的最大位置
时刻更新最大位置
可达位置小于数组长度返回 false，否则可以到达

# 答案

function canJump(nums: number[]): boolean {
  let k = 0
  for(let i = 0; i < nums.length; i++) {
    if(i > k) return false
    k = Math.max(k, nums[i] + i)
  }
  return true
}

# 加油站 (opens new window)

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升

你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i + 1 个加油站需要消耗汽油 cost[i] 升，你从其中一个加油站出发，开始时又想为空。

如果你可以环绕环路形式一周，则返回出发时加油站的编号，否则返回 -1。

# 思路

gas - cost >= 0 才能绕场一周，以此思想判断能否行驶一周
从正确初始位置开始，拥有的汽油总是比消耗的汽油多，以此思想寻找初始位置

# 答案

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let cur = 0, total = 0, start = 0
  for(let i = 0; i < gas.length; i++) {
    total += gas[i] - cost[i]
    if(cur < 0) {
      cur = gas[i] - cost[i]
      start = i
    } else {
      cur += gas[i] - cost[i]
    }
  }
  
  return total >= 0 ? start : -1
}

← 矩阵.md 链表.md →