LeetCode Day貪欲なアルゴリズム パート 2

122. 株式の売買に最適な時期 II

整数配列の 価格 が与えられます。ここで、prices[i] は i 日目の特定の株式の価格です。

毎日、株式を購入または売却するか、あるいはその両方を決定で​​きます。いつでも保有できる株式は最大 1 株のみです。ただし、購入してその日にすぐに売ることは可能です。

達成可能な最大利益を見つけて返します。

例 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 <= 数値[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]
出力: false
説明: 何があってもインデックス 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 の整数 num からなる 0 から始まるインデックスの配列が与えられます。最初は nums[0] に位置しています。

各要素 nums[i] は、インデックス i からの前方ジャンプの最大長を表します。つまり、nums[i] にいる場合は、次のいずれかの nums[i + j] にジャンプできます。

0 i + j 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 中国語 Web サイトの他の関連記事を参照してください。