Chuỗi dài nhất

Thuộc phần Logic và luồng thực thi trong hành trình Swift của Coddy. Bài học 35 trên 56.

streak là số ngày liên tiếp một thói quen được đánh dấu là đã hoàn thành. Với các ngày [1, 2, 3, 5, 6], streak dài nhất là 3 (ngày 1 đến 3).

Khi đã có danh sách ngày được sắp xếp, bạn chỉ cần duyệt tuyến tính một lần: so sánh từng ngày với ngày trước đó, kéo dài lượt liên tiếp hiện tại nếu chúng nối tiếp nhau, nếu không thì đặt lại.

func longestStreak(_ days: [Int]) -> Int {
    let sorted = days.sorted()
    var best = 0
    var run = 0
    var prev: Int? = nil
    for d in sorted {
        if let p = prev, d == p + 1 {
            run += 1
        } else {
            run = 1
        }
        if run > best { best = run }
        prev = d
    }
    return best
}

Mẫu “theo dõi lần chạy hiện tại và kết quả tốt nhất từ trước đến nay” xuất hiện trong nhiều bài toán. Chỉ cần nhận ra mẫu này một lần, bạn sẽ nhớ mãi.

Thử thách

Trung bình

Đọc một dòng đầu vào: danh sách các mục habit:day phân tách bằng dấu phẩy. Tạo từ điển như bạn đã làm trong bài học trước, sau đó tính streak dài nhất gồm các ngày liên tiếp trong tuần cho mỗi thói quen.

In các thói quen theo thứ tự bảng chữ cái, mỗi thói quen trên một dòng, theo định dạng:

<habit>: streak=<n>

Với đầu vào read:1,read:2,read:3,read:5,workout:2,workout:4, đầu ra là:

read: streak=3
workout: streak=1

Tự làm thử

var habits: [String: [Int]] = [:]
let ops = readLine()!.components(separatedBy: ",")
for op in ops {
    let parts = op.components(separatedBy: ":")
    let day = Int(parts[1])!
    if !(habits[parts[0], default: []].contains(day)) {
        habits[parts[0], default: []].append(day)
    }
}

// TODO: tìm streak dài nhất cho từng thói quen, in ra theo thứ tự tên với định dạng 'name: streak=n'