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中文網其他相關文章！