理论基础
455.分发饼干
题目链接
https://leetcode.cn/problems/assign-cookies/description/
题目描述
思路
自己写的，因为没有事先对两个数组进行排序，所以出现了问题
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(s);
Arrays.sort(g);
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < s.length; i++) {
list.add(s[i]);
}
int count = 0;
for (int i = 0; i < g.length; i++) {
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
Integer integer = iterator.next();
if (g[i] <= integer) {
count++;
iterator.remove();
break;
}
}
}
return count;
}
}
1、
public static int findContentChildren(int[] g, int[] s) {
//优先考虑大胃口，大饼干先喂饱大胃口
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = s.length-1;
for (int i = g.length-1; i >= 0;i--) {
if(i>=0&&g[i]<=s[start]){
start--;
count++;
}
}
return count;
}
2、
public static int findContentChildren(int[] g, int[] s) {
//优先考虑饼干，小饼干先喂饱小胃口
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = 0;
for (int i = 0; i < s.length&&start<g.length; i++) {
if(s[i]>=g[start]){
start++;
count++;
}
}
return count;
}
376. 摆动序列
题目链接
https://leetcode.cn/problems/wiggle-subsequence/description/
题目描述
思路
有点小懵
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
//当前差值
int curDiff = 0;
//上一个差值
int preDiff = 0;
int count = 1;
for (int i = 1; i < nums.length; i++) {
//得到当前差值
curDiff = nums[i] - nums[i - 1];
//如果当前差值和上一个差值为一正一负
//等于0的情况表示初始时的preDiff
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
count++;
preDiff = curDiff;
}
}
return count;
}
}
53. 最大子序和
题目链接
https://leetcode.cn/problems/maximum-subarray/description/
题目描述
思路
//result 存放最后的结果
//count用来统计每次累加的结果
//遍历数组，如果和为负数了，就将前边的丢掉，从下一个重新开始计算
class Solution {
public int maxSubArray(int[] nums) {
int result = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++) {
count += nums[i];
if(count>result) result = count;
if(count<0) count = 0;
}
return result;
}
}
这个代码太厉害了，就用了这几行！！！