郑州高端网站,中国风风格网站模板,安卓优化清理大师,东营网站建设方案策划第八章 贪心算法 455.分发饼干376.摆动序列53.最大子序和代码随想录文章详解 455.分发饼干
对饼干和胃口进行排序 遍历胃口#xff0c;若当前饼干值胃口值#xff0c;饼干继续往后寻找更大值 否则计数1#xff0c;向后遍历饼干值使其满足下一个胃口值
func findConten… 第八章 贪心算法 455.分发饼干376.摆动序列53.最大子序和代码随想录文章详解 455.分发饼干
对饼干和胃口进行排序 遍历胃口若当前饼干值胃口值饼干继续往后寻找更大值 否则计数1向后遍历饼干值使其满足下一个胃口值
func findContentChildren(g []int, s []int) int {sort.Ints(g)sort.Ints(s)count : 0for i, j : 0, 0; i len(g) j len(s); i {for j len(s) s[j] g[i] {j}if j len(s) {countj}}return count
}376.摆动序列
(1)贪心 寻找最长子摆动序列只需记录波峰波谷出现的次数。对于序列两端的元素只有一侧相邻元素小于或大于当前元素也满足要求 若遇到平坡只需在坡度发生摆动变化时记录
func wiggleMaxLength(nums []int) int {if len(nums) 1 {return len(nums)}count : 1curDiff : 0preDiff : curDifffor i : 1; i len(nums); i {curDiff nums[i] - nums[i-1]if preDiff 0 curDiff 0 || preDiff 0 curDiff 0 {countpreDiff curDiff}}return count
}(2)动态规划 nums[i] nums[i - 1]由波峰转移过来【波谷】或者保持原状态【持续向下坡度】 nums[i] nums[i - 1]由波谷转移过来【波峰】或者保持原状态【持续向上坡度】
func wiggleMaxLength(nums []int) int {if len(nums) 1 {return len(nums)}up, down : 1, 1for i : 1; i len(nums); i {if nums[i] nums[i-1] {down max(up1, down)} else if nums[i] nums[i-1] {up max(down1, up)}}return max(up, down)
}53.最大子序和
最大连续子序和 (1)贪心 若以nums[i]结尾求和小于当前值取当前值否则继续求和覆盖当前值。最大值为整个遍历过程中连续求和的最大值
func maxSubArray(nums []int) int {if len(nums) 1 {return nums[0]}res : nums[0]for i : 1; i len(nums); i {if nums[i]nums[i-1] nums[i] {nums[i] nums[i-1] nums[i]}res max(res, nums[i])}return res
}(2)动态规划 以nums[i]结尾的最大连续子序列和前一个最大和 当前值或者直接选当前值 然后选取序列中和最大的结果
func maxSubArray(nums []int) int {dp : make([]int, len(nums))dp[0] nums[0]res : dp[0]for i : 1; i len(nums); i {dp[i] max(dp[i-1]nums[i], nums[i])res max(dp[i], res)}return res
}代码随想录文章详解
理论基础 455.分发饼干 376.摆动序列 53.最大子序和
