在线免费网站模板,苏州汇聚人电子科技有限公司,大丰企业做网站多少钱,建设一个班级网站的具体步骤贪心算法#xff08;Greedy Algorithm#xff09;#xff1a;是一种在每次决策时采用当前状态下最优或最好的策略#xff0c;从而希望导致结果是最好或最优的算法。
455. 分发饼干
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:…贪心算法Greedy Algorithm是一种在每次决策时采用当前状态下最优或最好的策略从而希望导致结果是最好或最优的算法。
455. 分发饼干
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:g.sort(reverseTrue)s.sort(reverseTrue)p1, p2 0, 0ans 0while p2 len(s) and p1 len(g):if s[p2] g[p1]:ans 1p1 1p2 1else:p1 1return ans思路不难对饼干和孩子进行排序由大到小然后从最大的饼干和最大的孩子开始考虑如果饼干能满足当前孩子则计数加 1考虑下一个饼干和孩子如果不能满足则考虑下一个孩子。直到孩子或者饼干考虑完为止。
860. 柠檬水找零
class Solution:def lemonadeChange(self, bills: List[int]) - bool:five ten 0for num in bills:if num 5:five 1elif num 10:if five 0:return Falseelse:five - 1ten 1elif num 20:if ten 0 and five 0:five - 1ten - 1elif five 3:five - 3else:return Falsereturn True同样是分类讨论如果收到 5 块则 5 块加 1如果收到 10 块则找零 5 块10块加15块减1如果收到 20 块则优先使用 10 块 5 块找零其次再考虑用 3 张 5 块找零凡是无法找零都返回 False。
1005. K 次取反后最大化的数组和
class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) - int:nums.sort()index 0while index len(nums) and k 0 and nums[index] 0:nums[index] -nums[index]index 1k - 1if k 0 and k % 2 ! 0:return sum(nums) - 2 * min(nums)else:return sum(nums)首先对数组排序从小到大然后取反先从负数开始如果有的话如果没有负数了还剩余取反次数的话就只考虑奇数的情况偶数可以抵消这时就对最小的正数也是最小的数因为没负数了取反即可。
738. 单调递增的数字
class Solution:def monotoneIncreasingDigits(self, n: int) - int:a list(str(n))for i in range(len(a)-1,0,-1):if int(a[i]) int(a[i-1]):a[i-1] str(int(a[i-1]) - 1)a[i:] 9 * (len(a) - i) return int(.join(a)) 考虑两个相邻数字的情况如果左边的比右边大则为了满足单调递增的条件必定是左边的数减 1 而右边的数变成 9因为要单调递增所以右边所有数都变成 9。从个位数右边向左开始考虑每一对数字的情况当出现左边数减 1 时右边的所有数字一定都变成 9。
