Pythonを使用してサイズMの最新のグループを見つけるプログラム

1からnまでの数の順列を保持している配列arrがあるとします。サイズnのバイナリ文字列があり、最初はそのすべてのビットがゼロに設定されている場合。ここで、1からnまでの各ステップi（バイナリ文字列とarrの両方でインデックス作成は1から始まります）で、位置arr [i]のビットは1に設定されます。別の値mもあり、最新のものを見つける必要があります。サイズmのもののグループが存在するステップ。ここで、1のグループとは、どちらの方向にも拡張できないような1の連続したサブストリングを意味します。正確にmの長さのグループが存在する最新のステップを見つける必要があります。そのようなグループが見つからない場合は、-1を返します。

したがって、入力がarr =[3,5,1,2,4] m =3の場合、最初のバイナリ文字列は「00000」であるため、出力は4になります。次の手順-

• "00100"、グループ：["1"]

• "00101"、グループ：["1"、 "1"]

• "10101"、グループ：["1"、 "1"、 "1"]

• "11101"、グループ：["111"、 "1"]

• "11111"、グループ：["11111"]

ここで、サイズ3のグループが存在する最新のステップはステップ4です。

これを解決するには、次の手順に従います-

• n：=arrのサイズ

• num：=0

• ans：=-1

• l：=サイズnの配列、0で埋める

• r：=サイズnの配列で、0で埋めます

• 0からn-1の範囲のiの場合、実行

  • cur：=1

  • idx：=arr [i]-1

  • r [idx]がmと同じ場合、

    • num：=num-1

  • l [idx]がmと同じ場合、

    • num：=num-1

  • cur：=cur + l [idx] + r [idx]

  • num：=num+curはmと同じです

  • num> 0の場合、

    • ans：=ansの最大値、i + 1

  • idx --l [idx]> 0の場合、

    • r [idx --l [idx] -1]：=cur

  • idx + r [idx]

    • l [idx + r [idx] + 1]：=cur

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

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