Chương trình kiểm tra mọi danh sách con trong danh sách có chứa ít nhất một phần tử duy nhất trong Python

Giả sử chúng ta có một danh sách các phần tử được gọi là nums, chúng ta phải kiểm tra xem mọi danh sách con có ít nhất 1 phần tử xuất hiện đúng một lần trong danh sách con hay không. Chúng ta phải giải quyết vấn đề này trong thời gian tuyến tính.

Vì vậy, nếu đầu vào giống như nums =[5, 10, 20, 10, 0], thì đầu ra sẽ là True, vì mọi danh sách con trong nums đều có ít nhất một phần tử chỉ xuất hiện một lần. [[5], [10], [20], [10], [0], [5,10], [10,20], [20,10], [10,0], [5,10, 20], [10,20,10], [20,10,0], [5,10,20,10], [10,20,10,0], [5,10,20,10,0] ] tất cả đều có ít nhất một phần tử có tần số là 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm has_unique (). Thao tác này sẽ sang trái, sang phải
• if left> =right, then
  • trả về True
• counts:=một từ điển chứa tần số của từng phần tử có trong nums [từ chỉ mục từ trái sang phải]
• nếu tần suất tối thiểu từ số lượng> 1, thì
  • trả về Sai
• start:=left
• đối với chỉ mục trong phạm vi từ trái sang phải, thực hiện
  • nếu số lượng [nums [index]] bằng 1, thì
    • nếu has_unique (start, index - 1) là false, thì
      • trả về Sai
    • start:=index + 1
• return has_unique (bắt đầu, bên phải)
• Từ phương thức chính, trả về has_unique (0, kích thước của nums - 1)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

from collections import Counter
def solve(nums):
   def has_unique(left, right):
      if left >= right:
         return True

      counts = Counter(nums[left : right + 1])
      if min(counts.values()) > 1:
         return False

      start = left

      for index in range(left, right + 1):
         if counts[nums[index]] == 1:
            if not has_unique(start, index - 1):
               return False
            start = index + 1

      return has_unique(start, right)

   return has_unique(0, len(nums) - 1)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

Đầu vào

[5, 10, 20, 10, 0]

Đầu ra

True