代码随想录 day31 第八章 贪心算法 part01

●  理论基础

●  455.分发饼干

●  376. 摆动序列

●  53. 最大子序和

理论基础

• 本质
  • 选择当前阶段的局部最优 —> 达到全局最优
• 贪心的套路
  • 没有固定太路
  • 最好的策略是 举反例
    • 面试官pass：
      • 代码能跑过测试用例
      • 自己能自圆其说
• 贪心有时候就是常识性的推导
• 一般解题步骤
  1. 将问题分解为若干个子问题
  2. 找出适合的贪心策略
  3. 求解每一个子问题的最优解
  4. 将局部最优解堆叠成全局最优解
• 重点：
  • 想清楚 局部最优

1. 分发饼干

关联 leetcode 455.分发饼干

• 思路
  • 两种思路
    • 1、先满足胃口
      • 大饼干满足大胃口
        • for 倒序遍历胃口
    • 2、先满足饼干
      • 小饼干满足小胃口
        • for 正序遍历饼干
• 题解

  • 先满足饼干

    func findContentChildren(g []int, s []int) int {
    	sort.Ints(g)
    	sort.Ints(s)
     
    	child := 0//满足的孩子总数
    	// 遍历饼干, 小满足小饼干
    	for sIdx := 0; child < len(g) && sIdx < len(s); sIdx++ {
    		if s[sIdx] >= g[child] {
    			child++
    		}
    	}
    	return child
    }
    

  • 先满足胃口

    func findContentChildren(g []int, s []int) int {
    	sort.Ints(g)
    	sort.Ints(s)
     
    	ret := 0 //满足的孩子总数
     
    	// 倒序遍历胃口, 先找到胃口大的
    	for gIdx, sIdx := len(g)-1, len(s)-1; sIdx >= 0 && gIdx >= 0; gIdx-- {
    		if s[sIdx] >= g[gIdx] {
    			ret++
    			sIdx--
    		}
    	}
    	return ret
    }
    

2. 摆动序列

关联 leetcode 376. 摆动序列

• 思路

  • 明确要求连续数字的差正负摆动
  • 从原始序列中删除元素
    • 峰值元素不能删
      • 单调坡度上的元素
        • 单调递增、单调递减的上的中间元素删除
    • 保留峰值元素
  • 局部最优：
    • 删掉单调坡上的元素
      • ==》全局最优：最长的摆动序列
  • 没必要做真实删除
    • 统计峰值的数量即可
  • 注意平坡情况
    1. 情况一：上下坡中有平坡
    2. 情况二：数组首尾两端
    3. 情况三：单调坡中有平坡

• 题解

  func wiggleMaxLength(nums []int) int {
  	if len(nums) < 2 {
  		return len(nums)
  	}
  	preDiff := 0 //前一个差
  	curDiff := 0 //后一个差
  	res := 1     //峰值个数，默认序列最右边算一个峰值
  	for i := 0; i < len(nums)-1; i++ {
  		curDiff = nums[i+1] - nums[i]
  		// 出现摆动, 统一规则都删左边的元素, 所以对 preDiff 取 零值
  		if (curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0) {
  			res++
  			preDiff = curDiff
  		}
  	}
  	return res
  }
  

3. 最大子序和

关联 leetcode 53. 最大子序和

• 思路

  • 贪心解法
    • 局部最优
      • 当前 连续和 为负数的时候立刻放弃，从下一个元素重新计算 连续和
    • 全局最优
      • 选取最大的连续和
    • 取当前的 连续和 与 当前结果值 逐步比较

• 题解

  func maxSubArray(nums []int) int {
  	res := nums[0] //最终结果
  	count := 0     //当前连续和
  	for i := 0; i < len(nums); i++ {
  		count += nums[i]
  		if count > res { //更新结果
  			res = count
  		}
  		if count < 0 {//当前连续和为负数了, 重新开始计算连续和
  			count = 0
  		}
  	}
  	return res
  }
  

总结

贪心算法其实就是没有什么规律可言，所以大家了解贪心算法 就了解它没有规律的本质就够了。

不用花心思去研究其规律， 没有思路就立刻看题解。

基本贪心的题目 有两个极端，要不就是特简单，要不就是死活想不出来。

学完贪心之后再去看动态规划，就会了解贪心和动规的区别