leetcode-notes-20230912.

455. 分发饼干（C++实现贪心算法，先遍历胃口数组）

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        //先对两个数组进行排序
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1;//index保存饼干数组的当前位置
        int result = 0;//记录结果（孩子满足的人数）
        //外层for循环遍历胃口数组
        for(int i = g.size() - 1; i >= 0; i--){
            if(index >=0 && s[index] >= g[i]){
                index --;
                result ++;
            }
        }
        return result;
    }
};

455. 分发饼干（C++实现贪心算法，先遍历饼干数组）

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = 0;
        int result = 0;

        //先遍历饼干
        for(int i = 0;i < s.size(); i ++){
            if(index < g.size() && s[i] >= g[index]){
                index++;
                result++;
            }
        }
        return result;
    }
};

376. 摆动序列（C++贪心算法实现）

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= 1){
            return nums.size();
        }

        int preDiff = 0;
        int currDiff = 0;
        int result = 1;

        for(int i = 0;i < nums.size() - 1;i++){
            currDiff = nums[i + 1] - nums[i];
            //如果出现峰值
            if((preDiff >= 0 && currDiff < 0) || (preDiff <= 0 && currDiff > 0)){
                result ++;
                preDiff = currDiff;
            }
        }
        return result;
    }
};

53. 最大子数组和（C++贪心算法实现）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        //定义暂时保存的最大和变量count
        int count = 0;
        //单层for循环实现遍历
        for(int i = 0;i < nums.size();i++){
            //更新count
            count += nums[i];

            //判断count是否大于result，大于result的话直接更新result为count的值
            if(result < count){
                result = count;
            }

            //判断count是否小于等于0，如果是，表示当前nums[i]为负，那么就更count为nums[i+1]
            if(count <= 0){
                count = 0;
            }
        }
        return result;
    }
};

122. 买卖股票的最佳时机 II（C++贪心算法实现）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for(int i = 1;i < prices.size();i++){
            if(prices[i] - prices[i - 1] > 0){
                result += prices[i] - prices[i - 1];
            }
        }
        return result;
    }
};

122. 买卖股票的最佳时机 II（Java贪心算法实现）

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for(int i = 1;i < prices.length;i++){
            if(prices[i] - prices[i - 1] > 0){
                result += prices[i] - prices[i - 1];
            }
        }
        return result;
    }
}

55. 跳跃游戏（Java贪心算法实现）

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }

        int cover = 0;
        for(int i = 0;i <= cover;i++){
            if(i + nums[i] > cover){
                cover = i + nums[i];
            }

            if(cover >= nums.length - 1){
                return true;
            }
        }
        return false;
    }
}

45. 跳跃游戏 II（Java贪心算法实现）

class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        //当前定义的最小下标
        int currDistance = 0;
        int nextDistance = 0;
        int result = 0;
        for(int i = 0; i < nums.length;i++){
            nextDistance = Math.max(nums[i] + i, nextDistance);
            if(i == currDistance){
                result++;
                currDistance = nextDistance;
                if(nextDistance >= nums.length - 1){
                    break;
                }
            }
        }
        return result;
    }
}