首先了解一下什么是贪心算法
贪心算法
指在寻求一个问题的解决时，将问题1)分解为多个阶段，每个阶段都基于当前问题所处的状态2)寻求该阶段的最优解，然后将3)各阶段的最优解组合形成整个问题的一个解决
通俗地说，贪心 = 走一步，看一步， 只顾眼前
贪心算法的特点 - 局部最优
因为每一步只关心眼前的利益，因此产生的是局部最优；而往往局部最优的组合并不是全局最优。贪心只能产生局部最优解
贪心算法的应用 - 求 局部解和是否解
- 求某些问题的局部解。面对NP问题（Non-deterministic Polynomial，即多项式复杂度的非确定性问题关于NP问题可参考这里）时，由于求全局最优解的时间复杂度为非多项式级，会相当耗费资源，因此往往使用高效省资源的贪心算法求得一个局部最优解去逼近或者说替代全局最优解。人生其实就是一个不断使用贪心算法的过程，因为我们无法预知一生中的种种情况，不可能穷举出所有的情况然后寻找一条最优的路径，显然，求人生最优解的复杂度是非多项式级的；因此我们不断地贪心，选择走对现在的我们而言最好的路
- 求某些问题的是否解。即我们不关心我们的解是否是最优，而只关心我们能否找到问题的一个解，问题能够得到解决究竟是“是”还是“否”，经常可以使用贪心算法，通过找出问题的一个解，证明问题是可解的
贪心算法的例子
- 集合覆盖问题（局部解问题）
存在如下表所示的广播台，以及广播台信号可以覆盖的地区。 选择最少的广播台，让所有的地区都可以接收到信号
- 集合覆盖问题（局部解问题）
| 广播台 | 覆盖地区 | 备注 |
|---|---|---|
| K1 | ID,NV,UT | |
| K2 | WA,ID,MT | |
| K3 | OR,NV,CA | |
| K4 | NV,UT | |
| K5 | CA,AZ |
统计出来，所有的地区是ID,NV,UT,WA,MT,OR,CA,AZ共8个。如何找出覆盖所有地区的广播台的集合？
常规的想法也是最暴力的想法就是穷举，列出所有可能的广播台集合，当存在n个广播台时，容易知道这一共有 2n个这样的集合，这显然是一个幂级而非多项式级的问题，即NP问题。当n为20时，就需要计算220 = 1024 * 1024 次，这是相当可怕的。因此，当面对NP问题时，我们常常使用贪心算法，求局部最优，减少指数级的计算量
基于贪心的思想，我们可以
A)明确当前未覆盖的地区 和 可选择的广播台
B)基于未覆盖地区，从可选广播台中，选取覆盖地区最多的广播台
如此循环，直到未覆盖地区为空
这样得到的解或许不是全局最优的，但是从最坏的情况来看，时间复杂度也降低到O(n2) (即进行n次循环，每一次循环都要扫描一次当前可选择的广播台)......代码就不贴了，思路都比较简单
- 跳跃问题（是否解问题）这是leetcode中的一道题
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置
注意到题目求“是否”可达，那么可以尝试使用贪心算法，快速找到一条可达路径求解
贪心：
从后往前遍历数组，每次寻找上一个最近的可达元素：
- 如果遇到的元素可以到达最后一个元素，则截断后边的元素，因为从该元素总能跳到最后；将当前元素作为新数组的最后一个元素，从而不断减小问题规模
- 否则继续往前，如果最后剩下的元素大于1个，则判断为假，否则为真。时间复杂度O(n)
'''
伪代码：
用指针j指向当前阶段的末位元素，用指针i从j-1的位置开始从后向前扫描，不断更新j直到j为0时停止
（循环） 当 j > 0 时：
（循环） 指针i从j-1的位置开始从后向前扫描：
如果找到一个i能够跳到j，那么停止扫描并且更新j的值，结束本层循环
如果找不到这样的i，即i为负数，向前溢出，则返回False
如果跳出了j的循环，说明j为0，返回True
'''
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
j = len(nums) - 1
# j == 0 是循环跳出的条件，当指针j为0时，说明已经从后向前寻找到首个元素
while j > 0:
i = j - 1
while i >= 0:
# 如果可达，
if nums[i] + i >= j:
j = i
break
# 不可达，继续向前搜索
else:
i -= 1
# 如果指针i向前溢出，说明找不到j前面的元素可以跳到j
if i < 0:
return False
return True
成绩：
执行用时 :88 ms, 在所有 Python 提交中击败了87.11%的用户
内存消耗 :13.3 MB, 在所有 Python 提交中击败了39.94%的用户
另解：
这是我最开始的解法。容易发现当数组里所有的数都是正数时，显然可以跳到最后，因此问题出在数字0的身上。当数组中有0时，我们要观察0前面的数是否可以越过它，如果不能越过，则返回False。
需要注意的是，这种方法的边界情况需要仔细考虑，注意当末位为0时，前面位置的元素不必要越过它，到达即可。这种方法我一共提交了3次代码。我第二次提交代码时就没有考虑到这一点，导致部分测试用例通不过。下面是代码实现，除去注释其实也很短
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
j = len(nums)-1
# 当数组至少有2个元素时（因为当数组长度为1时，直接满足，第一次提交时未考虑，导致[0]输出了False
while j > 0:
now = nums[j]
# 如果某位为0，检查前面的位置是否可以越过它;不为0，再往前搜索上一个0
# 注意当末位为0时，前面位置的元素不必要越过它，到达即可，这在第二次提交时未考虑
if now == 0:
for i in range(j):
# 如果存在一个位置能越过0，将j指向i
if i + nums[i] > j or (i + nums[i] == j and j == len(nums)-1):
j = i
break
# 否则，返回False
else:
if i == j-1:
return False
continue
# 该位置不为0，再往前搜索上一个0
else:
j -= 1
# 考虑首个元素为0的边界情况
if j == 0 and nums[0] == 0:
return False
# 如果顺利跳出循环，实现大会师，返回True
return True
成绩：
执行用时 :72 ms, 在所有 Python 提交中击败了99.33%的用户
内存消耗 :13.3 MB, 在所有 Python 提交中击败了43.52%的用户
NOTE:
关于解是否问题的小体会。解是否问题，基本上循环是必须的，我们需要在循环里面去判断是否满足我们的条件
那么，return False要写在循环体内，一旦不满足条件马上返回False；而return True则写在循环体外，因为只要跳出了循环，说明成功通过了每一次循环的判断
这点东西拖了2天T_T
本文内容为作者原创，未经允许禁止转载
