Day31题目
LeetCode455.分发饼干
核心思想:将两个数组排序,计算饼干遍历完能有几个大于需求的个数
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0 ;
int j = 0;
int count = 0 ;
while(i < g.length && j < s.length){
if(s[j]>=g[i]){
count++;
j++;
i++;
}else{
// 如果当前最小的饼干满足不了最小需求,就增加饼干大小
j++;
}
}
return count ;
}
}
LeetCode376.摆动序列:前一个增加后一个就要减少
核心思想:看数组峰值的个数即可,最后的长度是峰值的个数加一
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length <= 1) return nums.length;
int result = 0;
// 记录一下上一个是增加还是减少
int preDiff = 0;
int curDiff = 0;
for(int i = 0 ; i < nums.length-1 ; i ++ ){
curDiff = nums[i+1] - nums[i];
// 只要前一个和现在这个不一样就行
if((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0) ){
result ++;
preDiff = curDiff;
}
}
return result+1;
}
}
LeetCode53.最大连续子数列和
核心思想:有好几种方法完成,使用数组维护从第一个数到目前这个数的所有子序列的和的最大值(动态规划),遍历
// 这里给出一个不用维护的办法:两年前自己写的。耗时最短,挺佩服当时没有模板刷题的自己
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
for(int i = 0 ; i < nums.length ; i ++){
if(nums[i] >= max){
max = nums[i];
}
}
int count = 0 ;
for(int i = 0 ; i < nums.length ; i ++){
count = count + nums[i];
if(count > 0){
if(count > max){
max = count;
}
}else{
// 如果前面的数的和小于0,那么自身的值就是目前最大
count = 0;
}
}
return max;
}
}