Chương trình kiểm tra có thể tách danh sách thành các dãy con tăng liên tiếp độ dài ≥3 không trong Python

Cho danh sách số nums đã sắp xếp không giảm. Kiểm tra xem có thể chia thành các dãy con (subsequence) sao cho mỗi dãy có độ dài ≥ 3 và các phần tử tăng liên tiếp (ví dụ: 2,3,4).

Ví dụ: nums = [2, 3, 4, 4, 5, 6, 7] → tách thành [2,3,4] và [4,5,6,7] → True.

Giải thuật (Đếm tần suất & xác định đoạn)

• Đếm tần suất mỗi số trong counts.
• Xác định các đoạn bắt đầu (starts) và kết thúc (ends) của các dãy con tiềm năng:
  • Nếu count[x] > count[x-1]: có count[x] - count[x-1] dãy mới bắt đầu tại x.
  • Nếu count[x] > count[x+1]: có count[x] - count[x+1] dãy kết thúc tại x.
• Ghép cặp (start, end) theo thứ tự, kiểm tra start + 2 <= end (độ dài ≥ 3).

Mã nguồn Python

from collections import Counter

class Solution:
    def solve(self, nums):
        count = Counter(nums)
        starts = []
        ends = []
        for x in sorted(count):
            if count[x] > count.get(x-1, 0):
                starts.extend([x] * (count[x] - count.get(x-1, 0)))
            if count[x] > count.get(x+1, 0):
                ends.extend([x] * (count[x] - count.get(x+1, 0)))
        return all(s + 2 <= e for s, e in zip(starts, ends))

ob = Solution()
nums = [2, 3, 4, 4, 5, 6, 7]
print(ob.solve(nums))  # Output: True

Đầu vào

[2, 3, 4, 4, 5, 6, 7]

Đầu ra

True