贪心算法

[TOC]

局部最优解->全局最优

455. 分发饼干（简单/贪心）

// g是胃口，s是饼干
// 用大饼干优先满足胃口大的，并统计满足小孩数量。 https://leetcode.cn/problems/assign-cookies/solution/455-fen-fa-bing-gan-tan-xin-jing-dian-ti-o6k6/
func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)

    gLen := len(g)
    sLen := len(s)

    index := sLen - 1
    count := 0
    for i := gLen - 1; i > 0; i-- {
        if index >= 0 && s[index] >= g[i] {
            count++
            index--
        }
    }
    return count
}

392. 判断子序列（简单/贪心）

452. 用最少数量的箭引爆气球（中等/贪心）

// https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/solution/yong-zui-shao-shu-liang-de-jian-yin-bao-qi-qiu-1-2/
// 一定存在一种最优（射出的箭数最小）的方法，使得每一支箭的射出位置都恰好对应着某一个气球的右边界。
func findMinArrowShots(points [][]int) int {
    // 按照右边界进行排序
    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })

    fmt.Println(points)
    count := 1 // 必定有一只箭
    end := points[0][1] 
    for i := 1; i < len(points); i++ {
        if points[i][0] > end { //前一个气球重点 < 当前气球起点，则数量+1,这里注意是point[i][0],注意是 > 
            count++
            end = points[i][1] //  这里注意是point[i][1]
        }
    }
    return count
}

435. 无重叠区间（中等/贪心）

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    fmt.Println(intervals)
    count := 1
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= end { // /当区间的左边界大于上一个区间的右边界的时候 说明是一对不重合区间,注意是 >=
            count++
            end = intervals[i][1]
        }

    }
    return len(intervals) - count // //intervals的长度减去最多的不重复的区间 就是最少删除区间的个数
}

1167. 连接棒材的最低费用(贪心/小顶堆)

、、https://www.jianshu.com/p/80a3d7add522

type intHeap []int

func (key intHeap) Len() int {
    return len(key)
}

func (key intHeap) Less(i int, j int) bool {
    return key[i] < key[j]
}

func (key intHeap) Swap(i int, j int) {
    key[i], key[j] = key[j], key[i]
}

func (h *intHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *intHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func (h *intHeap) push(x int) {
    heap.Push(h, x)
}

func (h *intHeap) pop() int {
    return heap.Pop(h).(int)
}

func connectSticks(sticks []int) int {
    res := 0
    sticksHeap := intHeap{}
    sticksHeap = sticks
    heap.Init(&sticksHeap)
    for sticksHeap.Len() > 1 {
        first, second := sticksHeap.pop(), sticksHeap.pop()
        sticksHeap.push(first+second)
        res += first+second
    }   
    return res
}

860. 柠檬水找零(简单/其实感觉没用到贪心)

// 一开始我还想着利用map来存，我真是傻逼
func lemonadeChange(bills []int) bool {
    five, ten := 0, 0
    for _, bill := range bills {
        if bill == 5 {
            five++
        } else if bill == 10 {
            if five == 0 {
                return false
            }
            five--
            ten++
        } else {
            if five > 0 && ten > 0 {
                five--
                ten--
            } else if five >= 3 {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}

56. 合并区间 （中等/感觉和贪心也没啥关系）

// ================ 解法一 ====================================
func merge(intervals [][]int) [][]int {
    //先从小到大排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    //再弄重复的
    for i := 0; i < len(intervals)-1; i++ {
        // 当前右边界intervals[i][1]和下一区间左边界intervals[i+1][0]比较
        if intervals[i][1] >= intervals[i+1][0] {
            // 更新区间右边界最大值
            intervals[i][1] = max(intervals[i][1], intervals[i+1][1]) //赋值最大值
            // 删除下一个区间元素，因为此时当前区间右边界已经变了
            intervals = append(intervals[:i+1], intervals[i+2:]...) // 很重要，删除i+1这一行
            i--
        }
    }
    return intervals
}

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

//  ====================  解法二(其实就是硬写，挺好理解的)  ============================
func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    var res [][]int
    start, end := intervals[0][0], intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] <= end {
            if intervals[i][1] > end {
                end = intervals[i][1]
            }
        } else {
            res = append(res, []int{start, end})
            start, end = intervals[i][0], intervals[i][1]
        }
    }
    return append(res, []int{start, end})
}

55 跳跃游戏

跳跃游戏 II

122. 买卖股票的最佳时机 II（中等/贪心）

/*
res =  (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])
    =  prices[3] - prices[0]
按照贪心算法，在下标为 1、2、3 的这三天，我们做的操作应该是买进昨天的，卖出今天的。
等价于：在下标为 0 的那一天买入，在下标为 3 的那一天卖出。
贪心算法的直觉：由于不限制交易次数，只要今天股价比昨天高，就交易。
*/

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

数组拆分 I

1710. 卡车上的最大单元数（简单/贪心）

func maximumUnits(boxTypes [][]int, truckSize int) int {
    sort.Slice(boxTypes, func(i, j int) bool {
        return boxTypes[i][1] > boxTypes[j][1]
    })
    res := 0
    for _, v := range boxTypes {
        size := min(truckSize, v[0])
        res += size * v[1]
        truckSize -= size
    }
    return res
}

1217. 玩筹码(简单/贪心)

交换字符使得字符串相同

构造 K 个回文字符串

921. 使括号有效的最少添加（中等/贪心）

func minAddToMakeValid(S string) int {
    //left, right 分别表示左右未配对的括号
    left, right := 0, 0
    for _, s := range S {
        if s == '(' {
            left++
        } else if left > 0 && s == ')' {
            left--
        } else {
            right++
        }
    }
    return left + right
}

1029. 两地调度（中等/贪心）

// 思路很重要：
我们这样来看这个问题，公司首先将这 2N 个人全都安排飞往 B 市，
再选出 N 个人改变它们的行程，让他们飞往 A 市。
如果选择改变一个人的行程，那么公司将会额外付出 price_A - price_B 的费用，这个费用可正可负。
因此最优的方案是，选出 price_A - price_B 最小的 N 个人，让他们飞往 A 市，其余人飞往 B 市。
func twoCitySchedCost(costs [][]int) int {
    sort.Slice(costs, func(i, j int) bool {
        return (costs[i][0] - costs[i][1]) > (costs[j][0] - costs[j][1])
    })

    cost := 0
    for i := 0; i < len(costs)/2; i++ { // 去B城市的
        cost += costs[i][1]
    }

    for i := len(costs) / 2; i < len(costs); i++ { // 去A城市的
        cost += costs[i][0]
    }

    return cost
}

给定行和列的和求可行矩阵

分发糖果

最大子序和（不算贪心题吧）

280. 摆动排序 (会员/中等/贪心)

单调递增的数字

移掉 K 位数字

翻转矩阵后的得分

555. 分割连接字符串（会员/中等/贪心）

2144. 打折购买糖果的最小开销（简单/贪心）

func minimumCost(cost []int) int {
    sort.Sort(sort.Reverse(sort.IntSlice(cost)))
    res := 0
    for i := range cost {
        if i%3 != 2 {
            res += cost[i]
        }
    }
    return res
}

2098. 长度为 K 的最大偶数和子序列（会员/中等/贪心）

给你一个整数数组 nums 和一个整数 k 。找出 nums 长度为 k 的所有子序列中的 最大偶数和 。
返回此总和，如果此总和不存在，则返回 -1。
子序列 是一个数组，可以通过删除一些元素或不删除任何元素而从另一个数组派生，而不改变其余元素的顺序。

输入: nums = [4,1,5,3,1], k = 3
输出: 12
解释:
具有最大可能偶数和的子序列是[4,5,3]。它的和为 4 + 5 + 3 = 12

/*
思路：
1、先降序排序，计算前K个数的和，如果是偶数，直接返回结果。如果是奇数，往下。
2、求前k个数中， 最小的奇数和偶数
3、求后n-k个数中最大的奇数和偶数
4、前k个数和为奇数，故减去其中最小的奇/偶数，加上后n-k个数中最大的偶/奇数，两个值返回最大
*/
func largestEvenSum(nums []int, k int) int64 {

    sort.Sort(sort.Reverse(sort.IntSlice(nums)))

    tempSum := 0
    for i := 0; i < k; i++ {
        tempSum += nums[i]
    }

    if tempSum%2 == 0 {
        return int64(tempSum)
    }

    minOdd := math.MaxInt32
    minEven := math.MaxInt32

    for i := 0; i < k; i++ {
        if nums[i]%2 != 0 && nums[i] < minOdd { //奇数
            minOdd = nums[i]
        }

        if nums[i]%2 == 0 && nums[i] < minEven {
            minEven = nums[i]
        }
    }

    maxOdd := math.MinInt32
    maxEven := math.MinInt32

    for i := k; i < len(nums); i++ {
        if nums[i]%2 != 0 && nums[i] > maxOdd { //奇数
            maxOdd = nums[i]
        }

        if nums[i]%2 == 0 && nums[i] > maxEven {
            maxEven = nums[i]
        }
    }

    // 前k个数和为奇数，故减去其中最小的奇/偶数，加上后n-k个数中最大的偶/奇数，两个值返回最大，这两个值也可能不存在
    ans1 := -1
    ans0 := -1
    if minOdd != math.MaxInt32 && maxEven != math.MinInt32 {
        ans1 = tempSum + maxEven - minOdd
    }
    if minEven != math.MaxInt32 && maxOdd != math.MinInt32 {
        ans0 = tempSum + maxOdd - minEven
    }
    return max(ans0, ans1)  // 不存在就返回-1
}

624. 数组列表中的最大距离(会员/中等/贪心)

给定 m 个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离