Chương trình tìm độ dài của danh sách con dài nhất chứa các số lặp lại bằng k phép toán trong Python

Giả sử chúng ta có một danh sách gọi là nums và một giá trị k, bây giờ chúng ta hãy xem xét một phép toán mà chúng ta có thể cập nhật giá trị của bất kỳ số nào trong danh sách. Chúng ta phải tìm độ dài của danh sách con dài nhất chứa các số lặp lại sau khi thực hiện nhiều nhất k phép toán.

Vì vậy, nếu đầu vào giống như nums =[8, 6, 6, 4, 3, 6, 6] k =2, thì đầu ra sẽ là 6, vì chúng ta có thể thay đổi 4 và 3 thành 6, để tạo mảng này [ 8, 6, 6, 6, 6, 6, 6] và độ dài của danh sách phụ với tất cả 6 giây là 6.

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

• nếu nums trống, thì

  • trả về 0

• num_count:=một bản đồ trống

• max_count:=0

• bắt đầu:=0

• đối với mỗi kết thúc chỉ mục và giá trị num tính bằng nums, thực hiện

  • num_count [num]:=num_count [num] + 1

  • max_count:=tối đa max_count và num_count [num]

  • nếu end - start + 1> max_count + k, thì

    • num_count [nums [start]]:=num_count [nums [start]] - 1

    • start:=start + 1

• return end - start + 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 defaultdict
def solve(nums, k):
   if not nums:
      return 0

   num_count = defaultdict(int)
   max_count = 0
   start = 0

   for end, num in enumerate(nums):
      num_count[num] += 1
      max_count = max(max_count, num_count[num])
      if end - start + 1 > max_count + k:
         num_count[nums[start]] -= 1
         start += 1
   return end - start + 1

nums = [8, 6, 6, 4, 3, 6, 6]
k = 2
print(solve(nums, k))

Đầu vào

[8, 6, 6, 4, 3, 6, 6], 2

Đầu ra

6