leetcode-notes-20230913

376. 摆动序列（Java贪心实现）

思路：先对数组进行升序排序，然后从后往前遍历胃口数组，遍历的同时去判断饼干数组是否有满足要求的数值，如果有，则结果返回变量result++。

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int preDiff = 0;
        int currDiff = 0;

        int result = 1;

        for(int i = 0;i < nums.length - 1;i++){
            currDiff = nums[i + 1] - nums[i];
            if((preDiff >= 0 &&currDiff < 0) || (preDiff <= 0 && currDiff > 0)){
                result ++;
                preDiff = currDiff;
            }
        }
        return result;
    }
}

53. 最大子数组和（Java贪心实现）

class Solution {
    public int maxSubArray(int[] nums) {
        //思路：首先遍历nums数组，定义count变量来记录从下标i开始的子数组元素累积和，如果出现count <= 0       //的情况，更新count = 0即可，从头开始记录。
        int count = 0;
        int result = Integer.MIN_VALUE;
        for(int i = 0;i < nums.length;i++){
            count += nums[i];

            if(result < count){
                result = count;
            }

            if(count <= 0){
                count = 0;
            }
        }
        return result;
    }
}

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

class Solution {
    public int maxProfit(int[] prices) {
        //思路：首先某一天既可以买入也可以卖出。如果假设在i天买入在第i+5天卖出，
        //实际上与从i天到i+5天每天买入和卖出，并取其中为正数的交易金额相加是一样的效果。
        int result = 0;
        for(int i = 0;i < prices.length - 1;i++){
            if(prices[i + 1] - prices[i] > 0){
                result += prices[i + 1] -prices[i];
            }
        }
        return result;
    }
}

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

class Solution {
    public boolean canJump(int[] nums) {
        //思路：定义一个cover变量保存从当前下标开始能覆盖的最大index，
        //如果cover大于或等于nums.length - 1，就表示能达到最后一个下标
        int cover = 0;
        
        if(nums.length == 1){
            return true;
        }

        for(int i = 0;i <= cover;i ++){
            //获得当前cover最大值
            cover = Math.max(i + nums[i], cover);

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

        return false;
    }
}

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

class Solution {
    public int jump(int[] nums) {
        //思路：定义两个变量currDistance和nextDistance，
        //其中currDistance表示从每次跳跃开始位置可以覆盖的最远坐标，
        //nextDistance表示从遍历的i开始，能达到的最远范围，
        //当i走到currDistance时，更新currDistance = nextDistance，表示从当前i位置开始
        //能到达的最远坐标范围，然后判断最远范围是否可以覆盖到数组最后，如果可以那么就break，
        //这样就可以保证以最小的次数跳跃到数组最后。
        
        //如果长度为0，那么不需要跳跃
        if(nums.length == 1){
            return 0;
        }

        int currDistance = 0;
        int result = 0;
        int nextDistance = 0;

        for(int i = 0;i < nums.length;i++){
            //得到当前能达到的最大坐标值nextDistance
            nextDistance = Math.max(i + nums[i], nextDistance);
            //表示到达了currDistance对应的坐标处
            if(i == currDistance){
                //更新currDistance
                currDistance = nextDistance;
                result ++;//跳跃次数增加1
                if(currDistance >= nums.length - 1){
                    break;
                }
            }
        }
        return result;
    }
}

1005. K 次取反后最大化的数组和（Java贪心实现）

//使用Java 8特性中的IntStream来实现
class Solution {
    public int largestSumAfterKNegations(int[] nums, int K) {
    	// 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
	nums = IntStream.of(nums)
		     .boxed()
		     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
		     .mapToInt(Integer::intValue).toArray();
	int len = nums.length;	    
	for (int i = 0; i < len; i++) {
	    //从前向后遍历，遇到负数将其变为正数，同时K--
	    if (nums[i] < 0 && K > 0) {
	    	nums[i] = -nums[i];
	    	K--;
	    }
	}
	// 如果K还大于0，那么反复转变数值最小的元素，将K用完

	if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
	return Arrays.stream(nums).sum();

    }
}



//使用带有排序规则器的方法实现
class Solution {

    static class AbsoluteValueComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer a, Integer b) {
            return Math.abs(b) - Math.abs(a);
        }
    }

    public int largestSumAfterKNegations(int[] nums, int K) {
        int len = nums.length;
        Integer[] numsInteger = new Integer[len];
        
        // 将 int[] 转换为 Integer[]
        for (int i = 0; i < len; i++) {
            numsInteger[i] = nums[i];
        }

    	// 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
        Arrays.sort(numsInteger, new AbsoluteValueComparator());

        //将排序后的numsInteger转为nums
        for (int i = 0; i < len; i++) {
            nums[i] = numsInteger[i];
        }

        for (int i = 0; i < len; i++) {
            //从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && K > 0) {
                nums[i] = -nums[i];
                K--;
            }
        }
        // 如果K还大于0，那么反复转变数值最小的元素，将K用完

        if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
        return Arrays.stream(nums).sum();
    }
}

134. 加油站（C++贪心算法实现）

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //使用贪心算法实现
        //思路：分三种情况，首先计算所有的gas[i] - cost[i]剩下的油总和是否小于0，
        //第三种情况：如果是，那么表示从哪里出发也无法转一圈；
        //第二种情况：如果min最小值大于0，表示从0出发可以达到；
        //第三种情况：如果min最小值为负数，那么从0开始判断，哪个位置的油可以使得min值变为大于0的数
        //那么这个位置i就是结果

        int currSum = 0;
        int min = INT32_MAX;

        for(int i = 0;i < gas.size();i++){
            int rest = gas[i] - cost[i];
            currSum += rest;
            if(currSum < min){
                min = currSum;
            }
        }

        if(currSum < 0){
            return -1;
        }

        if(min >= 0){
            return 0;
        }

        //情况三，从后向前遍历实现
        for(int i = gas.size() - 1;i >= 0;i--){
            int rest = gas[i] - cost[i];
            min += rest;
            if(min >= 0){
                return i;
            }
        }
        return -1;
    }
};