Chương trình để tìm ra độ dài của chuỗi con trong đó hai lần số lượng các số 0 trong chuỗi con nhỏ hơn hoặc bằng ba lần số lượng các số một trong chuỗi con trong Python

Giả sử chúng ta được cung cấp một chuỗi và một số nguyên k. Chuỗi được lặp lại k lần và được tạo thành chuỗi khác. Nhiệm vụ của chúng ta là tìm độ dài của chuỗi con trong chuỗi mới trong đó 2 * (số lượng các số 0 trong chuỗi con) <=3 * (số lượng các số 0 trong chuỗi con).

Vì vậy, nếu đầu vào là k =2, input_str ='0101011', thì đầu ra sẽ là 14.

Chuỗi có độ dài 7. Vì vậy, chuỗi mới được tạo ra từ chuỗi đầu tiên là 01010110101011. Ở đây số 0 là 6 và số 1 là 8. Vì vậy, 2 * 6 <=3 * 8. do đó, chuỗi con lớn nhất là toàn bộ chuỗi có độ dài 14.

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

• str_len:=kích thước của input_str
• list_a:=một danh sách mới có kích thước (str_len + 1) được khởi tạo bằng 0s
• list_b:=một danh sách mới có kích thước (str_len + 1) được khởi tạo bằng 0s
• list_b [0]:=một cặp mới chứa (0, 0)
• đối với tôi trong phạm vi 0 đến str_len, thực hiện
  • list_a [i + 1]:=list_a [i] - 3 * (1 nếu input_str [i] giống với '1', khác 0) + 2 * (1 nếu input_str [i] giống với '0 ', khác 0)
  • list_b [i + 1]:=một cặp mới bao gồm (list_a [i + 1], i + 1)
• sắp xếp danh sách list_b
• temp_list:=một danh sách mới có kích thước (str_len + 1) được khởi tạo bằng 0s
• temp_list [0]:=list_b [0, 1]
• đối với tôi trong phạm vi 0 đến str_len, thực hiện
  • temp_list [i + 1] =tối đa trong tổng số (temp_list [i], list_b [i + 1, 1])
• res:=0
• đối với tôi trong phạm vi 0 đến str_len, thực hiện
  • tmp:=list_b [0, 0] - list_a [i]
  • nếu list_a [str_len] <=0, thì
    • a:=k - 1
    • nếu tmp + list_a [str_len] * a> 0, thì
      • chuyển sang lần lặp tiếp theo
  • ngược lại khi tmp> 0, thì
    • chuyển sang lần lặp tiếp theo
  • nếu không,
    • a:=tối thiểu là (k - 1, giá trị sàn của (-tmp / list_a [str_len]))
  • v:=a * list_a [str_len] - list_a [i]
  • b:=(vị trí trong list_b nơi có thể chèn cặp (-v + 1, 0) để duy trì thứ tự đã sắp xếp) - 1
  • res:=tối đa trong tổng số (res, temp_list [b] - i + a * str_len)
• trả lại res

Ví dụ

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

from bisect import bisect_left
def solve(k, input_str):
   str_len = len(input_str)
   list_a = [0] * (str_len + 1)
   list_b = [0] * (str_len + 1)
   list_b[0] = (0, 0)
   for i in range(str_len):
      list_a[i + 1] = list_a[i] - 3 * (input_str[i] == '1') + 2 * (input_str[i] == '0')
      list_b[i + 1] = (list_a[i + 1], i + 1)

   list_b.sort()
   temp_list = [0] * (str_len + 1)
   temp_list[0] = list_b[0][1]
   for i in range(str_len):
      temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1])
   res = 0
   for i in range(str_len):
      tmp = list_b[0][0] - list_a[i]
      if list_a[str_len] <= 0:
         a = k - 1
         if tmp + list_a[str_len] * a > 0:
            continue
      elif tmp > 0:
         continue
      else:
         a = min(k - 1, -tmp // list_a[str_len])

      v = a * list_a[str_len] - list_a[i]
      b = bisect_left(list_b, (-v + 1, 0)) - 1
      res = max(res, temp_list[b] - i + a * str_len)
   return res

print(solve(2, '0101011'))

Đầu vào

2, '0101011'

Đầu ra

14