网站做附近地图导航企业网站建设的报价

当前位置： 首页 > news >正文

网站做附近地图导航,企业网站建设的报价,做招投标网站,软件开发服务平台贪心算法理论基础 贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。 贪心一般解题步骤#xff08;贪心无套路#xff09;#xff1a; 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 455.分发饼干 …贪心算法理论基础 贪心的本质是选择每一阶段的局部最优从而达到全局最优。 贪心一般解题步骤贪心无套路 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 455.分发饼干 这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩 或者是 局部最优就是小饼干喂给胃口小的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩 注意事项注意两种情况 //大饼干满足胃口大的孩子 最大饼干一定要用所以for控制胃口 代码中先遍历的胃口在遍历的饼干那么可不可以 先遍历 饼干在遍历胃口呢其实是不可以的。外面的 for 是里的下标 i 是固定移动的而 if 里面的下标 index 是符合条件才移动的。 如果 for 控制的是饼干 if 控制胃口就是出现如下情况 、 if 里的 index 指向 胃口 10 for 里的 i 指向饼干 9因为 饼干 9 满足不了 胃口 10所以 i 持续向前移动而 index 走不到s[index] g[i] 的逻辑所以 index 不会移动那么当 i 持续向前移动最后所有的饼干都匹配不上。        所以 一定要 for 控制 胃口里面的 if 控制饼干。 //小饼干满足胃口小的孩子   for控制饼干  if控制胃口最小胃口一定要被喂所以for控制饼干 //大饼干满足胃口大的孩子 class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int index s.length - 1;int result 0 ;for (int i g.length -1; i 0; i–) {if(index 0 s[index] g[i]){index–;result;}}return result;} }//小饼干满足胃口小的孩子 class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int index 0;for (int i 0; i s.length; i) {if(index g.length g[index] s[i]){index;}}return index;} } 误区 如果说使用这种代码的话使用while判断可能会导致重复技术即g[1,2,3]  s[1,1]会导致结果为2而不是正确的情况只满足一个孩子所以判断使用if。 for (int i g.length -1; i 0; i–) {while(index 0 s[index] g[i]){index–;result;} } 376. 摆动序列 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。 整体最优整个序列有最多的局部峰值从而达到最长摆动序列 实际操作上其实连删除的操作都不用做因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了相当于是删除单一坡度上的节点然后统计长度这就是贪心所贪的地方尽可能的保持峰值然后删除单一坡度上的节点 大体思路 在计算是否有峰值的时候遍历下标 i 计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]如果prediff 0 curdiff 0 或者 prediff 0 curdiff 0 此时就有波动就需要统计。 三种情况 情况一上下坡中有平坡情况二数组首尾两端情况三单调坡中有平坡 上下坡中有平坡 在图中当 i 指向第一个 2 的时候prediff 0 curdiff 0 当 i 指向最后一个 2 的时候 prediff 0 curdiff 0。 如果我们采用删左面三个 2 的规则那么 当 prediff 0 curdiff 0 也要记录一个峰值因为他是把之前相同的元素都删掉留下的峰值。 所以我们记录峰值的条件应该是 (preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)为什么这里允许 prediff 0 就是为了 上面我说的这种情况。 情况二数组首尾两端prediff0为了解决数组最左端  最右端初始化为0 如果只有两个不同的元素那摆动序列也是 2。 可以假设数组最前面还有一个数字针对序列[2,5]可以假设为[2,2,5]这样它就有坡度了即 preDiff 0如图 针对以上情形result 初始为 1默认最右面有一个峰值 情况三单调坡度有平坡解决情况2出现的问题在坡度有变化时再prediff curdiff 我们忽略了一种情况即 如果在一个单调坡度上有平坡例如[1,2,2,2,3,4]如图 在三个地方记录峰值但其实结果因为是 2因为 单调中的平坡 不能算峰值即摆动。 那么我们应该什么时候更新 prediff 呢 我们只需要在 这个坡度 摆动变化的时候更新 prediff 就行这样 prediff 在 单调区间有平坡的时候 就不会发生变化造成我们的误判。 总结 本题异常情况的本质就是要考虑平坡 平坡分两种一个是 上下中间有平坡一个是单调有平坡如图 class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length 1)return nums.length;int prediff 0;int curdiff 0;int count 1;for (int i 1; i nums.length; i) {curdiff nums[i] - nums[i-1];if ((curdiff 0 prediff 0) || (curdiff 0 prediff 0)) {count;prediff curdiff; //在坡度变化时改变prediff}//prediff curdiff; 这种写法解决不了单调有平坡的问题}//System.out.println(count);return count;} } 53. 最大子序和 局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。 全局最优选取最大“连续和” 常见误区 误区一 不少同学认为 如果输入用例都是-1或者 都是负数这个贪心算法跑出来的结果是 0 这是又一次证明脑洞模拟不靠谱的经典案例建议大家把代码运行一下试一试就知道了也会理解 为什么 result 要初始化为最小负数了。 误区二 大家在使用贪心算法求解本题经常陷入的误区就是分不清是遇到 负数就选择起始位置还是连续和为负选择起始位置。 在动画演示用大家可以发现 4遇到 -1 的时候我们依然累加了为什么呢 因为和为 3只要连续和还是正数就会 对后面的元素 起到增大总和的作用。 所以只要连续和为正数我们就保留。 这里也会有录友疑惑那 4 -1 之后 不就变小了吗 会不会错过 4 成为最大连续和的可能性 其实并不会因为还有一个变量 result 一直在更新 最大的连续和只要有更大的连续和出现result 就更新了那么 result 已经把 4 更新了后面 连续和变成 3也不会对最后结果有影响 class Solution {public int maxSubArray(int[] nums) {if(nums.length 1)return nums[0];int sum Integer.MIN_VALUE; //存储最大值int count 0; //统计大小for (int i 0; i nums.length; i) {count nums[i];sum Math.max(sum,count);if(count 0) {count 0;}}return sum;} }