使用 Python 查找大小为 M 的最新组的程序
假设我们有一个数组arr,它保存了从1到n的数字排列。如果我们有一个大小为n的二进制字符串,并且最初它的所有位都设置为零。现在在从1到n的每一步i(二进制字符串和arr的索引都从1开始),位置arr[i]处的位被设置为1。我们还有另一个值m,我们需要找到最新的存在一组大小为m的步骤。这里的一组1表示一个连续的1子串,这样它就不能在任一方向上扩展。我们必须找到存在一组长度正好为m的组的最新一步。如果我们找不到任何这样的组,则返回-1。
因此,如果输入类似于arr=[3,5,1,2,4]m=3,则输出将为4,因为初始二进制字符串为“00000”,然后执行以下步骤-
“00100”,组:[“1”]
“00101”,组:[“1”,“1”]
“10101”,组:[“1”,“1”,“1”]
“11101”,组:[“111”,“1”]
“11111”,组:[“11111”]
这里存在一组大小为3的组的最新步骤是步骤4。
为了解决这个问题,我们将按照以下步骤操作-
n:=arr的大小
数量:=0
答案:=-1
l:=大小为n的数组,并用0填充
r:=大小为n的数组,并用0填充
对于0到n-1范围内的i,请执行
l[idx+r[idx]+1]:=当前
r[idx-l[idx]-1]:=cur
ans:=ans的最大值,i+1
数量:=数量-1
数量:=数量-1
当前:=1
idx:=arr[i]-1
如果r[idx]与m相同,则
如果l[idx]与m相同,则
cur:=cur+l[idx]+r[idx]
num:=num+cur与m相同
如果num>0,则
如果idx-l[idx]>0,则
如果idx+r[idx]
返回答案
让我们看看以下实现以获得更好的理解-
示例
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))
输入
[3,5,1,2,4], 3输出结果
4