网站建设公司宣传标语,长沙小升初有什么做试卷的网站,汉中网站建设公司推荐,新冠三阳最新消息目录
455 分发饼干
376 摆动序列
53 最大子数组和 455 分发饼干 将胃口值与饼干进行排序使其从小到大。 从后向前遍历胃口值#xff0c;并取得此时最大的饼干值#xff0c;如果饼干大于当前胃口值则将答案res加一#xff0c;并且将饼干减一。 class Solution {public in…目录
455 分发饼干
376 摆动序列
53 最大子数组和 455 分发饼干 将胃口值与饼干进行排序使其从小到大。 从后向前遍历胃口值并取得此时最大的饼干值如果饼干大于当前胃口值则将答案res加一并且将饼干减一。 class Solution {public int findContentChildren(int[] g, int[] s) {int res 0;Arrays.sort(s);Arrays.sort(g);int j s.length - 1;for(int i g.length - 1;i 0;i--){//遍历胃口if(j 0 s[j] g[i]){res;j--;}}return res;}
}
时间复杂度O(max(nlogn,mlogm))快速排序所占时间复杂度为nlogn与mlogm,遍历g与s所占时间复杂度为n与m
空间复杂度O(max(logn,logm))快速排序所占的额外空间
376 摆动序列 设置up和down两条子序列up序列表示到目前为止最后一个元素呈上升的最大序列的长度down表示到目前为止最后一个元素呈下降的最大序列的长度。遍历nums如果当前的元素比上一个小则将down赋值为up加1代表转换为最后一个元素呈下降的最大序列的长度。如果当前的元素比上一个大则将up赋值为down加1代表转换为最后一个元素呈上升的最大序列的长度。 class Solution {public int wiggleMaxLength(int[] nums) {int up 1;//表示到目前为止最后一个元素呈上升的最大序列的长度int down 1;//表示到目前为止最后一个元素呈下降的最大序列的长度for(int i 1;i nums.length;i){if(nums[i] nums[i - 1])up down 1;//最后一个为下降的最大序列的长度加一转化为上升的序列if(nums[i] nums[i - 1])down up 1;//最后一个为上升的最大序列的长度加一转化为下降的序列}return Math.max(up,down);//返回两条子序列中的最大值}
}
时间复杂度O(n)
空间复杂度O(1)
53 最大子数组和 将res赋值为int的最小值遍历nums通过sum累加nums中的值并且每次都判断是否需要更改res的值。如果当前sum的值小于0说明当前累加值对之后的值一定是负收益将sum赋值为0继续进行遍历。 class Solution {public int maxSubArray(int[] nums) {int res Integer.MIN_VALUE;int now 0;for(int i 0;i nums.length;i){now nums[i];res Math.max(res,now);if(now 0)now 0;}return res;}
}
时间复杂度O(n)
空间复杂度O(1)
