在Python中查找子串的长度,其中子串中的0的数量是其1的数量的三倍,并且小于或等于两倍的计算机领域英语文章
假设给定一个字符串和一个整数k。该字符串重复k次并重新生成另一个字符串。我们的任务是找到新字符串中子字符串的长度,其中 2 *(子字符串中零的数量)<= 3 *(子字符串中1的数量)。
因此,如果输入为k = 2,input_str =’0101011’,则输出将为 14。
该字符串的长度为7。因此,从第一个字符串制作的新字符串为 01010110101011。这里的0的数量为6,1的数量为8。因此,2 * 6 <= 3 * 8。因此,最大子字符串是整个长度为14的字符串。
要解决此问题,请执行以下步骤−
- str_len:=输入字符串大小
- list_a:=大小为(str_len + 1)的新列表,初始化为0
- list_b:=大小为(str_len + 1)的新列表,初始化为0
- list_b [0]:=包含(0,0)的新对
- for i in range 0 to str_len, do
- list_a[i+1]:=-3*(如果input_str [i]与’1’相同,则为1,否则为0)+ 2 *(如果input_str [i]与’0’相同,则为1,否则为0)+ list_a[i]
- list_b[i + 1] := 包含(list_a [i + 1],i + 1)的新对
- 对列表list_b进行排序
- templist :=大小为(str_len + 1)的新列表,初始化为0
- templist[0]: = list_b [0,1]
- for i in range 0 to str_len, do
- temp_list[i + 1] =(temp_list[i],list_b [i + 1,1])的最大值
- res:= 0
- for i in range 0 to str_len, do
- 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:= k-1和((-tmp / list_a[str_len])的floor值)的最小值
- v:=a * list_a[str_len] – list_a[i]
- b:=(可以插入新对(- v + 1,0)保持排序顺序的列表list_b中的位置)-1
- res: =最大值(res,temp_list[b] – i + a * str_len)
- 返回res
例子
让我们看一下以下实现,以获得更好的理解−