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 次查看

启动您的职业生涯

完成课程获得认证

开始
广告