Jump Game

+10

Kamu berada di indeks 0 pada array nums. Dari indeks i, kamu dapat melompat ke depan sebanyak langkah antara 1 hingga nums[i], jadi nums[i] adalah lompatan terjauhmu dari sana dan 0 berarti kamu tidak dapat bergerak. Kembalikan true jika ada rangkaian lompatan yang mendarat di indeks terakhir, dan false jika tidak.

Fungsi

canJump(nums: integer-array) → boolean

numsinteger-array: lompatan terjauh yang bisa kamu lakukan dari setiap indeks
Mengembalikanboolean: true jika kamu dapat mencapai indeks terakhir mulai dari indeks 0, jika tidak false

Batasan

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵
Lompatan bisa lebih pendek daripada nums[i], jadi lompatan jauh tidak akan memaksamu melewati indeks terakhir.

Contoh

Input: nums = [2, 0, 3, 1, 0, 2]
Output: true
Penjelasan: Dari indeks 0, kamu bisa mencapai indeks 1 atau 2. Indeks 1 berisi 0 dan merupakan jalan buntu, tetapi indeks 2 berisi 3 dan mencapai indeks 5, indeks terakhir.

Pertanyaan lanjutan

Hitung berbagai urutan lompatan yang mendarat di indeks terakhir, modulo 10^9+7, tetap dalam waktu O(n).

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Mencoba rute satu per satu membutuhkan waktu eksponensial. Perhatikan indeksnya: indeks yang bisa kamu jangkau selalu membentuk satu blok utuh yang dimulai dari indeks 0. Ujung kanan blok itu menyimpan semua yang kamu butuhkan, dan satu kali penelusuran menentukan jawabannya.

Coba setiap lompatan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Mulai dari indeks 0, coba setiap titik pendaratan secara bergiliran, lalu lakukan hal yang sama lagi dari setiap titik. Jika salah satu cabang mencapai indeks terakhir, jawabannya adalah true. Pencarian ini benar karena mencoba setiap rute.

Pencarian ini tidak pernah mengingat indeks yang sudah dijelajahi, jadi saat jawabannya false, pencarian harus memeriksa setiap rute. Dalam [4, 3, 2, 1, 0, 5], setiap indeks sebelum 0 dapat mencapai 0, sehingga ada 8 rute menuju indeks tersebut. Dengan 30 indeks seperti itu, jumlahnya lebih dari 500 juta.

Algoritma

Tulis fungsi pembantu reach(i) yang menjawab: bisakah kamu mencapai indeks terakhir dari indeks i?
Jika i adalah indeks terakhir, kembalikan true.
Jika tidak, coba setiap titik pendaratan next dari i+1 hingga min(i+nums[i], n-1), lalu kembalikan true segera setelah reach(next) mengembalikan nilai tersebut.
Jika tidak ada titik pendaratan yang berhasil, kembalikan false.
Jawabannya adalah reach(0).

def canJump(nums):
    last = len(nums) - 1

    def reach(i):
        # Can you get from index i to the last index?
        if i == last:
            return True
        for nxt in range(i + 1, min(i + nums[i], last) + 1):
            if reach(nxt):
                return True
        return False

    return reach(0)

Ingat indeks mana yang dapat menjadi akhir

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Sebut suatu indeks baik jika kamu bisa mencapai akhir dari indeks itu. Indeks terakhir adalah indeks baik, dan indeks i adalah indeks baik jika ada indeks dari i+1 sampai i+nums[i] yang merupakan indeks baik. Setiap indeks hanya bergantung pada indeks di sebelah kanannya, jadi isi tabel dari kanan ke kiri dan tentukan setiap indeks satu kali. Pada contoh pertama, indeks 2 mencapai indeks 5, jadi indeks itu baik, begitu juga indeks 0, yang mencapai indeks 2.

Menentukan satu indeks masih bisa memindai n sel. Dalam [9998, 9997, …, 1, 0, 7], setiap indeks mencapai 0 dan tidak mencapai apa pun setelahnya, jadi setiap indeks memindai seluruh rentangnya: sekitar 5 × 10^7 pemeriksaan untuk 10^4 elemen.

Algoritma

Buat array boolean good dengan panjang n, lalu tetapkan good[n-1] ke true.
Telusuri i dari n-2 turun hingga 0.
Periksa j dari i+1 hingga min(i+nums[i], n-1). Jika ada good[j] yang bernilai true, tetapkan good[i] ke true dan hentikan pemeriksaan.
Kembalikan good[0].

def canJump(nums):
    n = len(nums)
    good = [False] * n  # good[i]: from i you can reach the last index
    good[n - 1] = True
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, min(i + nums[i], n - 1) + 1):
            if good[j]:
                good[i] = True
                break
    return good[0]

Lacak indeks terjauh yang dapat dijangkau

Intuisi

Dari indeks yang dapat dijangkau i, kamu dapat mendarat di mana saja mulai dari i+1 hingga i+nums[i], tanpa celah. Rentang itu dimulai di dalam blok yang sudah dijangkau, sehingga blok bertambah tanpa celah dan selalu berupa [0, farthest].

Telusuri i dari kiri ke kanan. Selama i ≤ farthest, indeks i dapat dijangkau dan memperluas farthest menjadi max(farthest, i+nums[i]). Jika i melewati farthest, tidak ada indeks yang dapat dijangkau yang bisa melompat ke i, dan blok tidak akan pernah bisa melewati celah itu, sehingga indeks terakhir tidak dapat dijangkau. Menyimpan hanya ujung kanan tidak menghilangkan apa pun: kamu tidak pernah menetapkan lompatan, dan setiap titik pendaratan yang lebih dekat berada di dalam blok.

Pada contoh kedua, farthest berubah menjadi 0, 1, 4, lalu tetap 4 selama tiga angka nol. Indeks 5 melewatinya, sehingga jawabannya adalah false.

Algoritma

Tetapkan farthest = 0.
Untuk setiap indeks i dari kiri ke kanan: jika i > farthest, kembalikan false.
Jika tidak, tetapkan farthest = max(farthest, i+nums[i]).
Jika perulangan selesai, setiap indeks dapat dijangkau, jadi kembalikan true.

def canJump(nums):
    farthest = 0  # every index up to farthest can be reached
    for i, jump in enumerate(nums):
        if i > farthest:
            return False  # nothing reachable jumps to i
        farthest = max(farthest, i + jump)
    return True

Jebakan dan kasus tepi

Selalu melompat tepat sebanyak nums[i] langkah. Dengan [2, 5, 0, 0], lompatan penuh dari indeks 0 mendarat di angka 0, sedangkan lompatan 1 langkah ke indeks 1 mencapai akhir.
Mengembalikan false begitu kamu melihat angka 0. [2, 0, 1] melompati angka 0 dan jawabannya adalah true.
Memperbarui farthest sebelum memeriksa i > farthest. Indeks yang tidak dapat dijangkau tidak boleh memperpanjang rentang.
Menganggap array dengan satu elemen sebagai kegagalan. Kamu sudah berada di indeks terakhir, meskipun nilainya 0.
Menggunakan rekursi pada array yang panjang. Sebuah rute bisa terdiri dari 10,000 lompatan, yang menyebabkan stack pemanggilan meluap di beberapa bahasa. Secara default, Python berhenti setelah 1,000 pemanggilan bersarang.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Jump Game?

Pass jangkauan terjauh mengunjungi setiap indeks satu kali, jadi prosesnya berjalan dalam waktu O(n) dengan ruang ekstra O(1). Pendekatan tabel memiliki kompleksitas O(n²) dalam kasus terburuk, dan mencoba setiap rute membutuhkan waktu eksponensial.

Apakah Jump Game merupakan masalah pemrograman dinamis?

Bisa dilakukan dengan menandai setiap indeks sebagai baik jika salah satu titik pendaratannya baik, dari kanan ke kiri, dalam O(n²). Hanya indeks baik paling kiri yang ditemukan sejauh ini yang penting, karena indeks yang mencapai indeks baik mana pun di sebelah kanannya juga mencapai indeks tersebut. Pindahkan goal ke i setiap kali i+nums[i] ≥ goal.

Bagaimana cara menemukan jumlah lompatan minimum?

Gunakan gagasan jangkauan terjauh secara bertahap. Lacak ujung blok yang bisa kamu capai dengan jumlah lompatan saat ini dan indeks terjauh yang bisa dicapai pada lompatan berikutnya. Ketika i melewati ujung blok saat ini, hitung satu lompatan lagi dan perluas blok hingga indeks terjauh tersebut. Ini tetap satu lintasan O(n).

def canJump(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [2, 0, 3, 1, 0, 2]

Output yang diharapkan

true

Jump Game

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Coba setiap lompatan

Ingat indeks mana yang dapat menjadi akhir

Lacak indeks terjauh yang dapat dijangkau

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa