『代码随想录』贪心（Greedy）

DAY 31

分发饼干

遍历每块饼干，尝试将其分配给胃口最小的那个尚未满足的孩子

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
    n, m := len(g), len(s)
    i, j := 0, 0

    for i < n && j < m {
        if s[j] >= g[i] {
            i++
        }
        j++
    }
    return i
}

摆动序列

直接找出山峰和山谷就行，那些山腰的元素全都不要

func wiggleMaxLength(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }

    prev := nums[1] - nums[0]
    ans := 2
    if prev == 0 {
        ans = 1
    }

    for i := 2; i < n; i++ {
        diff := nums[i] - nums[i-1]
        if diff > 0 && prev <= 0 || diff < 0 && prev >= 0 {
            ans++
            prev = diff
        }
    }
    return ans
}

最大子数组和

这道题按理来说应该使用 dp，但是既然要用贪心，那就写写贪心的（

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小

func maxSubArray(nums []int) int {
    n := len(nums)
    ans := math.MinInt
    sum := 0
    for i := 0; i < n; i++ {
        sum += nums[i]
        ans = max(ans, sum)
        if sum < 0 {
            sum = 0
        }
    }
    return ans
}

DAY 32

买卖股票的最佳时机 II

这道题照理来说也应该使用 dp （

贪心的思想是，只要今天的价格比昨天的价格高，就假设我们昨天买入，今天卖出，从而获得利润

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

跳跃游戏

每一步都尽可能远更新覆盖范围

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

跳跃游戏 II

需要维护两个区间范围

func jump(nums []int) int {
    n := len(nums)
    curr, next, ans := 0, 0, 0

    for i := 0; i < n-1; i++ {
        next = max(nums[i]+i, next)
        if i == curr {
            curr = next
            ans++
        }
    }
    return ans
}

DAY 33

周日休息

DAY 34

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

尽量将负数转为正数

func largestSumAfterKNegations(nums []int, k int) int {
    n := len(nums)
    sort.Ints(nums)

    for i := 0; i < n && nums[i] < 0 && k > 0; i, k = i+1, k-1 {
        nums[i] = -nums[i]
    }
    if k == 0 {
        return getSum(nums)
    }
    sort.Ints(nums)
    for k != 0 {
        nums[0] = -nums[0]
        k--
    }
    return getSum(nums)
}

func getSum(nums []int) int {
    ans := 0
    for _, val := range nums {
        ans += val
    }
    return ans
}

加油站

func canCompleteCircuit(gas []int, cost []int) int {
    n := len(gas)
    diff := make([]int, n)
    for i := 0; i < n; i++ {
        diff[i] = gas[i] - cost[i]
    }

    ans, i, sum, totalSum := 0, 0, 0, 0
    for ; i < n; i++ {
        sum += diff[i]
        totalSum += diff[i]
        if sum < 0 {
            sum = 0
            ans = i + 1
        }
    }

    if totalSum < 0 {
        return -1
    }
    return ans
}

分发糖果

感觉有点像接雨水，要考虑左边也要考虑右边

func candy(ratings []int) int {
    n := len(ratings)
    need := make([]int, n)
    for i := 0; i < n; i++ {
        need[i] = 1
    }
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            need[i] = need[i-1] + 1
        }
    }
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            need[i] = max(need[i+1]+1, need[i])
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        ans += need[i]
    }
    return ans
}

DAY 35

柠檬水找零

• 当支付 5 时，直接收下
• 当支付 10 时，拿 5 找零
• 当支付 20 时，优先使用 10+5 进行找零，再使用 5+5+5

func lemonadeChange(bills []int) bool {
    five, ten, twenty := 0, 0, 0
    for _, bill := range bills {
        switch bill {
        case 5:
            five++
        case 10:
            five--
            ten++
        case 20:
            if ten != 0 {
                ten--
                five -= 1
            } else {
                five -= 3
            }
            twenty++
        }
        if five < 0 || ten < 0 || twenty < 0 {
            return false
        }
    }
    return true
}

根据身高重建队列

func reconstructQueue(people [][]int) [][]int {
    sort.Slice(people,func(i,j int)bool{
        if people[i][0] != people[j][0]{
            return people[i][0]>people[j][0]
        }
        return people[i][1]<people[j][1]
    })
    ans:=[][]int{}
    for _,person:=range people{
        idx:=person[1]
        ans=append(ans[:idx],append([][]int{person},ans[idx:]...)...)
    }
    return ans
}

用最少数量的箭引爆气球

看上去有点像合并区间

func findMinArrowShots(points [][]int) int {
    ans:=0
    curr:=math.MinInt
    sort.Slice(points,func (i,j int)bool{
        return points[i][1]<points[j][1]
    })
    for _,point:=range points{
        if point[0]>curr{
            curr=point[1]
            ans++
        }
    }
    return ans
}

DAY 36

无重叠区间

记录有多少重叠区间即可，与上题相同

func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    ans, curr := 0, math.MinInt
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    for _, interval := range intervals {
        if interval[0] >= curr {
            curr = interval[1]
            ans++
        }
    }
    return n - ans
}

划分字母区间

因为要包含所有的当前字符，所以需要记录字符的最远出现位置

func partitionLabels(s string) []int {
    m := map[rune]int{}
    for idx, c := range s {
        m[c] = idx
    }
    left, right := 0, 0
    ans := []int{}
    for idx, c := range s {
        right = max(right, m[c])
        if idx == right {
            ans = append(ans, right-left+1)
            left = right + 1
        }
    }
    return ans
}

合并区间

经典题目

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    ans := [][]int{}
    for _, interval := range intervals {
        if len(ans) > 0 && interval[0] <= ans[len(ans)-1][1] {
            ans[len(ans)-1][1] = max(ans[len(ans)-1][1], interval[1])
        } else {
            ans = append(ans, interval)
        }
    }
    return ans
}

DAY 37

单调递增的数字

从左往右遍历各位数字，找到第一个开始下降的数字，将其减一，然后后面全是 9 即可

func monotoneIncreasingDigits(n int) int {
    s := []byte(strconv.Itoa(n))
    i := 1
    for i < len(s) && s[i] >= s[i-1] {
        i++
    }
    if i < len(s) {
        for i > 0 && s[i] < s[i-1] {
            s[i-1]--
            i--
        }
        for i++; i < len(s); i++ {
            s[i] = '9'
        }
    }
    ans, _ := strconv.Atoi(string(s))
    return ans
}

监控二叉树

尽量在叶子节点的父节点安装摄像头

讲真这道题有点抽象，还是 hard（

这道题讲真应该动态规划做