Posted at 2021-04-26Updated at 2021-04-27 算法算法数据结构 leetcode

贪心法用来解可由局部最优推出全局最优的问题。

# 基础

贪心法一般步骤：

将问题分解为子问题
找出适合的贪心策略
求子问题的最优解
局部最优堆叠为全局最优

# 实践

# 分发饼干

从最大的开始，依次试图满足孩子的胃口

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
    cookie := len(s) - 1
    count := 0
    for kid := len(g) - 1; kid >= 0; kid-- {
        if cookie >= 0 && s[cookie] >= g[kid] {
            count++
            cookie--
        }
    }
    return count
}

# 摆动序列

摆动序列

依次判断前后差值，当差值异号时计入统计，统一拓展至边界值，[2, 5]可以看做[2, 2, 5]是等价的，序列均为2。

func wiggleMaxLength(nums []int) int {
    lastDiff := 0
    curDiff := 0
    count := 1 // 1 by default
    for i := 1; i < len(nums); i++ {
        curDiff = nums[i] - nums[i - 1]
        if curDiff > 0 && lastDiff <= 0 || lastDiff >= 0 && curDiff < 0 {
            count++
            lastDiff = curDiff
        }
    }
    return count
}

# 最大子序和

最大子序和

暴力法

func maxSubArray(nums []int) int {
    max := math.MinInt64
    for i := 0; i < len(nums); i++ {
        count := 0
        for j := i; j < len(nums); j++ {
            count += nums[j]
            if count > max {
                max = count
            }
        }
    }
    return max
}

贪心，负数总会拉低总和，如果连续和已经为负数就应该立刻放弃。

func maxSubArray(nums []int) int {
    max := math.MinInt64
    count := 0
    for i := 0; i < len(nums); i++ {
        count += nums[i]
        if count > max {
            max = count
        }
        if count < 0 {
            count = 0
        }
    }
    return max
}

# 买卖股票的最佳时机 II

买卖股票的最佳时机 II

累加所有差为正的区间

func maxProfit(prices []int) int {
    curDiff := 0
    max := 0
    for i := 1; i < len(prices); i++ {
        curDiff = prices[i] - prices[i - 1]
        if curDiff > 0 {
            max += curDiff
        }
    }
    return max
}

# 跳跃游戏

跳跃游戏

计算下标+数值的最大值，如果下标大于最大值说明无法到达

func canJump(nums []int) bool {
    max := 0
    for i := 0; i < len(nums); i++ {
        if i > max {
            return false
        }
        if (nums[i] + i) > max {
            max = nums[i] + i
        }
    }
    return true
}

考虑覆盖，如果max已覆盖最后一个index，则直接返回

func canJump(nums []int) bool {
    max := 0
    if len(nums) == 1 {
        return true
    }
    for i := 0; i <= max; i++ {
        if (nums[i] + i) > max {
            max = nums[i] + i
        }
        if max >= len(nums) - 1 {
            return true
        }
    }
    return false
}

# 跳跃游戏II

跳跃游戏II

计算下标+数值的最大值，当当前下标不是最后一个下标时，最大步数总要+1，而两段部分重叠的区间，总可以2步走完。

func jump(nums []int) int {
    if len(nums) == 1 {
        return 0
    }
    cur := 0
    next := 0
    ans := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] + i > next {
            next = nums[i] + i
        }
        if i == cur {
            if cur != len(nums) - 1 {
                ans++
                cur = next
                if next >= len(nums) - 1 {
                    break
                }
            } else {
                break
            }
        }
    }
    return ans
}

# K 次取反后最大化的数组和

K 次取反后最大化的数组和

首先按绝对值从大到小排序，把K的次数用在翻转负数上，如果全部翻转完K>0，则全部用在绝对值最小的值上

type Arr []int
func (a Arr) Len() int           { return len(a) }
func (a Arr) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a Arr) Less(i, j int) bool { return abs(a[i]) > abs(a[j]) }

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func largestSumAfterKNegations(A []int, K int) int {
    sort.Sort(Arr(A))
    for i := 0; i < len(A); i++ {
        if A[i] < 0 {
            A[i] = -A[i]
            K--
        }
        if K == 0 {
            break
        }
    }
    if K > 0 {
        if K % 2 == 1 {
            A[len(A) - 1] = -A[len(A) - 1]
        }
    }
    sum := 0
    for _, a := range A {
        sum += a
    }
    return sum
}

# 加油站

加油站

贪心，如果gas总量小于cost则不能跑完，否则一定存在起始点，从0开始累加gas-cost差，如果累加和小于0，则之前站点不能作为起始站点，累加和清零，起始点一定出现在当前点或之后。

func canCompleteCircuit(gas []int, cost []int) int {
    sum := 0
    cur := 0
    start := 0
    for i, _ := range gas {
        cur += gas[i] - cost[i]
        sum += gas[i] - cost[i]
        if cur < 0 {
            cur = 0
            start = i + 1
        }
    }
    if sum < 0 {
        return -1
    }
    return start    
}

# 分发糖果

分发糖果

模拟暴力法，模拟发糖过程，如果当前评分低于前值，从当前位置向前补发糖果

func candy(ratings []int) int {
    if len(ratings) == 0 {
        return 0
    }
    candies := make([]int, len(ratings))
    candies[0] = 1
    for i := 1; i < len(ratings); i++ {
        if ratings[i - 1] < ratings[i] {
            candies[i] = candies[i - 1] + 1
        } else {
            candies[i] = 1
            for j := i; j > 0; j-- {
                if ratings[j] < ratings[j - 1] {
                    if candies[j - 1] <= candies[j] {
                        candies[j - 1] = candies[j] + 1
                    } else {
                        break
                    }
                } else {
                    break
                }
            }
        }
    }
    sum := 0
    for _, c := range candies {
        sum += c
    }
    return sum
}

贪心，先满足右边，再满足左边，满足左边时右边的条件也不能被破坏

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func candy(ratings []int) int {
    if len(ratings) == 0 {
        return 0
    }
    candies := make([]int, len(ratings))
    for i, _ := range candies {
        candies[i] = 1
    }
    for i := 1; i < len(ratings); i++ {
        if ratings[i] > ratings[i - 1] {
            candies[i] = candies[i - 1] + 1
        }
    }
    for i := len(ratings) - 2; i >= 0; i-- {
        if ratings[i] > ratings[i + 1] {
            candies[i] = max(candies[i], candies[i + 1] + 1)
        }
    }
    sum := 0
    for _, c := range candies {
        sum += c
    }
    return sum
}

# 柠檬水找零

柠檬水找零

模拟法，优先给10块

func lemonadeChange(bills []int) bool {
    left5 := 0
    left10 := 0
    for i := 0; i < len(bills); i++ {
        if bills[i] == 5 {
            left5++
        } else if bills[i] == 10 {
            if left5 >= 1 {
                left5--
                left10++
            } else {
                return false
            }
        } else if bills[i] == 20 {
            if left5 >= 1 && left10 >= 1 {
                left5--
                left10--
            } else if left5 >= 3 {
                left5 -= 3
            } else {
                return false
            }
        }
    }
    return true
}

# 根据身高重建队列

根据身高重建队列

先按身高从大到小排列，身高相同时，k按从小到大排列，再按k的序号顺序插入即可

type Arr [][]int
func (a Arr) Len() int           { return len(a) }
func (a Arr) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a Arr) Less(i, j int) bool {
    return a[i][0] > a[j][0] || a[i][0] == a[j][0] && a[i][1] < a[j][1] 
}

func reconstructQueue(people [][]int) [][]int {
    sort.Sort(Arr(people))
    // fmt.Printf("%v\n", people)
    queue := make([][]int, len(people))
    for i := 0; i < len(people); i++ {
        // fmt.Printf("%v\n", queue)
        pos := people[i][1]
        for j := i - 1; j >= pos; j-- {
            queue[j+1] = queue[j]
        }
        queue[pos] = people[i]
    }
    return queue
}

数组shift改成copy，好像并没有变快很多

type Arr [][]int
func (a Arr) Len() int           { return len(a) }
func (a Arr) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a Arr) Less(i, j int) bool {
    return a[i][0] > a[j][0] || a[i][0] == a[j][0] && a[i][1] < a[j][1] 
}

func reconstructQueue(people [][]int) [][]int {
    sort.Sort(Arr(people))
    // fmt.Printf("%v\n", people)
    queue := make([][]int, len(people))
    for i := 0; i < len(people); i++ {
        // fmt.Printf("%v\n", queue)
        pos := people[i][1]
        copy(queue[pos+1:],queue[pos:])
        queue[pos] = people[i]
    }
    return queue
}

# 用最少数量的箭引爆气球

用最少数量的箭引爆气球

先按气球左边界从小到大排序，再逐一引爆气球，如果当前气球的右边界小于前一个气球的左边界，则是重叠的，可以引爆，此时合二为一，取两者交集（右边界中较小的），反之，需要一只箭。

type Arr [][]int
func (a Arr) Len() int           { return len(a) }
func (a Arr) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a Arr) Less(i, j int) bool {
    return a[i][0] < a[j][0] || a[i][0] == a[j][0] && a[i][1] < a[j][1] 
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func findMinArrowShots(points [][]int) int {
    if len(points) == 0 { return 0 }
    sort.Sort(Arr(points))
    arrow := 1
    for i := 1; i < len(points); i++ {
        if points[i][0] > points[i-1][1] {
            arrow++
        } else {
            points[i][1] = min(points[i - 1][1], points[i][1])
        }
    }
    return arrow
}

# 无重叠区间

无重叠区间

先按左边界从小到大排序，再逐一判断是否交叠，如果当前左边界小于右边界，说明发生交叠，必须移除一个，此时选择右边界更小的局部最优解，尽量避免和其他区间交叠。

type Arr [][]int
func (a Arr) Len() int           { return len(a) }
func (a Arr) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a Arr) Less(i, j int) bool {
    return a[i][0] < a[j][0] || a[i][0] == a[j][0] && a[i][1] < a[j][1] 
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func eraseOverlapIntervals(intervals [][]int) int {
    if len(intervals) == 0 {
        return 0
    }
    sort.Sort(Arr(intervals))
    count := 0
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < intervals[i - 1][1] {
            count++
            intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])
        }
    }
    return count
}

# 划分字母区间

划分字母区间

先遍历找到每个字母的最远边界，再从头开始，如果当前字母的最远边界大于右边界，则将右边界更新为当前字母最远边界，如果遍历index等于右边界，说明右边界内所有值的最远程度均小于等于右边界，形成一个分割点。

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func partitionLabels(S string) []int {
    m := make([]int, 26)
    for i := 0; i < len(S); i++ {
        m[int(S[i]) - int('a')] = i
    }
    left := 0
    right := 0
    res := []int{}
    for i := 0; i < len(S); i++ {
        right = max(right, m[int(S[i]) - int('a')])
        if i == right {
            res = append(res, right - left + 1)
            left = right + 1
        }
    }
    return res
}

# 合并区间

合并区间

同区间重叠

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func merge(intervals [][]int) [][]int {
    res := [][]int{}
    if len(intervals) == 0 {
        return res
    }
  sort.Slice(intervals, func(i, j int) bool {
    return intervals[i][0] < intervals[j][0]
  })
    left := intervals[0][0]
    right := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] <= right {
            right = max(intervals[i][1], right)
        } else {
            res = append(res, []int{left, right})
            left, right = intervals[i][0], intervals[i][1]
        }
    }
    res = append(res, []int{left, right})
    return res
}

# 单调递增的数字

单调递增的数字

贪心策略，如果前一位较大，则将前一位减一，当前位置为9。

func monotoneIncreasingDigits(N int) int {
    num := []rune(fmt.Sprintf("%v", N))
    start := len(num)
    for i := len(num) - 1; i > 0; i-- {
        if num[i - 1] > num[i] {
            start = i
            num[i - 1] = rune(int(num[i - 1]) - 1)
        }
    }
    for i := start; i < len(num); i++ {
        num[i] = '9'
    }
    ret, _ := strconv.Atoi(string(num))
    return ret
}

# 监控二叉树

监控二叉树

贪心策略，为了最小化摄像头数量，叶子节点不放，根节点最好也不放，其余节点隔两个放一个，从叶子节点开始后序遍历。节点状态分为0无覆盖，1有摄像头，2有覆盖三种，空节点默认为有覆盖。

处理逻辑分为：

左右节点都有覆盖则返回无覆盖
左右至少有一个无覆盖则放置摄像头
左右节点至少有一个摄像头则返回有覆盖
根节点如果无覆盖则放置摄像头

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minCameraCover(root *TreeNode) int {
    count := 0
    var traverse func (node *TreeNode) int
    traverse = func (node *TreeNode) int {
        if node == nil {
            return 2
        }

        left := traverse(node.Left)
        right := traverse(node.Right)

        if left == 2 && right == 2 { return 0 }
        if left == 0 || right == 0 { 
            count++
            return 1
        }
        if left == 1 || right == 1 {
            return 2
        }
        return -1
    }

    if traverse(root) == 0 {
        count++
    }
    return count
}

Previous post: 算法基础 - 动态规划法 Next post: 烤面筋 - 算法

吹拉弹唱

# 基础

# 实践

# 分发饼干

# 摆动序列

# 最大子序和

# 买卖股票的最佳时机 II

# 跳跃游戏

# 跳跃游戏II

# K 次取反后最大化的数组和

# 加油站

# 分发糖果

# 柠檬水找零

# 根据身高重建队列

# 用最少数量的箭引爆气球

# 无重叠区间

# 划分字母区间

# 合并区间

# 单调递增的数字

# 监控二叉树