贪心专题01

第一题：力扣455题

解题思路：

使用贪心算法，只要满足局部最优解，最后就可以得到全局最优的解！
从数组的后边往前边依次遍历，满足大饼干给胃口大的孩子吃，最后就是尽可能地满足所有孩子的需求！

代码如下：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int sIndex = s.length - 1;
        int res = 0;

        for(int i = g.length - 1; i >= 0; i--) {
            if(sIndex >= 0 && s[sIndex] >= g[i]) {
                res++;
                sIndex--;
            }
        }
        return res;
    }
}

第二题：力扣376题

解题思路：

摆动序列相当于单调递增或单调递减交错进行，把中间的数省略掉即可。

代码如下：

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1) {
            return nums.length;
        }
        int curDiff = 0;
        int preDiff = 0;
        int res = 1;//默认最右边有个峰值
        for(int i = 0; i < nums.length - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            //只要满足摆动数列，res就加加
            if(curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
                res++;
                preDiff = curDiff;
            }
        }
        return res;
    }
}

第三题：力扣53题

解题思路：

参见代码详解

代码如下：

class Solution {
    //贪心算法
    public int maxSubArray(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }
        int res = Integer.MIN_VALUE;
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            //开始累加
            count += nums[i];
            //找连续和最大值
            if(count > res) {
                res = count;
            }
            //只要count出现负值了，就从下一个数重新计算
            if(count < 0) {
                count = 0;
            }
        }
        return res;
    }
}

当时没有学习动态规划解题，现在爬楼回来补上之前落下的，记2022.3.8

动态规划解题思路：

dp[i]：包括下标i之前的最大连续子序列和为dp[i]。
dp[i]怎么推导过来的呢？？？
无非就两条路：其一就是 dp[i-1] + nums[i] ，也就是前i-1个数再加上第i个数； 其二就是nums[i]本身 ，从这里重新开始。二者取最大即可。

代码如下：

//动态规划
class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if(res < dp[i]) {
                res = dp[i];
            }
        }
        return res;
    }
}

第四题：力扣122题

解题思路：

详见代码详解，贪心算法的思路我感觉有点说不清，哈哈哈，总之找出局部最优解就是最后的全局最优解，就要用贪心算法。

代码如下：

class Solution {
    public int maxProfit(int[] prices) {
        //贪心解决该问题：
        int res = 0;
        //把i天的股票价格中 抽取出 i-1 天的股票差价，我们只要把差价 为正 的数加起来就是最大利润
        for(int i = 1; i < prices.length; i++) {
            res += Math.max(prices[i] - prices[i - 1], 0);
        }
        
        return res; 
    }
}

第五题：力扣55题

解题思路：

将移动问题转换成炮弹射程问题比较好理解，哈哈！
详解见代码注释！！！

代码如下：

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1) {
            return true;
        }
        int step = 0;
        //在当前能达到的范围内一步一步地移动
        for(int i = 0; i <= step; i++) {
            //每移动一步，更新一次step
            step = Math.max(step, i + nums[i]);
            //只要是step能够达到数组的最后一个下标位置，就返回true
            if(step >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

该题的升级版：力扣45题

解题思路：

类似与上一个题，只不过这次需要求出最小次数，详解见代码注释。

代码如下：

class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1) {
            return 0;
        }
        int maxDistance = 0;//整体覆盖最大距离
        int curDistance = 0;//当前覆盖最大距离
        int res = 0;//结果
        //在当前能达到的范围内一步一步地移动
        for(int i = 0; i < nums.length; i++) {
            //更新最大距离
            maxDistance = Math.max(maxDistance, i + nums[i]);
            //只要覆盖到了最后，res++，之后跳出循环
            if(maxDistance >= nums.length - 1) {
                res++;
                break;
            }
            //如果到了当前最大范围还没有到达数组最后一个元素，那就更新当前最大距离
            if(curDistance == i) {
                curDistance = maxDistance;
                res++;
            }
        }
        return res;
    }
}

第六题：力扣1005题

解题思路：

第一步：将数组按照大小从大到小排序
第二步：从前向后遍历，遇到负数将其变为正数，同时K–
第三步：求和
第四步：如果此时K用完了，那就直接返回res；如果K还大于0，K为偶数，不用变了，直接返回res；K为奇数，用res减去2倍的最小正数，返回。

代码如下：

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 排序，把可能有的负数排到前面
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 贪心：如果是负数，而k还有剩余，就把负数反过来
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
            //绝对值全加起来
            sum += nums[i];
        }
        Arrays.sort(nums);
        // 如果k没剩，那说明能转的负数都转正了，已经是最大和，返回sum
        // 如果k有剩，说明负数已经全部转正，所以如果k还剩偶数个就自己抵消掉，不用删减，如果k还剩奇数个就减掉2倍最小正数。
        return sum - (k % 2 == 0 ? 0 : 2 * nums[0]); 
    }
}

第七题：力扣134题

解题思路：

实在是想不到，参考人家这个自己写了一下Java代码！！！

代码如下：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //贪心解决
        int curSum = 0;
        int totalSum = 0;
        int res = 0;
        for(int i = 0; i < gas.length; i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            totalSum += rest;
            //只要出现前几个和为0，说明车是跑不到这个加油站的，那就以下个加油站为起点跑
            if(curSum < 0) {
                res = i + 1;
                curSum = 0;
            }
        }
        //总的剩余油量rest小于0，根本不可能跑完一圈
        if(totalSum < 0) {
            return -1;
        }
        return res;
    }
}

今天不行了，肝不动了，休战，哇哈哈哈哈！明日大战三百回合===>