LeetCode Day 贪心算法 第 2 部分

122. 买卖股票的最佳时机 II

给你一个整数数组prices，其中prices[i]是给定股票第i天的价格。

每天，您都可以决定购买和/或出售股票。您在任何时候最多只能持有一股股票。不过，您可以购买并在当天立即出售。

找到并返回您可以获得的最大利润。

示例1：

输入：价格 = [7,1,5,3,6,4]
输出：7
说明：第 2 天买入（价格 = 1），第 3 天卖出（价格 = 5），利润 = 5-1 = 4。
然后在第 4 天买入（价格 = 3）并在第 5 天卖出（价格 = 6），利润 = 6-3 = 3。
总利润为 4 + 3 = 7。
示例2：

输入：价格 = [1,2,3,4,5]
输出：4
说明：第 1 天买入（价格 = 1），第 5 天卖出（价格 = 5），利润 = 5-1 = 4。
总利润为 4。
示例 3：

输入：价格 = [7,6,4,3,1]
输出：0
说明：没有办法盈利，所以我们从来不买股票来实现最大利润0。

限制：

1 0 原始页面

错误代码

    public int maxProfit(int[] prices) {
        int profit = 0;
        int buy = Integer.MAX_VALUE;
        int sum = 0;
        int peek = 0;

        for(int i=0; i<prices.length; i++){
            int num = prices[i];
            if(num > buy && num > peek){
                profit = num - buy;
                peek = num;
            }
            else if((num>buy && num<peek) || num < buy){
                sum += profit;
                profit = 0;
                buy = num;
                peek = num;
            }

        }

        return sum+profit;
    }

我初始化购买 int MAX_VALUE 并忘记更新，这可能会导致一些错误。

修复此问题并截断代码

精细代码

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }
        int profit = 0;
        int buy = prices[0];
        int sum = 0;
        int peek = prices[0];

        for(int i=0; i<prices.length; i++){
            int num = prices[i];
            if( num > peek){
                profit = num - buy;
                peek = num;
            }
            else if(num<peek){
                sum += profit;
                profit = 0;
                buy = num;
                peek = num;
            }

        }
        sum += profit;
        return sum;
    }

1005. K 个否定后数组的和最大化

给定一个整数数组 nums 和一个整数 k，按以下方式修改该数组：

选择一个索引 i 并将 nums[i] 替换为 -nums[i]。
您应该准确应用此过程 k 次。您可以多次选择相同的索引 i。

以这种方式修改数组后，返回数组可能的最大和。

示例1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择索引 1，nums 变为 [4,-2,3]。
示例2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择索引 (1, 2, 2)，nums 变为 [3,1,0,2]。
示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择索引 (1, 4)，nums 变为 [2,3,-1,5,4]。

限制：

1 <= nums.length <= 10^4
-100 <= nums[i] <= 100
1 <= k <= 10^4
原始页面

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int change = nums[nums.length-1] >=0?0:nums.length-1;
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0 && k>0){

                sum  -= nums[i];
                k--;
            }else{
                sum += nums[i];
            }
            // find the cross over 
            if(i>0 && nums[i-1]<=0 && nums[i]>0){
                if(-nums[i-1]>nums[i]){
                    change = i;
                }else{
                    change = i-1;
                }    
            }  
        }
        // k>nums.length so we need to run out of these k
        if(k>0){
            if(k%2!=0){
                //find the min abs value
                sum -= 2*Math.abs(nums[change]);
            }
        }
        return sum;
    }

55. 跳跃游戏

给你一个整数数组 nums。您最初位于数组的第一个索引处，数组中的每个元素代表您在该位置的最大跳跃长度。

如果可以到达最后一个索引，则返回 true，否则返回 false。

示例1：

输入：nums = [2,3,1,1,4]
输出：true
说明：从索引 0 跳 1 步到 1，然后跳 3 步到最后一个索引。
示例2：

输入：nums = [3,2,1,0,4]
输出：假
说明：无论如何，你总是会到达索引 3。它的最大跳转长度为0，这使得它无法到达最后一个索引。

限制：

1 0

错误代码

    public boolean canJump(int[] nums) {
        //find whether achive the last element so that we only can see whether can reach the second last element 
        for(int i=0; i<nums.length-1;){
            int size = nums[i];
            int next = 0;
            int nextVal = 0;
            if(size == 0){
                return false;
            }
            if(i+size >= nums.length){
                return true;
            }
            //find the max steps among the current step
            for(int j=0; j<=size; j++){
                // calculate max for both index and value
                if(i+j+nums[i+j]>next){
                    next = i+j+nums[i+j];
                }
            }
            i = next;
        }
        return true;
    }

错误代码2

    public boolean canJump(int[] nums) {
        if(nums.length==1){

            return true;
        }

        if(nums[0] == 0){
            return false;
        }

        for(int i=0; i<nums.length-1; i++){
            if(i+nums[i]>=nums.length-1){
                return true;
            }
        }

        return false;
    }

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

        int range = 0;

        for(int i=0; i<=range; i++){
            range = Math.max(range, i+nums[i]);
            if(range >= nums.length-1){
                return true;
            }
        }

        return false;
    }

45. 跳跃游戏二

给定一个长度为 n 的 0 索引整数 nums 数组。您最初位于 nums[0].

每个元素nums[i]代表从索引i向前跳转的最大长度。换句话说，如果你在 nums[i]，你可以跳转到任何 nums[i + j]，其中：

0 i+j＜ n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以达到 nums[n - 1]。

示例1：

输入：nums = [2,3,1,1,4]
输出：2
说明：到达最后一个索引的最小跳转次数为 2。从索引 0 到 1 跳转 1 步，然后跳转 3 步到最后一个索引。
示例2：

输入：nums = [2,3,0,1,4]
输出：2

限制：

1 0 保证你能达到nums[n - 1]。

    public int jump(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int step = 0;
        int range = 0;
        int preRange = 0;
        for(int i=0; i<nums.length-1; i++){
            range = Math.max(range, i+nums[i]);
            if(range >= nums.length-1){
                step++;
                break;
            }
            if(i == preRange){
                preRange = range;
                step++;
            }

        }
        return step;

    }

以上是LeetCode Day 贪心算法 第 2 部分的详细内容。更多信息请关注PHP中文网其他相关文章！