手机网站优点,企业建网站需要什么,iis 网站目录权限,帮客户做网站内容贪心算法理论基础
贪心的本质#xff1a;通过每一阶段的局部最优推出全局最优。
思路#xff1a;找局部最优#xff0c;看能不能推出全局最优#xff0c;并尝试举反例。
步骤#xff1a;
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最…贪心算法理论基础
贪心的本质通过每一阶段的局部最优推出全局最优。
思路找局部最优看能不能推出全局最优并尝试举反例。
步骤
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优
455.分发饼干
题目链接
讲解链接
首先想到的解法是先将s数组和g数组按照从小到大的顺序排序然后用两个for循环来遍历两个数组外层遍历g数组内层遍历s数组每次遇到满足g[i] s[i]的情况时就将result1然后将s[i]置零代表这篇饼干已被使用过并跳出当前层循环若不满足则直接continue查找下一片饼干。总体思路就是优先满足胃口小的孩子。
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:s.sort() # 排序从小到大g.sort() # 使小胃口的孩子和小饼干排列在前result 0 # 结果初始为0for i in range(len(g)): # 遍历孩子数组for j in range(len(s)): # 遍历饼干数组if g[i] s[j]: # 意味着饼干不能满足孩子胃口直接跳过寻找下一块饼干continueelse:s[j] 0 # 满足条件则将当前饼干置零防止后续再被使用result 1breakreturn result
优化版本不需要使用两个for循环降低时间复杂度
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:s.sort()g.sort()index 0 # 用一个index来遍历胃口for i in range(len(s)): # for循环遍历饼干if index len(g) and g[index] s[i]: # 仅当满足条件时index才会1index 1return index # 返回index也就是消耗的饼干数
这里必须外层遍历饼干内层遍历胃口才可以因为外层循环的i是固定移动的内层的index只有在满足条件时才会移动如果交换顺序就会导致一直在用最小的饼干来对比所有孩子的胃口从而无法得出结果。
376.摆动序列
题目链接
讲解链接
思路局部最优——删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。整体最优——整个序列有最多的局部峰值从而达到最长摆动序列。
实际上不需要进行删除操作因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了相当于是删除单一坡度上的节点然后统计长度。如果前一对差值prediff与当前对差值curdiff的乘积小于0那么就说明当前是一处摆动。代码如下
class Solution:def wiggleMaxLength(self, nums: List[int]) - int:if len(nums) 1: # 如果数组长度小于等于1那么则直接返回数组的长度return len(nums)prediff, curdiff, result 0, 0, 1 # 初始化前一对差值当前差值和结果因为输出的结果是序列的长度所以结果的初值要设置为1单纯计算正负差值的对数的结果与序列长度相差1for i in range(1, len(nums)): # 遍历数组从1开始curdiff nums[i] - nums[i - 1] # 计算当前差值if curdiff * prediff 0 and curdiff ! 0: # 若当前差与前一对差乘起来的结果是负数或0且当前差值不为0那么说明出现了摆动result 1 # 结果1prediff curdiff # 只有出现摆动时才令前一对差等于当前差return result
53.最大子数组和
题目链接
讲解链接
暴力解法容易想到但会超时。
class Solution:def maxSubArray(self, nums: List[int]) - int:result float(-inf) # 结果初始为无穷小for i in range(len(nums)): # i对应遍历的起始位置sum 0 # 每次改变起始位置时都将sum置零for j in range(i, len(nums)): # 每次从j从i开始遍历寻找最大值sum nums[j]if sum result: # 如果sum大于之前的result就进行赋值result sumreturn result
贪心思路
局部最优——当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。全局最优——选取最大“连续和”
遍历 nums从头开始用sum累积如果sum一旦加上nums[i]变为负数那么就应该从 nums[i1]开始从 0 累积sum了因为已经变为负数的sum只会拖累总和。
这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
class Solution:def maxSubArray(self, nums: List[int]) - int:result float(-inf) # result初始为无穷小sum 0 # 连续和初始为0for i in range(len(nums)): # 遍历数组sum nums[i] # 将第i个元素加到连续和上if sum result: # 如果当前连续和大于result则更新result的值result sumif sum 0: # 如果连续和小于0则直接舍弃sum 0 # 将连续和置零continue # 从下一个i开始重新计算类似于暴力法的移动起始位置return result
