做ppt网站大全,学电子商务去哪个学校比较好,重庆建设部网站,企业网站备案案例系列文章目录 目录 系列文章目录455.分发饼干贪心算法大饼干喂胃口大的#xff08;先遍历胃口#xff09;胃口大的先吃大饼干(先遍历饼干#xff09;小饼干先喂胃口小的#xff08;先遍历胃口#xff09;胃口小的先吃小饼干#xff08;先遍历饼干#xff09; 376. 摆动序…系列文章目录 目录 系列文章目录455.分发饼干贪心算法大饼干喂胃口大的先遍历胃口胃口大的先吃大饼干(先遍历饼干小饼干先喂胃口小的先遍历胃口胃口小的先吃小饼干先遍历饼干 376. 摆动序列贪心算法只关心上下坡摆动对所有平坡忽略总体看[看了其他人的想法好理解一些]只关心节点左右的坡度局部若两边坡度相反则是峰值考虑了平坡的情况[自己想不出来] 53. 最大子序和①暴力解法双层for循环超时②贪心解法 455.分发饼干
贪心算法 大饼干喂胃口大的先遍历胃口
import java.util.Arrays;
class Solution {public int findContentChildren(int[] g, int[] s) {//先从小到大自然排序Arrays.sort(g);Arrays.sort(s);int lenG g.length;int rightS s.length - 1;int count 0;//记录满足的孩子个数for (int i lenG - 1; i 0; i--) {//遍历胃口if (rightS 0 s[rightS] g[i]) {// 遍历饼干(要先判断是否还有饼干再遍历count;rightS--;}}return count;}
}胃口大的先吃大饼干(先遍历饼干
import java.util.Arrays;
class Solution {public int findContentChildren(int[] g, int[] s) {//先从小到大自然排序Arrays.sort(g);Arrays.sort(s);int rightG g.length - 1;int count 0;for (int i s.length - 1; i 0; i--) {while (rightG 0) {if (s[i] g[rightG]) {count;rightG--;break;}rightG--;}}return count;}
}小饼干先喂胃口小的先遍历胃口
import java.util.Arrays;
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count 0;int leftS 0;for (int i 0; i g.length; i) {while (leftS s.length) {if (s[leftS] g[i]) {count;leftS;break;}leftS;}}return count;}
}胃口小的先吃小饼干先遍历饼干
import java.util.Arrays;
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count 0;int leftG 0;for (int i 0; i s.length; i) {if (leftG g.length s[i]g[leftG]){count;leftG;}}return count;}
}376. 摆动序列
贪心算法
只关心上下坡摆动对所有平坡忽略总体看[看了其他人的想法好理解一些]
class Solution {int mark 0;// 记录是否出现摆动没出现摆动为0出现摆动后上坡为1下坡为-1int count 1;//因1 nums.length 1000故最少有一个元素public int wiggleMaxLength(int[] nums) {// nums.length 1或2的情况可以包含在下面for循环中// if (nums.length 1) return 1; // 不进入for循环直接返回1// if (nums.length 2) return nums[0] nums[1] ? 1 : 2; // 有摆动才返回2否则返回1// 策略只有第一次出现摆动以及上下坡的转折点的时候才resfor (int i 1; i nums.length; i) {int prediff nums[i] - nums[i - 1];// 如果之前都没出现摆动第一次出现摆动if (mark 0) {if (prediff 0) {// 第一次出现的摆动为上坡mark 1;count;}if (prediff 0) {// 第一次出现的摆动为下坡mark -1;count;}//平坡代表没有摆动不处理}// 如果遇到上坡判断上一个摆动是否为下坡是再记录结果并更新摆动if (prediff 0 mark -1) {mark 1;// 记录上坡count;}// 如果遇到下坡判断上一个摆动是否为上坡是再记录结果并更新摆动if (prediff 0 mark 1) {mark -1;// 记录下坡count;}// 注意此处包含对了平坡的忽略}return count;}
}只关心节点左右的坡度局部若两边坡度相反则是峰值考虑了平坡的情况[自己想不出来]
class Solution {int count 1;//默认最右面有一个峰值int prediff 0;public int wiggleMaxLength(int[] nums) {for (int i 0; i nums.length - 1; i) {int curdiff nums[i 1] - nums[i];//i节点右边坡度// 出现峰值if (prediff 0 curdiff 0 || prediff 0 curdiff 0) {count;prediff curdiff;}}return count;}
}53. 最大子序和
①暴力解法双层for循环超时
第一层 for 就是设置起始位置第二层 for 循环遍历数组寻找最大值。
class Solution {int sum 0;int maxSum Integer.MIN_VALUE;//将最大和先置为int的最小值public int maxSubArray(int[] nums) {for (int i 0; i nums.length; i) {sum 0;//每遍历一个节点先将sum置为0for (int j i; j nums.length; j) {sum nums[j];maxSum sum maxSum ? sum : maxSum;}}return maxSum;}
}②贪心解法
思路
局部最优每遍历一个元素都记录着截止到当前元素的最大子数组和当前元素不一定是最大子数组和对应子数组的结尾。全局最优遍历到最后一个元素就相当于获得了全局最大子数组和。 maxSum 要初始化为最小负数因数组可能全是负数初始化为0会导致最大和为0。
class Solution {int sum 0;int maxSum Integer.MIN_VALUE;//将最大和先置为int的最小值public int maxSubArray(int[] nums) {for (int i 0; i nums.length; i) {sum nums[i];if (sum maxSum) maxSum sum;// 取区间累计的最大值相当于不断确定最大子序终止位置if (sum 0) {sum 0; // 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}}return maxSum;}
}
