Python程式：查詢子串長度，其中子串中零的個數的兩倍小於或等於子串中一的個數的三倍

假設我們給定一個字串和一個整數k。該字串重複k次構成另一個字串。我們的任務是找到新字串中子串的長度，其中子串中零的個數的兩倍小於或等於子串中一的個數的三倍。

因此，如果輸入為k = 2，input_str = '0101011'，則輸出為14。

該字串長度為7。因此，由第一個字串構成的新的字串為01010110101011。這裡零的個數為6，一的個數為8。所以，2 * 6 <= 3 * 8。因此，最長的子串是整個長度為14的字串。

為了解決這個問題，我們將遵循以下步驟：

  • str_len := input_str的長度
  • list_a := 一個大小為(str_len + 1)的新列表，初始化為0
  • list_b := 一個大小為(str_len + 1)的新列表，初始化為0
  • list_b[0] := 一個包含(0, 0)的新元組
  • 對於範圍0到str_len中的i，執行：
    • list_a[i + 1] := list_a[i] - 3 *(如果input_str[i]等於'1'則為1，否則為0) + 2 *(如果input_str[i]等於'0'則為1，否則為0)
    • list_b[i + 1] := 一個包含(list_a[i + 1], i + 1)的新元組
  • 對列表list_b進行排序
  • temp_list := 一個大小為(str_len + 1)的新列表，初始化為0
  • temp_list[0] := list_b[0, 1]
  • 對於範圍0到str_len中的i，執行：
    • temp_list[i + 1] = max(temp_list[i], list_b[i + 1, 1])
  • res := 0
  • 對於範圍0到str_len中的i，執行：
    • tmp := list_b[0, 0] - list_a[i]
    • 如果list_a[str_len] <= 0，則
      • a := k - 1
      • 如果tmp + list_a[str_len] * a > 0，則
        • 進行下一次迭代
    • 否則，如果tmp > 0，則
      • 進行下一次迭代
    • 否則，
      • a := min(k - 1, floor(-tmp / list_a[str_len]))
    • v := a * list_a[str_len] - list_a[i]
    • b := (在list_b中插入元組(-v + 1, 0)並保持排序順序的位置) - 1
    • res := max(res, temp_list[b] - i + a * str_len)
  • 返回res

示例

讓我們看看下面的實現以更好地理解：

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'))

輸入

2, '0101011'

輸出

14

更新於：2021年10月20日

167 次檢視

啟動您的職業生涯

完成課程獲得認證

開始
廣告