Prompt dan konteks
Ini ialah masalah tamak dengan kekangan sumber. Bahan api hanya boleh diambil daripada stesen yang telah dilalui, dan objektifnya ialah bilangan hentian dan bukannya jumlah bahan api. Jawapan temu duga yang mantap menghubungkan kebolehcapaian, keputusan tertangguh (lazy decisions), batas tak berubah max-heap, dan segmen akhir dari stesen terakhir ke sasaran.
Perkara yang dinilai oleh penemu duga
- Sama ada anda menukar "isi bahan api hanya apabila perlu" kepada strategi lazy greedy.
- Sama ada anda membuktikan bahawa mengambil bahan api terbesar yang telah dilalui tidak boleh meningkatkan kiraan hentian optimum.
- Sama ada anda mengendalikan permulaan, sasaran, kedudukan pendua, dan kes yang tidak dapat dicapai.
- Sama ada anda menyediakan pelaksanaan masa O(n log n) dan ruang O(n).
Soalan penjelasan
Sahkan bahawa stesen disusun mengikut kedudukan, sama ada kedudukan pendua dibenarkan, bahawa bahan api adalah bukan negatif, dan sama ada sasaran itu sendiri ialah sebuah stesen. Tanya tentang saiz input dan julat integer. Model lalai bermula pada kedudukan 0 dan membenarkan bahan api daripada stesen hanya selepas mencapainya.
Garis besar jawapan 30 saat
Imbas stesen mengikut kedudukan dan tolak (push) setiap jumlah bahan api yang dilalui ke dalam max heap. Sebelum sampai ke setiap stesen seterusnya atau sasaran, tolak jarak. Jika bahan api menjadi negatif, hentian dipaksa, jadi pop bahan api terbesar yang dilalui berulang kali dan tingkatkan kiraan hentian. Jika heap kosong, kembalikan -1. Memilih bahan api terbesar yang tersedia pada setiap hentian paksa memaksimumkan jarak yang boleh dicapai tanpa meningkatkan bilangan hentian.
Penyelesaian langkah demi langkah
1. Wujudkan batas tak berubah kebolehcapaian
Pada kedudukan p, heap mengandungi bahan api dari setiap stesen pada atau sebelum p, manakala fuel ialah jumlah yang tidak digunakan. Jika jumlah bahan api adalah negatif, kemajuan adalah mustahil tanpa menggunakan salah satu daripada stesen tersebut. Setiap pop meluaskan julat yang boleh dicapai sehingga jumlah bahan api menjadi bukan negatif semula.
2. Buktikan pilihan lazy greedy
Andaikan pelan optimum memilih jumlah yang dilalui yang lebih kecil a apabila ia mesti mengisi bahan api, manakala jumlah yang lebih besar b tersedia. Gantikan a dengan b: kiraan hentian tidak berubah dan baki bahan api selepas titik ini tidak berkurangan, jadi setiap segmen kemudiannya kekal boleh dilaksanakan. Mengulangi pertukaran ini menghasilkan pelan yang sama optimum yang sentiasa memilih nilai maksimum.
3. Rawat sasaran sebagai sempadan
Tambahkan stesen maya (target, 0) dan prosesnya sama seperti setiap kedudukan lain. Mulakan dari kedudukan 0, tolak setiap jarak, dan hanya kemudian tambah bahan api stesen. Jika sasaran masih memerlukan pop, hentian tersebut dikira; heap yang kosong semasa bahan api negatif bermakna sasaran tidak dapat dicapai.
4. Laksanakan heap
heapq Python ialah min heap, jadi nilai bahan api negatif mensimulasikan max heap. Setiap stesen ditolak sekali dan dipop hanya apabila hentian diperlukan:
import heapq
def min_refuel_stops(target, start_fuel, stations):
fuel = start_fuel
previous = 0
max_heap = []
stops = 0
for position, station_fuel in [*stations, (target, 0)]:
fuel -= position - previous
while fuel < 0 and max_heap:
fuel += -heapq.heappop(max_heap)
stops += 1
if fuel < 0:
return -1
heapq.heappush(max_heap, -station_fuel)
previous = position
return stops5. Analisis kerumitan dan sempadan
Dengan n stesen, setiap nilai bahan api masuk dan keluar dari heap paling banyak sekali, memberikan masa O(n log n) dan ruang heap O(n). Uji bahan api awal yang mencukupi, stesen pertama yang tidak dapat dicapai, hentian yang diperlukan selepas stesen terakhir, sifar bahan api, kedudukan pendua, ketibaan sasaran yang tepat, dan sasaran yang tidak dapat dicapai.
Contoh jawapan berkualiti tinggi
Saya akan menambahkan sasaran sebagai stesen maya sifar bahan api. Semasa imbasan, tolak jarak perjalanan dan tolak bahan api dari stesen yang telah dicapai. Setiap kali baki bahan api adalah negatif, hentian dipaksa; ambil bahan api sejarah terbesar berulang kali sehingga kedudukan semasa boleh dicapai. Heap yang kosong bermaksud -1. Bukti pertukaran menggantikan mana-mana bahan api yang dilalui yang lebih kecil yang dipilih dengan bahan api lebih besar yang tersedia tanpa meningkatkan hentian atau mengurangkan kebolehcapaian masa hadapan. Setiap stesen ditolak dan dipop paling banyak sekali, jadi kerumitannya ialah masa O(n log n) dan ruang O(n).
Kesilapan biasa
- Mengisi bahan api serta-merta di setiap stesen dan bukannya melambatkan keputusan.
- Menyemak jurang antara stesen sahaja dan melupakan jurang sasaran akhir.
- Mencampurkan bahan api semasa yang tidak digunakan dengan bahan api yang tersedia dalam heap.
- Menggunakan min heap dan mengambil jumlah terkecil.
- Menambah stesen sebelum mencapainya dan menggunakan bahan api masa hadapan lebih awal.
- Menguji contoh yang boleh dicapai sahaja dan terlepas heap kosong atau sempadan berangka.
Soalan susulan
Mengapa tidak mengambil maksimum di setiap stesen?
Objektifnya ialah kiraan hentian. Pengisian bahan api awal boleh menambah hentian tanpa meningkatkan kebolehcapaian. Melambatkan sehingga bahan api tidak mencukupi memastikan setiap hentian menjawab kekangan sebenar.
Apakah yang berubah jika pengisian bahan api separa dibenarkan?
Keadaan dan fungsi kos berubah. Harga atau kapasiti tangki mungkin penting, jadi bukti untuk mengambil keseluruhan bahan api stesen tidak lagi terpakai secara langsung.
Mengapakah kedudukan pendua berfungsi?
Jaraknya adalah sifar, jadi ia boleh ditolak dalam sebarang susunan. Heap masih mendedahkan jumlah terbesar yang tersedia apabila segmen kemudian benar-benar memerlukan bahan api.
Bagaimanakah anda akan mengembalikan hentian sebenar?
Simpan indeks stesen dengan setiap nilai heap dan rekod indeks setiap kali ia dipop. Isih indeks yang direkodkan mengikut kedudukan atau susunan pemilihan untuk membina semula laluan.