代码随想录训练营day27|贪心算法part1

分发饼干

力扣题目链接

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int result = 0;
        int j = 0;
        for(int i = 0; i < g.size(); i++){
            while(j < s.size() && s[j] < g[i]){
                j++;
            }
            if(j < s.size()){
                j++;
                result++;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

摆动序列

力扣题目链接

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int result = 1;
        int flag = 0;
        int pre = 0;
        int cur = 0;
        while(cur < nums.size()){
            // 初始化
            if(flag == 0 && nums[pre] != nums[cur]){
                if(nums[pre] < nums[cur]){
                    flag = -1;
                }
                else if(nums[pre] > nums[cur]){
                    flag = 1;
                }
                pre = cur;
                cur++;
                result = 2;                
            }
            // 未初始化
            else if(flag == 0 && nums[pre] == nums[cur]){
                pre = cur;
                cur++;
            }
            // 相同符号
            else if((flag > 0 && nums[pre] >= nums[cur]) || (flag < 0 && nums[pre] <= nums[cur])){
                pre = cur;
                cur++;
                continue;
            }
            //符号改变
            else{
                flag *= -1;
                pre = cur;
                cur++;
                result++;           
            }
        }
        return result;
    }
};
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
31
32
33
34
35
36
37
38
39
40
41
42

最大子序和

力扣题目链接

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = nums[0];
        int sum = 0;
        int index = 0;
        while(index < nums.size()){
            sum = max(nums[index], sum + nums[index]);
            result = max(sum, result);
            index++;
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14