算法 之 贪心思维训练！

• 贪心策略在处理一些题目的时候能够带来意想不到的效果
  • 从最小/最大开始贪心，优先考虑最小/最大的数，从小到大/从大到小贪心，在此基础上出现了反悔贪心
  • 从最左/最右开始贪心，思考第一个数、最后一个数的贪心策略，把n个数的原问题转换为n-1个数(或者更少)的子问题(最左最右开始贪心的情况，一般是原来的数组是无法进行排序的)

从最大/最小开始贪心

2279.装满石头的背包的最大数量

2279.装满石头的背包的最大数量

思路分析：

• 需要计算出每个背包还能装的石头的数量，然后进行升序排序，将总的还能放的时候逐一分配即可

class Solution:def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:# 贪心的味道！n = len(rocks)need = [0]*n for i in range(n):need[i] = capacity[i] - rocks[i]# 升序排序need.sort()ans = 0# 直接写一个前缀和好了for i in range(1,n):need[i] += need[i-1]for i in range(n):if need[i] <= additionalRocks:ans += 1else:breakreturn ans

2971.找到最大周长的多边形

2971.找到最大周长的多边形

思路分析：

• 首先，为了更好按照公式计算出边长的满足关系，应该先把边长进行排序，然后为了方便计算和的情况,接着使用这个前缀和进行计算
• 在这里，应该意识到一个思想:要想让最后的总的周长最大，应该只需要从最长的边长进行枚举，判断先前的边是否满足和>nums[i],不可能会出现nums[s]-nums[e] 和这个 nums[i] 组成最长的周长的三角形的情况，因为这样都满足的话，那直接加上剩余的达到nums[0]的情况也是满足的

class Solution:def largestPerimeter(self, nums: List[int]) -> int:# 肯定得用贪心思想，直接把边进行排序，然后弄一个前缀和，将最大的边与前面所有情况进行比较即可n = len(nums)# 升序排序# 时间复杂度在这里nlognnums.sort()pre = [0]*n for i in range(n):if i == 0:pre[0] = nums[0]else:pre[i] = pre[i-1] + nums[i]ans = 0# 枚举这个除了nums[n-1]的左边的情况# 策略有问题，应该是移动这个for i in range(n-1,1,-1):if nums[i] < pre[i-1]:ans = ibreakreturn pre[ans] if ans != 0 else -1

从最左、最右开始贪心

2712.使所有字符相等的最小成本

2712.使所有字符相等的最小成本

灵神讲解第三题

• 对于这种翻转的问题，我们可以有哪些思考的思路？
  • 是否和翻转的顺序有关？
  • 选择翻转左边还是右边？
  • 翻转之后的哪些不变量？

class Solution:def minimumCost(self, s: str) -> int:# 全部相等，那么最终的情况就是 全部是0或者全部是1# 根据模拟和贪心的思想，最终如果长度是偶数，那么变成n = len(s)# 怎么说ans = 0for i in range(n-1):if s[i] != s[i+1]:ans += min(i+1,n-(i+1))return ans

划分型贪心

1221.分割平衡字符串

1221.分割平衡字符串

思路分析：

• 贪心思路：直接进行统计，如果没有出现，就加入 ，否则就计数+1，同时记录的集合清零

class Solution:def partitionString(self, s: str) -> int:n = len(s)ans = 0curnum = set()for i in range(n):# 如果已经在里面了if s[i] in curnum:ans+=1# 清零curnum = set()curnum.add(s[i])return ans + 1