day31
贪心算法
455.分发饼干
题目链接：455. 分发饼干
局部最优，保证大饼干能够满足大孩子，依次遍历，外层一定是孩子的胃口。
// 时间：O(nlogn)
// 空间：O(1)
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
// 小孩和饼干从小到大排序
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int result = 0; //这里一定要给result赋初值
int index = s.size()-1;
//开始小孩从大到小遍历，取局部最优
for( int i = g.size() - 1 ; i >= 0 ; i--){
if ( index >= 0 && s[index] >= g[i]){
result++;
index--;
}
}
return result;
}
};
376.摆动序列
题目链接：376. 摆动序列
- 贪心解法
根据局部最优（删除单调坡度上的节点（不包括单调坡度两端的节点））推导全局最优（整个序列最多的局部峰值）
实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）
定义两个变量,prediff(nums[i]-nums[i-1])和curdiff(nums[i+1] - nums[i])
// 有波动的情况
prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0
根据分析，本题有三种情况
- 上下坡中有平坡
如上图，摆动序列的长度是3，因此需要删除掉前三个2，判断条件就是根据之前的两个变量。
对于第一个2和最后一个2，有不同的方式，统一规则删除前面的三个，这个时候判断条件就有加prediff==0的情况。
- 数组首尾两端
相当于前面加了一个元素，还是满足等于0的情况。
- 单调坡中有平坡
这种情况在于更新prediff的规则，只有当计算出来坡度摆动的时候再更新prediff，这样就能得到最后的结果。
本题注意两种平坡的情况：上下中间有平坡，单调有平坡
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
// 判断等于1的情况
if( nums.size() <= 1) return nums.size();
int result = 1; //初始记录最后一个元素坡度
int prediff = 0; //相当于首位元素有坡度
int curdiff = 0;
for( int i = 0; i < nums.size() - 1; i++){ //这里不包括最后一个元素，因为result已经记录了其坡度
curdiff = nums[i+1] - nums[i]; //给curdiff赋值，prediff的赋值后面更新
if( (prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff >0)){ // 统一更新规则
result++;
prediff = curdiff;
}
}
return result;
}
};
53.最大子序和
题目链接：53. 最大子数组和
暴力解法
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
// 暴力超时
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) { // 设置起始位置
count = 0;
for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
count += nums[j];
result = count > result ? count : result;
}
}
return result;
}
};
贪心解法
局部最优的思路：当连续和为负数的时候立刻放弃前面所有值，直接置为0，从下一个元素重新计算连续和，因为负数加上下一个元素指挥变小
全局最优：选取最大的连续和
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
关于如何收获最大值，当计数值大于结果值就更新结果值。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0; //计算中间值
int result = INT_MIN;
for( int i = 0; i < nums.size(); i++){ //遍历数组
sum += nums[i]; // 累加数组
// result = max( sum, result);
if( sum > result ) result = sum;
if( sum < 0 ){ //当发现总和为负直接变为0
sum = 0;
}
}
return result;
}
};