Max Consecutive Ones

Q: Berapa kompleksitas waktu Max Consecutive Ones?

Solusi satu lintasan berjalan dalam waktu O(n) , karena membaca setiap nilai satu kali, dan menggunakan ruang ekstra O(1) : satu penghitung untuk rentetan saat ini dan satu untuk rentetan terbaik. Memulai ulang hitungan pada setiap indeks membutuhkan O(n²) pada array yang berisi semua angka 1.

Q: Mengapa penghitung kembali ke 0, bukan 1?

Penghitung menyimpan panjang perulangan yang berakhir pada indeks saat ini. Saat nilainya 0 , tidak ada perulangan angka 1 yang berakhir di sana, jadi panjangnya adalah 0 . Angka 1 berikutnya menaikkan nilainya menjadi 1 , yaitu panjang perulangan baru.

Q: Apakah Max Consecutive Ones merupakan masalah sliding window?

Kamu bisa melihatnya sebagai satu: window menyimpan proses yang sedang berjalan, tepi kanannya bergerak pada setiap nilai, dan 0 menggeser tepi kirinya melewati nilai itu. Window tidak pernah mengecil selangkah demi selangkah, jadi satu penghitung menggantikan kedua tepi.

PemulaArray dan string

+10

Kamu mendapatkan sebuah array nums yang setiap nilainya adalah 0 atau 1. Run adalah rangkaian angka 1 yang bersebelahan tanpa 0 di antaranya. Kembalikan panjang run terpanjang, atau 0 jika array tidak berisi angka 1 sama sekali.

Fungsi

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: array yang berisi 0 dan 1
Mengembalikaninteger: panjang rangkaian 1 berurutan terpanjang

Batasan

1 ≤ nums.length ≤ 2 × 10⁴
Setiap nums[i] bernilai 0 atau 1.

Contoh

Input: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Output: 3
Penjelasan: Angka 1 membentuk tiga perulangan: indeks 0 sampai 1 (panjang 2), 3 sampai 5 (panjang 3), dan indeks 7 saja (panjang 1). Yang terpanjang memiliki panjang 3.

Input: nums = [0, 1, 0, 1, 1]
Output: 2
Penjelasan: Angka 1 tunggal pada indeks 1 kalah dari pasangan pada indeks 3 dan 4, jadi jawabannya adalah 2.

Input: nums = [0, 0, 0]
Output: 0
Penjelasan: Tidak ada angka 1 di mana pun, jadi tidak ada perulangan dan jawabannya adalah 0.

Pertanyaan lanjutan

Apa yang terjadi jika kamu boleh mengubah hingga k angka nol menjadi angka satu? Seberapa panjang perulangan terpanjang yang bisa kamu dapatkan, dan apakah kamu masih bisa menemukannya dalam satu kali lintasan?

Petunjuk

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

0 dari 3 dibuka

Solusi

Suatu rentetan berakhir saat 0 muncul, jadi pada setiap indeks kamu hanya perlu mengetahui panjang rentetan yang berakhir di sana. Satu pencacah yang bertambah saat menemukan 1 dan diatur ulang saat menemukan 0 akan menemukan rentetan terpanjang dalam satu kali pemindaian.

Hitung maju dari setiap indeks

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Coba setiap indeks sebagai titik awal, lalu telusuri ke depan selama kamu melihat angka 1. Jumlah langkahnya adalah panjang rangkaian yang dimulai dari indeks tersebut. Rangkaian terpanjang dimulai dari salah satu indeks ini, jadi jumlah terbesar adalah jawabannya.

Penelusuran ini saling tumpang tindih. Pada array yang berisi n angka 1, penelusuran membutuhkan sekitar n² / 2 langkah, yaitu 2 × 10^8 untuk n = 2 × 10^4.

Algoritma

Tetapkan best = 0.
Untuk setiap indeks start, tetapkan length = 0.
Selama start + length berada di dalam array dan nums[start + length] bernilai 1, tambahkan 1 ke length.
Simpan nilai yang lebih besar antara best dan length.
Kembalikan best.

def findMaxConsecutiveOnes(nums):
    n = len(nums)
    best = 0
    for start in range(n):
        length = 0
        while start + length < n and nums[start + length] == 1:
            length += 1
        best = max(best, length)
    return best

Satu kali penelusuran dengan penghitung yang terus bertambah

Intuisi

Pertahankan current, panjang rangkaian angka 1 yang berakhir di indeks yang sedang kamu periksa. Angka 1 memperpanjang rangkaian itu satu angka, sedangkan angka 0 mengakhirinya, sehingga current kembali menjadi 0. Setiap rangkaian diukur pada indeks terakhirnya, saat current sama dengan panjang penuh rangkaian itu, jadi nilai terbesar yang dicapai current adalah jawabannya.

Pada [1, 1, 0, 1, 1, 1, 0, 1], nilai current berturut-turut adalah 1, 2, 0, 1, 2, 3, 0, 1, dan nilai terbesarnya adalah 3.

Algoritma

Tetapkan best = 0 dan current = 0.
Untuk setiap nilai dalam nums: jika nilainya 1, tambahkan 1 ke current dan simpan nilai yang lebih besar antara best dan current.
Jika nilainya 0, tetapkan current = 0.
Kembalikan best.

def findMaxConsecutiveOnes(nums):
    best = 0
    current = 0
    for x in nums:
        if x == 1:
            current += 1
            best = max(best, current)
        else:
            # A 0 breaks the run.
            current = 0
    return best

Jebakan dan kasus tepi

Memperbarui best hanya saat kamu menemukan 0. Perulangan yang mencapai akhir, seperti [0, 1, 1], tidak pernah dicatat. Perbarui setelah setiap angka 1, atau lakukan perbandingan sekali lagi setelah perulangan.
Tidak mengatur ulang current saat menemukan 0. Beberapa perulangan terpisah akan dijumlahkan, dan [1, 1, 0, 1, 1] menghasilkan 4.
Memulai best dari 1 atau dari nums[0]. [0, 0, 0] harus menghasilkan 0.
Di Lua dan R, yang array-nya dimulai dari 1, membatasi penelusuran maju dengan < n alih-alih ≤ n. Nilai terakhir tidak pernah dibaca, sehingga [0, 1] menghasilkan 0.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Max Consecutive Ones?

Solusi satu lintasan berjalan dalam waktu O(n), karena membaca setiap nilai satu kali, dan menggunakan ruang ekstra O(1): satu penghitung untuk rentetan saat ini dan satu untuk rentetan terbaik. Memulai ulang hitungan pada setiap indeks membutuhkan O(n²) pada array yang berisi semua angka 1.

Mengapa penghitung kembali ke 0, bukan 1?

Penghitung menyimpan panjang perulangan yang berakhir pada indeks saat ini. Saat nilainya 0, tidak ada perulangan angka 1 yang berakhir di sana, jadi panjangnya adalah 0. Angka 1 berikutnya menaikkan nilainya menjadi 1, yaitu panjang perulangan baru.

Apakah Max Consecutive Ones merupakan masalah sliding window?

Kamu bisa melihatnya sebagai satu: window menyimpan proses yang sedang berjalan, tepi kanannya bergerak pada setiap nilai, dan 0 menggeser tepi kirinya melewati nilai itu. Window tidak pernah mengecil selangkah demi selangkah, jadi satu penghitung menggantikan kedua tepi.

def findMaxConsecutiveOnes(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [1, 1, 0, 1, 1, 1, 0, 1]

Output yang diharapkan