Max Consecutive Ones

Q: Độ phức tạp thời gian của Max Consecutive Ones là bao nhiêu?

Lời giải duyệt một lượt chạy trong thời gian O(n) vì nó đọc mỗi giá trị một lần và dùng thêm O(1) dung lượng: một biến đếm cho chuỗi liên tiếp hiện tại và một biến cho chuỗi dài nhất. Đếm lại từ đầu tại mỗi chỉ số sẽ mất O(n²) với một mảng toàn số 1.

Q: Tại sao bộ đếm trở về 0 thay vì 1?

Biến đếm lưu độ dài của chuỗi liên tiếp kết thúc tại chỉ số hiện tại. Khi giá trị tại đó là 0 , không có chuỗi liên tiếp nào gồm các số 1 kết thúc tại đó, nên độ dài là 0 . Số 1 tiếp theo làm tăng giá trị này lên 1 , tức là độ dài của chuỗi liên tiếp mới.

Q: Max Consecutive Ones có phải là bài toán cửa sổ trượt không?

Bạn có thể xem nó như một cửa sổ: cửa sổ chứa lần chạy hiện tại, cạnh phải dịch chuyển theo mỗi giá trị, còn 0 khiến cạnh trái vượt qua nó. Cửa sổ không thu hẹp từng bước, vì vậy một bộ đếm có thể thay thế hai cạnh.

Người mớiMảng và chuỗi

+10

Bạn nhận được một mảng nums trong đó mỗi giá trị là 0 hoặc 1. Một dãy liên tiếp là một đoạn gồm các số 1 nằm cạnh nhau, không có 0 nào ở giữa. Hãy trả về độ dài của dãy liên tiếp dài nhất, hoặc 0 nếu mảng không có số 1 nào.

Hàm

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: một mảng gồm các số 0 và 1
Trả vềinteger: độ dài của dãy số 1 liên tiếp dài nhất

Ràng buộc

1 ≤ nums.length ≤ 2 × 10⁴
Mỗi nums[i] là 0 hoặc 1.

Ví dụ

Đầu vào: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Đầu ra: 3
Giải thích: Các số 1 tạo thành ba đoạn: từ chỉ số 0 đến 1 (độ dài 2), từ 3 đến 5 (độ dài 3) và riêng chỉ số 7 (độ dài 1). Đoạn dài nhất có độ dài 3.

Đầu vào: nums = [0, 1, 0, 1, 1]
Đầu ra: 2
Giải thích: Số 1 đơn lẻ ở chỉ số 1 không lớn bằng cặp số ở các chỉ số 3 và 4, nên đáp án là 2.

Đầu vào: nums = [0, 0, 0]
Đầu ra: 0
Giải thích: Không có số 1 nào, nên không có đoạn liên tiếp nào và đáp án là 0.

Câu hỏi mở rộng

Bạn có thể đổi tối đa k số 0 thành số 1 không? Đoạn liên tiếp dài nhất có thể dài bao nhiêu, và bạn vẫn có thể tìm ra đoạn đó chỉ với một lượt duyệt không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một dãy liên tiếp kết thúc ngay khi xuất hiện 0, vì vậy tại mỗi chỉ số, bạn chỉ cần độ dài của dãy kết thúc ở đó. Một bộ đếm tăng lên khi gặp 1 và đặt lại về 0 khi gặp 0 sẽ tìm được dãy dài nhất chỉ trong một lượt duyệt.

Đếm tiến từ mọi chỉ số

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Thử từng chỉ số làm điểm bắt đầu và đi tiếp khi bạn còn thấy số 1; số bước đi được là độ dài của đoạn bắt đầu tại đó. Đoạn dài nhất bắt đầu tại một trong các chỉ số này, vì vậy số đếm lớn nhất chính là đáp án.

Các lượt đi bị chồng lấp. Với một mảng gồm n số 1, chúng cần khoảng n² / 2 bước, tức 2 × 10^8 bước khi n = 2 × 10^4.

Thuật toán

Đặt best = 0.
Với mỗi chỉ số start, đặt length = 0.
Khi start + length vẫn nằm trong mảng và nums[start + length] là 1, hãy tăng length thêm 1.
Giữ giá trị lớn hơn giữa best và length.
Trả về 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

Một lượt duyệt với bộ đếm đang chạy

Ý tưởng

Giữ current, độ dài của đoạn gồm các số 1 liên tiếp kết thúc tại chỉ số hiện tại. Số 1 kéo dài đoạn đó thêm một phần tử; số 0 kết thúc đoạn, vì vậy current giảm xuống 0. Mỗi đoạn được đo tại chỉ số cuối cùng, nơi current bằng độ dài đầy đủ của đoạn, nên giá trị lớn nhất mà current đạt được chính là đáp án.

Với [1, 1, 0, 1, 1, 1, 0, 1], current nhận các giá trị 1, 2, 0, 1, 2, 3, 0, 1, và giá trị lớn nhất là 3.

Thuật toán

Đặt best = 0 và current = 0.
Với mỗi giá trị trong nums: nếu giá trị đó là 1, cộng 1 vào current và giữ giá trị lớn hơn giữa best và current.
Nếu giá trị đó là 0, đặt current = 0.
Trả về 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

Lỗi thường gặp và trường hợp biên

Chỉ cập nhật best khi gặp 0. Một lượt chạy đến cuối, như [0, 1, 1], sẽ không bao giờ được ghi nhận. Hãy cập nhật sau mỗi số 1 hoặc so sánh thêm một lần sau vòng lặp.
Không đặt lại current khi gặp 0. Các lượt chạy riêng biệt sẽ cộng dồn, nên [1, 1, 0, 1, 1] trả về 4.
Khởi tạo best bằng 1 hoặc bằng nums[0]. [0, 0, 0] phải trả về 0.
Trong Lua và R, nơi mảng bắt đầu từ 1, hãy giới hạn lượt duyệt tiến bằng < n thay vì ≤ n. Giá trị cuối cùng sẽ không bao giờ được đọc, nên [0, 1] trả về 0.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Max Consecutive Ones là bao nhiêu?

Lời giải duyệt một lượt chạy trong thời gian O(n) vì nó đọc mỗi giá trị một lần và dùng thêm O(1) dung lượng: một biến đếm cho chuỗi liên tiếp hiện tại và một biến cho chuỗi dài nhất. Đếm lại từ đầu tại mỗi chỉ số sẽ mất O(n²) với một mảng toàn số 1.

Tại sao bộ đếm trở về 0 thay vì 1?

Biến đếm lưu độ dài của chuỗi liên tiếp kết thúc tại chỉ số hiện tại. Khi giá trị tại đó là 0, không có chuỗi liên tiếp nào gồm các số 1 kết thúc tại đó, nên độ dài là 0. Số 1 tiếp theo làm tăng giá trị này lên 1, tức là độ dài của chuỗi liên tiếp mới.

Max Consecutive Ones có phải là bài toán cửa sổ trượt không?

Bạn có thể xem nó như một cửa sổ: cửa sổ chứa lần chạy hiện tại, cạnh phải dịch chuyển theo mỗi giá trị, còn 0 khiến cạnh trái vượt qua nó. Cửa sổ không thu hẹp từng bước, vì vậy một bộ đếm có thể thay thế hai cạnh.

def findMaxConsecutiveOnes(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi