day31 代码随想录 分发饼干&摆动序列&最大子序和

大纲

● 理论基础
● 455.分发饼干
● 376. 摆动序列
● 53. 最大子序和

455.分发饼干

题目：455.分发饼干

// 分发饼干
// 有数组g代表胃口大小，数组s代表饼干大小
// 求满足最多胃口的值
// 思路是对g s排序
// 优先选择最大的饼干满足最大的胃口
// [1,2,3] [1,1]
int fitChildVal(vector& g, vector& s)
{
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());

    int index = s.size() - 1, count = 0;
    for (int i = g.size() - 1; i >= 0; --i) {
        if (index >= 0 && s[index] >= g[i]) {
            index--;
            count++;
        }
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

376. 摆动序列

题目：376. 摆动序列

// 给定一个数组arr，判断里面是摆动序列组合的最大长度
// 思路是计算相邻数据的差形成一个数组，然后删除相邻同符号的值
// 返回剩下数组长度+1
// 可以优化为一个变量统计和一个变量记录上一个值，减少空间复杂度
// 忘记处理val为0的情况了
int maxUpDownArrayLength(vector& nums) {
//    vector plusVec;
    int lastVal = 0;
    int count = 0;
    for (int i = 1; i < nums.size(); ++i) {
        int val = nums[i] - nums[i - 1];
        if (val == 0) continue;
        if (count !=0 && lastVal > 0 && val > 0)
            continue;
        if (count !=0 && lastVal < 0 && val < 0)
            continue;
        lastVal = val;
//        plusVec.push_back(val);
        count++;
    }

    return count + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

53. 最大子序和

题目：53. 最大子序和

// 最大子数组和
// 遍历所有种可以的子数组，分别统计最大和 取最大值
// O(n ^ 2)时间复杂度

// 用递归吧
// 结束条件是抵达最后元素值
// 参数是开始的元素下标
// 循环体，遍历元素
//
// 但是行不通，原因在于递归使其遍历了所有组合可能，而不是仅仅相邻的
int maxSum = INT_MIN;
void _maxSub(vector& nums, int& pathSum, int startIndex)
{
    if (startIndex >= nums.size()) return;
    if (maxSum < pathSum)
        maxSum = pathSum;

    for (int i = startIndex; i < nums.size(); ++i) {
        pathSum += nums[i];
        _maxSub(nums, pathSum, i + 1);
        pathSum -= nums[i];
    }
}

int maxSubArraySum(vector& nums) {
    int pathSum = 0;
    _maxSub(nums, pathSum, 0);
    return maxSum;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

总结

贪心的解法比较难想到解决办法，也没有太多规律，需要自己多熟悉