使用 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] < n - 1,则

    • 返回答案

    让我们看看以下实现以获得更好的理解 -

    示例

    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

    以上是 使用 Python 查找大小为 M 的最新组的程序 的全部内容, 来源链接: utcz.com/z/317369.html

    回到顶部