Algoritma LeetCode DayGreedy Bahagian 2

122. Masa Terbaik untuk Membeli dan Menjual Saham II

Anda diberi harga tatasusunan integer dengan harga[i] ialah harga saham tertentu pada hari ke-1.

Pada setiap hari, anda boleh membuat keputusan untuk membeli dan/atau menjual saham. Anda hanya boleh memegang paling banyak satu bahagian saham pada bila-bila masa. Walau bagaimanapun, anda boleh membelinya kemudian menjualnya dengan segera pada hari yang sama.

Cari dan pulangkan keuntungan maksimum yang anda boleh capai.

Contoh 1:

Input: harga = [7,1,5,3,6,4]
Keluaran: 7
Penjelasan: Beli pada hari ke-2 (harga = 1) dan jual pada hari ke-3 (harga = 5), untung = 5-1 = 4.
Kemudian beli pada hari ke-4 (harga = 3) dan jual pada hari ke-5 (harga = 6), untung = 6-3 = 3.
Jumlah keuntungan ialah 4 + 3 = 7.
Contoh 2:

Input: harga = [1,2,3,4,5]
Keluaran: 4
Penjelasan: Beli pada hari 1 (harga = 1) dan jual pada hari ke-5 (harga = 5), untung = 5-1 = 4.
Jumlah keuntungan ialah 4.
Contoh 3:

Input: harga = [7,6,4,3,1]
Output: 0
Penjelasan: Tidak ada cara untuk membuat keuntungan positif, jadi kami tidak pernah membeli saham untuk mencapai keuntungan maksimum 0.

Kekangan:

1 <= harga.panjang <= 3 * 104
0 <= harga[i] <= 104
Halaman Asal

Kod Salah

    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;
    }

Saya ini membeli ke int MAX_VALUE dan terlupa untuk mengemas kini ini mungkin membawa kepada beberapa ralat.

baiki ini dan potong kod

Kod Baik

    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. Maksimumkan Jumlah Tatasusunan Selepas K Negasi

Memandangkan nombor tatasusunan integer dan integer k, ubah suai tatasusunan dengan cara berikut:

pilih indeks i dan gantikan nums[i] dengan -nums[i].
Anda harus menggunakan proses ini tepat k kali. Anda boleh memilih indeks i yang sama beberapa kali.

Kembalikan jumlah terbesar tatasusunan yang mungkin selepas mengubah suainya dengan cara ini.

Contoh 1:

Input: angka = [4,2,3], k = 1
Keluaran: 5
Penjelasan: Pilih indeks 1 dan nombor menjadi [4,-2,3].
Contoh 2:

Input: angka = [3,-1,0,2], k = 3
Keluaran: 6
Penjelasan: Pilih indeks (1, 2, 2) dan nombor menjadi [3,1,0,2].
Contoh 3:

Input: nombor = [2,-3,-1,5,-4], k = 2
Keluaran: 13
Penjelasan: Pilih indeks (1, 4) dan nombor menjadi [2,3,-1,5,4].

Kekangan:

1 <= nums.length <= 10^4
-100 <= angka[i] <= 100
1 <= k <= 10^4
Halaman Asal

    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;
    }




</p>
<h2>
  
  
  55. Permainan Lompat
</h2>

<p>Anda diberi nombor tatasusunan integer. Anda pada mulanya diletakkan pada indeks pertama tatasusunan, dan setiap elemen dalam tatasusunan mewakili panjang lompatan maksimum anda pada kedudukan itu.</p>

<p>Kembalikan benar jika anda boleh mencapai indeks terakhir, atau palsu sebaliknya.</p>

<p>Contoh 1:</p>

<p>Input: nombor = [2,3,1,1,4]<br>
Output: benar<br>
Penjelasan: Lompat 1 langkah dari indeks 0 ke 1, kemudian 3 langkah ke indeks terakhir.<br>
Contoh 2:</p>

<p>Input: nombor = [3,2,1,0,4]<br>
Output: palsu<br>
Penjelasan: Anda akan sentiasa tiba di indeks 3 tidak kira apa pun. Panjang lompatan maksimumnya ialah 0, yang menjadikannya mustahil untuk mencapai indeks terakhir.</p>

<p>Kekangan:</p>

<p>1 <= nums.length <= 10^4<br>
0 <= angka[i] <= 10^5</p>
<h2>
  
  
  Kod Salah
</h2>


<pre class="brush:php;toolbar:false">    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;
    }


</p>
<h2>
  
  
  Kod Salah 2
</h2>


<pre class="brush:php;toolbar:false">    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. Permainan Lompat II

Anda diberi tatasusunan 0-indeks nombor integer dengan panjang n. Anda pada mulanya diletakkan di nums[0].

Setiap elemen nombor[i] mewakili panjang maksimum lompatan hadapan dari indeks i. Dalam erti kata lain, jika anda berada di nums[i], anda boleh melompat ke mana-mana nums[i + j] di mana:

0 <= j <= angka[i] dan
i + j < n
Kembalikan bilangan lompatan minimum untuk mencapai angka[n - 1]. Kes ujian dijana supaya anda boleh mencapai nombor[n - 1].

Contoh 1:

Input: nombor = [2,3,1,1,4]
Keluaran: 2
Penjelasan: Bilangan lompatan minimum untuk mencapai indeks terakhir ialah 2. Lompat 1 langkah dari indeks 0 ke 1, kemudian 3 langkah ke indeks terakhir.
Contoh 2:

Input: nombor = [2,3,0,1,4]
Keluaran: 2

Kekangan:

1 <= nums.length <= 104
0 <= angka[i] <= 1000
Ia dijamin bahawa anda boleh mencapai nombor[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){
                step++;
                break;
            }
            if(i == preRange){
                preRange = range;
                step++;
            }

        }
        return step;

    }





          

            
        
Atas ialah kandungan terperinci Algoritma LeetCode DayGreedy Bahagian 2. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!