Jumlah lompatan minimum untuk mencapai hujung menggunakan java

Kod Java ini mengira lompatan minimum yang diperlukan untuk melintasi array, di mana setiap elemen mewakili jarak lompat maksimum dari kedudukan tersebut. Mari kita meneroka algoritma dan kod langkah demi langkah. Matlamatnya adalah untuk mencari lompatan paling sedikit yang diperlukan untuk mencapai hujung array, bermula dari indeks 0. Jika akhir tidak dapat dicapai, fungsi kembali -1.

Definisi Masalah:

Diberi array

, di mana setiap elemen arr[] menunjukkan bilangan maksimum langkah yang boleh anda ambil dari kedudukan itu, tentukan bilangan lompatan minimum untuk mencapai indeks terakhir. arr[i]

Algoritma:

Algoritma menggunakan pendekatan tamak, melangkah melalui array dan menjejaki indeks yang boleh dicapai paling jauh (

) pada setiap langkah. Ia mengekalkan kaunter maxReach dan jumps untuk menjejaki kemajuan dalam setiap lompat. steps

1. Inisialisasi:

   • : Mengira jumlah lompatan. Diasaskan kepada 0. jumps
   • : Indeks paling jauh dapat dicapai dari kedudukan semasa. Inisialisasi ke maxReach. arr[0]
   • : bilangan langkah yang tinggal di dalam lompatan semasa. Inisialisasi ke steps. arr[0]

2. iTeration:

   kod itu melangkah melalui array.
   untuk setiap elemen
   • : arr[i]
     kemas kini
     • ke maksimum maxReach dan maxReach (indeks yang boleh dicapai paling jauh dari kedudukan semasa). i arr[i]
     penurunan
     • (kami telah mengambil satu langkah). steps
     Jika
     • menjadi 0, ini bermakna kita telah meletihkan langkah -langkah lompat semasa. Oleh itu: steps
       kenaikan
       • . jumps
       Jika
       • kurang daripada atau sama dengan maxReach, ini bermakna kita terjebak dan tidak dapat mencapai lebih jauh. Kembali -1. i
       reset
       • ke steps (langkah -langkah yang tinggal di lompat seterusnya). maxReach - i

3. Penamatan:

   Jika gelung selesai tanpa kembali -1, ini bermakna akhir dapat dicapai. Fungsi ini kembali
   • . jumps

Java Code:

public class MinJumpsToEnd {
    public static int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) return 0; // Already at the end or empty array

        int jumps = 0;
        int maxReach = arr[0];
        int steps = arr[0];

        for (int i = 1; i < n; i++) {
            maxReach = Math.max(maxReach, i + arr[i]); // Update maxReach
            steps--; // Decrement steps

            if (steps == 0) { // Jump needed
                jumps++;
                if (maxReach <= i) return -1; // Unreachable
                steps = maxReach - i; // Reset steps for next jump
            }
            if (i == n-1) return jumps; // Reached the end

        }
        return jumps;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 1, 2, 4, 2, 0, 1, 1};
        System.out.println("Minimum jumps required: " + minJumps(arr)); // Output: 4
    }
}

kerumitan masa dan ruang:

• kerumitan masa: o (n), di mana n adalah panjang array. Kod itu melangkah melalui array sekali.
• kerumitan ruang: o (1), kerana algoritma menggunakan jumlah ruang tambahan yang tetap.

Penjelasan dan kod yang lebih baik ini memberikan pemahaman yang lebih jelas tentang algoritma dan pelaksanaannya. Komen tambahan meningkatkan kebolehbacaan dan pengendalian kes kelebihan (array kosong atau tunggal) menjadikan kod itu lebih mantap.

Atas ialah kandungan terperinci Jumlah lompatan minimum untuk mencapai hujung menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!