学习笔记

贪心算法

概念：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
局限性：当下最优最终全局不一定最优，所以一般是在某一步使用贪心算法然后再全局加上一个搜索递归或者是动态规划等结合使用。
贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。
一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
贪心算法的难点是你怎么证明它是能够使用贪心算法的
适用贪心算法的场景
1. 简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。
2. 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

练习题

柠檬水找零
最佳买卖时间
分饼干
跳跃游戏
跳跃游戏II

二分查找

3个前提条件
1. 目标函数单调性（单调递增或者递减）
二分的数据必须是有序的，这样可以通过它的某些特征排除掉比如说前半部分或者后半部分
1. 存在上下界（bounded)
2. 能够通过索引访问（index accessible)

代码模板

left,right = 0,len(array)-1
while left <= right :
    mid = (left + right)/2
    if array[mid] == target :
        # find the target !!
        break or return result
    elif array[mid] < target :
        left = mid + 1
    else :
        right = mid -1

实战步骤

先写好二分查找模板，把变量全部带入填写好再写详细逻辑
看实际情况用不用 mid+- 1
mid = (left + right) / 2 在强类型的语言中可能导致数字越界，那么可以采用 mid = left + (right - left) / 2

练习题

x的平方根
有效的完全平方数
扩展牛顿迭代法