代码随想录 day35 第八章 贪心算法 part04

本文主要是介绍代码随想录 day35 第八章 贪心算法 part04，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

●  860.柠檬水找零

●  406.根据身高重建队列

●  452. 用最少数量的箭引爆气球

1. 柠檬水找零

关联 leetcode 860.柠檬水找零

• 思路

  • 使用金额的三种情况
    • 情况一 :
      • 账单是5, 直接收下
    • 情况二 :
      • 账单是10, 消耗一个5, 收获一个10
    • 情况三 :
      • 账单是20, 优先消耗一个10和一个5，如果不够，再消耗三个5
  • 贪心[ 针对情况三 ]
    • 局部
      • 优先消耗 10元, 5元的更万能
    • 全局
      • 完成账单清零

• 题解

  func lemonadeChange(bills []int) bool {if bills[0] > 5 || len(bills) < 1 {return false}restMoney := make(map[int]int) //剩余零钱, 可以用数字提升效率, 这里用map看的更清楚for _, b := range bills {switch b {case 5:restMoney[5] += 1case 10:restMoney[5] -= 1if restMoney[5] < 0 {return false}restMoney[10] += 1case 20:if restMoney[10] > 0 {restMoney[10] -= 1restMoney[5] -= 1} else {restMoney[5] -= 3}if restMoney[5] < 0 {return false}restMoney[20] += 1 // 这一步可以不要, 20不会用来找零}}return true
  }

2. 根据身高重建队列

关联 leetcode 406.根据身高重建队列

• 思路

  • 两个指标出现时, 每次解决一个指标
    • 本题的 k, h 每次贪一个指标
    • 本题来说
      • 身高是绝对序列, 唯一有序
      • 前面的人数是可能唯一有序
      • 选择 身高 作为第一次遍历指标
  • 贪心
    • 前提 已经按照身高降序排序,
    • 再按照 k 值升序
      • k小的前面人更少, 所以这个人在更前面的位置
    • 局部最优
      • 优先按身高高的people的k来插入。插入操作过后的people满足队列属性
    • 全局最优
      • 最后都做完插入操作，整个队列满足题目队列属性

• 题解

  func reconstructQueue(people [][]int) [][]int {sort.Slice(people, func(i, j int) bool {if people[i][0] == people[j][0] {return people[i][1] < people[j][1]}return people[i][0] > people[j][0]})rets := make([][]int, len(people))for i := 0; i < len(people); i++ {insertVal := people[i]insertIdx := people[i][1]//插入if rets[insertIdx] == nil {rets[insertIdx] = insertValcontinue}before := rets[:insertIdx]after := make([][]int, len(rets[insertIdx:]))copy(after, rets[insertIdx:])before = append(before, insertVal)rets = append(before, after...)}return rets[:len(people)]
  }
  

3. 用最少数量的箭引爆气球

关联 leetcode 452. 用最少数量的箭引爆气球

• 思路

  • 贪心
    • 局部最优
      • 重叠最多的气球
    • 全局最优
      • 最少的箭
  • 排序
    • 选择左/右边界来排序
      • 算重叠
        • 当前 左边界 与 前一个 右边界关系

• 题解

  func findMinArrowShots(points [][]int) int {if len(points) < 2 {return len(points)}sort.Slice(points, func(i, j int) bool {return points[i][0] < points[j][0]})res := 1 //至少需要一只箭for i := 1; i < len(points); i++ { // i从1开始, 要与左边的相比, 至少是从左开始数第二个if points[i][0] > points[i-1][1] { // 当前的左边 比 前一个的右边大res++ //多需要一只箭} else { // 当前的左边 <= 上一个右边 == 当前的气球和上一个气球有重叠或贴边points[i][1] = min(points[i-1][1], points[i][1]) // 更新重叠气球的最小右边界}}return res}func min(a, b int) int {if a < b {return a}return b
  }
  

这篇关于代码随想录 day35 第八章 贪心算法 part04的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---