LeetCode 455 分发饼干
本题思路:分发饼干的时候,外层循环是胃口,内层是饼干,按照大饼干满足大胃口的思维来投递饼干。
需要将 两个数组,一开始就进行排序处理。
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int sum = 0;
int j = s.length - 1;
// 先喂饱大胃口的
for(int i = g.length - 1 ; i >= 0; i--){
if( j >= 0 && s[j] >= g[i]){
sum++;
j--;
}
}
return sum;
}
}
LeetCode 376 摆动子序列
本题思路:先进行一个元素的去重,去重之后,算出每个元素的差值,然后记录下来。然后根据根据 摆动子序列的要求,找到对应的差值,最后加个 1 。
class Solution {
public int wiggleMaxLength(int[] nums) {
int k = 0;
for(int i = 0; i<nums.length;i++){
if(i > 0 && nums[i] != nums[i-1]){
nums[++k] = nums[i];
}
}
if(k+1 <= 2){
return k+1;
}
int[] cha = new int[k+1];
for(int i = 1; i < cha.length; i++){
cha[i-1] = nums[i] - nums[i-1];
}
int ans = 1;
boolean pre = cha[0] > 0 ? true:false;
for(int i = 1; i < cha.length; i++){
if((cha[i] < 0 && pre) || (!pre && cha[i] > 0)){
ans++;
pre = !pre;
}
}
return ans+1;
}
}
LeetCode 53 最大子数组和
本题思路:先记录累加,如果累加和大于之前记录的,就重新记录累加和,如果累加和为负数,直接跳过。然后累加和置为 0 ,从新的正数开始累加。因为累加和如果是负数的话,再怎么加也是往小的,不如直接跳过。
class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE;
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
if(sum > res){
res = sum;
}
if(sum < 0){
sum = 0;
}
}
return res;
}
}