贪心算法

每一步选取当前最优解

问题能够分解成子问题，子问题最优解，递推到最终最优解

与动态规划区别：

贪心算法：每个子情况都进行选择，不能回退

动态规划：保存以前的运算结果，可以回退

PS： 关键点在于如何证明可以使用贪心算法，能得到想要的结果

例题

跳跃游戏

// 倒序贪心，从后开始，最先能跳到目标点的
func canJump(nums []int) bool {
    if len(nums) == 0 {
        return false
    }
    tmp := len(nums) - 1
    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] + i >= tmp {
            tmp = i
        }
    }
    // 看最后是不是0
    return tmp == 0
}

分发饼干

// 先进行排序，然后贪心
func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
    i, j, res := 0, 0, 0
    // 通过两个指针，进行移动
    for i < len(g) && j < len(s) {
        if s[j] < g[i] {
            j++
        } else {
            res += 1
            i++
            j++
        }
    }
    return res
}

跳跃游戏2

// jump ...
// 最少的跳跃次数，则从前开始贪心，每次跳最大步数
// 也就是从后开始，可以到达最后结果的最远步数，下标最小的那个
func jump(nums []int) int {
    count := 0
    tmp := len(nums) - 1
    for tmp > 0 {
        // 每次从头开始循环，找到最先满足的值，然后break，更新tmp
        // 每次都是最先满足，最优解，贪心算法
        for i := 0; i < tmp; i++ {
            if nums[i] + i >= tmp {
                count += 1
                tmp = i
                break
            }
        }
    }
    return count
}

// 优化贪心，减少for循环
// 从前往后找其每次能跳跃的最大步数，实现贪心
func jump(nums []int) int {
    count := 0
    end := 0
    maxTmp := 0
    // 一次循环
    for i := 0; i < len(nums) - 1; i++ {
        // 每次循环找其跳的最大步数
        maxTmp = max(maxTmp, nums[i] + i)
        // 遍历到end，说明要发生跳跃，加1，并更新end
        if i == end {
            count += 1
            end = maxTmp
        }
    }
    return count
}

柠檬水找零

// 两个指针记录5， 10的数量，通过，5，10，20的计算，每次循环判断数量小于0则false
func lemonadeChange(bills []int) bool {
    f, t := 0, 0
    for i := 0; i < len(bills); i++ {
        if bills[i] == 5 {f += 1}
        if bills[i] == 10 {
            t += 1
            f -= 1
        }
        if bills[i] == 20 {
            if t > 0 {
                t -= 1
                f -= 1
            } else {f -= 3}
        }
        if f < 0 || t < 0 {return false}
    }
    return true
}

买卖股票的最佳时机

// 每次循环，只要有收益就进行计算，完成收益累加
func maxProfit(prices []int) int {
    res := 0
    for i := 1; i < len(prices); i++ {
        if prices[i] > prices[i - 1] {
            res += prices[i] - prices[i - 1]
        }
    }
    return res
}

模拟机器人

// 记录障碍点为map
func robotSim(commands []int, obstacles [][]int) int {
    type p struct {
        x int
        y int
    }
    res := p{0, 0}
    maxRes := 0
    dire := 0
    obsMap := make(map[p]bool, len(obstacles))
    for i := 0; i< len(obstacles); i++ {
        tmp := p{obstacles[i][0], obstacles[i][1]}
        obsMap[tmp] = true
    }
    for _, v := range commands {
        // 步数行走
        if v > 0 {
            // 一步一步走，每步判断是否障碍点
            for i := 1; i <= v; i++ {
                // 临时点
                tmp := res
                // 结果往前走
                switch dire {
                case 3: res.x -= 1
                case 0: res.y += 1
                case 1: res.x += 1
                case 2: res.y -= 1
                }
                // 如果结果遇到障碍，则结果回到临时点
                if _, ok := obsMap[res]; ok {
                    res = tmp
                    break
                } else { // 没遇到则计算
                    if (res.x*res.x + res.y*res.y) > maxRes {
                        maxRes = res.x*res.x + res.y*res.y
                    }
                }
            }
        }
        // 处理方向，0北，1东，2南，3西，取余简单循环
        if v == -1 {
            dire = (dire + 1) % 4
        }
        if v == -2 {
            dire = (dire + 4 - 1) % 4
        }
    }
    return maxRes
}