代码随想录day24 | 贪婪算法理论基础 leetcode 455.分发饼干 376.摆动序列 ...

贪婪算法理论基础

贪婪算法是一种在每一步选择中都做出当前看起来最优的选择，从而盼望通过局部最优解得到全局最优解的算法。贪婪算法的基本头脑是：在办理题目时，尽量选择当前最好的选项，终极达到全局最优解.
分发饼干

标题：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽大概多的孩子，并输出这个最大数值。
为了尽大概满足最多数量的孩子，从贪婪的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。
for循环不利于控制移动，舍弃这种普遍思维，习惯用变量的移动控制，学习数据处理惩罚的元素控制，区分辨认动态，非动态，目标值，固定值。

1. public int findContentChildren(int[] g, int[] s) {
2.         Arrays.sort(g);
3.         Arrays.sort(s);
4.         int count = 0,index = s.length-1;
5.         for(int i = g.length-1;i>=0;i--){
6.             if(index>=0&&s[index]>=g[i]){
7.                 index--;
8.                 count++;
9.                
10.             }
11.         }
12.         return count;        
13.     }

复制代码

---

摆动序列

以下是一些界说：
特别地，对于长度为 1 的序列，它既是「上升摆动序列」，也是「降落摆动序列」。
序列中的某个元素被称为「峰」，当且仅当该元素两侧的相邻元素均小于它。如序列 [1,3,2,4] 中，3 就是一个「峰」。
序列中的某个元素被称为「谷」，当且仅当该元素两侧的相邻元素均大于它。如序列 [1,3,2,4] 中，2 就是一个「谷」。
特别地，对于位于序列两头的元素，只有一侧的相邻元素小于或大于它，我们也称其为「峰」或「谷」。如序列 [1,3,2,4] 中，1 也是一个「谷」，4 也是一个「峰」。
因为一段相邻的雷同元素中我们最多只能选择此中的一个，以是我们可以忽略相邻的雷同元素。现在我们假定序列中恣意两个相邻元素都不雷同，即要么左侧大于右侧，要么右侧大于左侧。对于序列中既非「峰」也非「谷」的元素，我们称其为「过渡元素」。如序列 [1,2,3,4] 中，2 和 3 都是「过渡元素」。
解题：模拟图像，将数字差值变成坡度。
1. 上下坡中有平坡
舍弃curdiff = 0，平坡时差值为0。
2.数组首尾两头
标题中限定了：仅有一个元素或者含两个不等元素的序列也视作摆动序列。
3.单调坡度有平坡
当某段大体成递增趋势时，只用考虑最高波峰，与初始过渡元素。

1.   public int wiggleMaxLength(int[] nums) {
2.         int prediff = 0,curdiff = 0;//prediff相当于初始0，curdiff是当前值
3.         int result = 1;//最右端的
5.         for (int i = 0; i < nums.length-1; i++) {
6.             curdiff = nums[i+1] - nums[i];
7.             if((prediff >= 0&&curdiff<0)||(prediff <= 0&&curdiff>0)){
8.                 result++;
9.                 prediff = curdiff;//记录递增的第一个，后面若没遇到摆动的话，不必进行记录
10.             }
12.         }//某段是递增序列，递减序列。
13.         //连续递增序列
14.         return result;
15.     }

复制代码

---

最大子序和

局部最优：当前“连续和”为负数的时间立刻放弃，从下一个元素重新盘算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
方法：贪婪。
贪婪贪的是哪里呢？
如果 -2 1 在一起，盘算出发点的时间，肯定是从 1 开始盘算，因为负数只会拉低总和，这就是贪婪贪的地方！
误区：如果输入用例都是-1，或者 都是负数，这个贪婪算法跑出来的结果是 0， 这是又一次证明脑洞模拟不靠谱的经典案例，实际为最大负数。

1. public int maxSubArray(int[] nums) {
2.          int result = Integer.MIN_VALUE;
3.         int count = 0;
4.         for (int i = 0; i < nums.length; i++) {
5.             count += nums[i];
6.             if (count>result){
7.                 result = count;
8.             }
9.             if (count<0){
10.                 count =0;
11.             }
12.         }
13.         return result;
14.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。