算法训练（leetcode）二刷第二十三天 | 455. 分发饼干、*376. 摆动序列、53. 最大子数组和
455. 分发饼干
贪心算法。将两个数组排序后都从大向小匹配（优先考虑胃口）。
两个数组哪个是外层移动，哪个是内层移动：胃口在外，饼干尺寸在内。
也就是说：
- 若当前胃口若对得上当前饼干尺寸，则二者同时移动，且结果数+1；
- 若当前饼干尺寸无法满足当前胃口，就需要胃口数组向更小的方向移动，而饼干尺寸不变。
**Tips：**若是从小到大匹配（优先考虑饼干），则内外层交换。
时间复杂度：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 排序用时O(nlogn) 匹配用时O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
// java
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int cnt = 0;
int i=s.length-1;
for(int j=g.length-1; j>=0&&i>=0; j--){
if(s[i] >= g[j]){
cnt++;
i--;
}
}
return cnt;
}
}
*376. 摆动序列
题目要求严格摆动序列，因此前一组差和后一组差必须一正一负。而起始状态下没有计算差值默认前一组差值为0。因此在判断时: (preDiff >= 0 || preDiff <= 0)加入了等于0的判断。
**Tips：**为什么这里用preDiff=0判断起始状态而不是用curDiff=0判断？
因为curDiff计算的是当前一组的差值，若当前组差值为0则为平坡，不进入if；而preDiff是在if中进行更新的，因此只会在初始状态下问为0，其余情况均不为0。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
// java
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length <= 1) return nums.length;
int preDiff = 0;
int curDiff = 0;
int result = 1;
for(int i=0; i<nums.length-1; i++){
curDiff = nums[i+1] - nums[i];
if((curDiff<0 && preDiff>=0) || (curDiff>0 && preDiff<=0)){
result++;
preDiff = curDiff;
}
}
return result;
}
}
53. 最大子数组和
求最大连续子数组和，对数组中元素依次求和，当和为负值时将其置为0重新累加。为处理数组中全为负的情况，需要先记录最大值再置0。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
// java
class Solution {
public int maxSubArray(int[] nums) {
int maxVal = -10001;
int curVal = 0;
for(int i=0; i<nums.length; i++){
curVal += nums[i];
if(curVal > maxVal) maxVal = curVal;
if(curVal<0) curVal = 0;
}
return maxVal;
}
}
原文地址：https://blog.csdn.net/weixin_43872997/article/details/143694497
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！