Giả sử chúng ta có một danh sách các số được gọi là nums và được sắp xếp theo thứ tự không giảm, chúng ta phải kiểm tra xem nó có thể được chia thành bất kỳ số lượng dãy con nào sao cho mỗi dãy con có độ dài tối thiểu là 3 và tăng liên tục hay không.
Vì vậy, nếu đầu vào giống như nums =[2, 3, 4, 4, 5, 6, 7], thì đầu ra sẽ là True, vì chúng ta có thể chia danh sách thành [2, 3, 4] và [4, 5, 6, 7].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- counts:=Một bản đồ chứa các phần tử của num và số lượng của nó
- started:=một danh sách mới
- kết thúc:=một danh sách mới
- đối với mỗi x trong các mục của số lượng theo thứ tự đã sắp xếp, hãy thực hiện
- nếu count [x]> count [x - 1], thì
- l:=danh sách kích thước (đếm [x] - đếm [x - 1]) và điền bằng x
- chèn l vào phần bắt đầu
- nếu count [x]> count [x + 1], thì
- l:=danh sách kích thước (đếm [x] - đếm [x + 1]) và điền bằng x
- chèn l vào phần bắt đầu
- nếu count [x]> count [x - 1], thì
- trả về true khi tất cả cặp (start, end) thỏa mãn (start + 2 <=end), nếu không thì trả về false
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from collections import Counter class Solution: def solve(self, nums): count = Counter(nums) starts = [] ends = [] for x in sorted(count): if count[x] > count[x - 1]: starts.extend([x] * (count[x] - count[x - 1])) if count[x] > count[x + 1]: ends.extend([x] * (count[x] - count[x + 1])) 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))
Đầu vào
[6, 7, 5, 10, 13], 2
Đầu ra
True