网站源码建站教程,网页设计与制作考试试题及答案,网站优化无限关键词设置,部门网站建设宗旨贪心算法其实就是没有什么规律可言#xff0c;所以大家了解贪心算法 就了解它没有规律的本质就够了。 不用花心思去研究其规律#xff0c; 没有思路就立刻看题解。 基本贪心的题目 有两个极端#xff0c;要不就是特简单#xff0c;要不就是死活想不出来。 学完贪心之后再… 贪心算法其实就是没有什么规律可言所以大家了解贪心算法 就了解它没有规律的本质就够了。 不用花心思去研究其规律 没有思路就立刻看题解。 基本贪心的题目 有两个极端要不就是特简单要不就是死活想不出来。 学完贪心之后再去看动态规划就会了解贪心和动规的区别。 理论基础 代码随想录 455.分发饼干 代码随想录 两个数组先排序倒着看最大的cookie能满足的孩子向前计数。 Python: class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:g.sort()s.sort()i len(g)-1j len(s)-1result 0while j0 and i0:if s[j]g[i]:result 1j - 1i - 1return resultC: C版本用i--实现也算简洁。 class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int result0;int i g.size()-1;int j s.size()-1;for (int ig.size()-1; i0; i--) {if (j0 s[j]g[i]) {result;j--;}}return result;}
}; 376. 摆动序列 代码随想录 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。 主要难点要考虑平坡的情况。 Python: class Solution:def wiggleMaxLength(self, nums: List[int]) - int:n len(nums)if n1: return nprev_diff nums[1] - nums[0]n_diff int(prev_diff!0)for i in range(2, n):cur_diff nums[i] - nums[i-1]if cur_diff * prev_diff 0 or (prev_diff0 and cur_diff!0):n_diff 1prev_diff cur_diff return n_diff 1 C: class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size()1) return nums.size();int preDiff 0;int curDiff 0;int result 1;for (int i0; inums.size()-1; i) {curDiff nums[i1] - nums[i];if ((preDiff0 curDiff0) || (preDiff0 curDiff0)) {result;preDiff curDiff;}}return result;}
}; 53. 最大子序和 代码随想录 局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。 全局最优选取最大“连续和” 局部最优的情况下并记录最大的“连续和”可以推出全局最优。 从代码角度上来讲遍历 nums从头开始用 count 累积如果 count 一旦加上 nums[i]变为负数那么就应该从 nums[i1]开始从 0 累积 count 了因为已经变为负数的 count只会拖累总和。 这相当于是暴力解法中的不断调整最大子序和区间的起始位置。 Python贪心: class Solution:def maxSubArray(self, nums: List[int]) - int:result float(-inf)count 0for num in nums:count numif count result:result countif count 0:count 0return result Python动态规划 class Solution:def maxSubArray(self, nums: List[int]) - int:curSum, maxSum nums[0], nums[0]for num in nums[1:]:curSum max(num, curSum num)maxSum max(maxSum, curSum)return maxSum C贪心: class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0; for (int i0; inums.size(); i) {count nums[i];if (countresult) result count;if (count 0) count0;}return result; }
}; C动态规划 class Solution {
public:int maxSubArray(vectorint nums) {int curSum nums[0];int maxSum nums[0];for (int i1; inums.size(); i) {curSum max(nums[i], curSumnums[i]);maxSum max(maxSum, curSum);}return maxSum;}
};
