贪心算法.md

# 贪心
## 思想
在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，它所做出的是某种意义上的局部最优解。
## 题目
### [剪绳子](https://leetcode-cn.com/problems/jian-sheng-zi-lcof/)
> 给你一根长度为 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 的拆分，得到的乘积最大。
综上所述，算法的整体思路为：
1. n 除以 3 的结果为 a，余数为 b；
2. 当 b 为 0 时，直接将 a 个 3 相乘；
3. 当 b 为 1 时，将 (a - 1) 个 3 相乘，再乘以 4；
4. 当 b 为 2 时，将 a 个 3 相乘，再乘以 2。
空间复杂度为 O(1)，时间复杂度为 O(1)。
#### 答案
```typescript
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
}
```
### [跳跃游戏](https://leetcode-cn.com/problems/jump-game/)
> 给定一个非负整数数组，你最初位于数组的第一个位置。
>
> 数组中每个元素代表你在该位置可以跳跃的最大长度。
>
> 判断你是否能够达到最后一个位置。
#### 思路
1. 使用一个变量保存当前可到达的最大位置
2. 时刻更新最大位置
3. 可达位置小于数组长度返回 false，否则可以到达
#### 答案
```typescript
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
}
```
### [加油站](https://leetcode-cn.com/problems/gas-station/)
> 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升
>
> 你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i + 1 个加油站需要消耗汽油 cost[i] 升，你从其中一个加油站出发，开始时又想为空。
>
> 如果你可以环绕环路形式一周，则返回出发时加油站的编号，否则返回 -1。
#### 思路
1. gas - cost >= 0 才能绕场一周，以此思想判断能否行驶一周
2. 从正确初始位置开始，拥有的汽油总是比消耗的汽油多，以此思想寻找初始位置
#### 答案
```typescript
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
}
```