Chương trình tìm nhóm kích thước M mới nhất bằng Python

Giả sử chúng ta có một mảng arr, mảng này chứa một hoán vị của các số từ 1 đến n. Nếu chúng ta có một chuỗi nhị phân kích thước n và ban đầu tất cả các bit của nó được đặt bằng không. Bây giờ ở mỗi bước i (Lập chỉ mục bắt đầu từ 1 cho cả chuỗi nhị phân và arr) từ 1 đến n, bit ở vị trí arr [i] được đặt thành 1. Chúng ta cũng có một giá trị m khác và chúng ta cần tìm giá trị mới nhất bước mà tại đó tồn tại một nhóm có kích thước m. Ở đây, một nhóm có nghĩa là một chuỗi con liền kề của 1s sao cho nó không thể được mở rộng theo một trong hai hướng. Chúng ta phải tìm bước mới nhất mà tại đó tồn tại một nhóm có độ dài chính xác là m. Nếu chúng tôi không thể tìm thấy bất kỳ nhóm nào như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào là arr =[3,5,1,2,4] m =3, thì đầu ra sẽ là 4 vì, chuỗi nhị phân ban đầu là "00000", sau đó làm theo các bước -

• "00100", nhóm:["1"]

• "00101", nhóm:["1", "1"]

• "10101", nhóm:["1", "1", "1"]

• "11101", nhóm:["111", "1"]

• "11111", nhóm:["11111"]

Đây là bước mới nhất mà tại đó tồn tại một nhóm có kích thước 3 là bước 4.

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

• n:=kích thước của arr

• num:=0

• ans:=-1

• l:=một mảng có kích thước n và điền bằng 0

• r:=một mảng có kích thước n và điền bằng 0

• đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện

  • cur:=1

  • idx:=arr [i] - 1

  • nếu r [idx] giống với m thì

    • num:=num - 1

  • nếu l [idx] giống với m thì

    • num:=num - 1

  • cur:=cur + l [idx] + r [idx]

  • num:=num + cur giống với m

  • nếu num> 0, thì

    • ans:=tối đa ans, i + 1

  • nếu idx - l [idx]> 0, thì

    • r [idx - l [idx] - 1]:=cur

  • nếu idx + r [idx]

    • l [idx + r [idx] + 1]:=cur

• trả lại ans

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

Ví dụ

def solve(arr, m):
   n = len(arr)
   num = 0
   ans = -1
   l = [0] * n
   r = [0] * n
   for i in range(n):
      cur = 1
      idx = arr[i] - 1
      if r[idx] == m:
         num -= 1
      if l[idx] == m:
         num -= 1
      cur += l[idx] + r[idx]
      num += cur == m
      if num > 0:
         ans = max(ans, i + 1)
      if idx - l[idx] > 0:
         r[idx - l[idx] - 1] = cur
      if idx + r[idx] < n - 1:
         l[idx + r[idx] + 1] = cur
   return ans
arr = [3,5,1,2,4]
m = 3
print(solve(arr, m))

Đầu vào

[3,5,1,2,4], 3

Đầu ra

4