Pythonでのk回の演算による繰り返し数を含む最長のサブリストの長さを見つけるプログラム

numsというリストと値kがあるとします。次に、リスト内の任意の数値の値を更新できる操作について考えてみましょう。最大k回の操作を実行した後、繰り返される数を含む最長のサブリストの長さを見つける必要があります。

したがって、入力がnums =[8、6、6、4、3、6、6] k =2の場合、出力は6になります。これは、4と3を6に変更して、この配列を作成できるためです[ 8、6、6、6、6、6、6]、すべて6のサブリストの長さは6です。

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

• numsが空の場合、

  • 0を返す

• num_count：=空のマップ

• max_count：=0

• start：=0

• インデックスの終わりとnumの値numごとに、実行します

  • num_count [num]：=num_count [num] + 1

  • max_count：=max_countとnum_count[num]の最大値

  • end --start + 1> max_count + kの場合、

    • num_count [nums [start]]：=num_count [nums [start]]-1

    • start：=start + 1

• リターンエンド-スタート+1

例

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

from collections import defaultdict
def solve(nums, k):
   if not nums:
      return 0

   num_count = defaultdict(int)
   max_count = 0
   start = 0

   for end, num in enumerate(nums):
      num_count[num] += 1
      max_count = max(max_count, num_count[num])
      if end - start + 1 > max_count + k:
         num_count[nums[start]] -= 1
         start += 1
   return end - start + 1

nums = [8, 6, 6, 4, 3, 6, 6]
k = 2
print(solve(nums, k))

入力

[8, 6, 6, 4, 3, 6, 6], 2

出力

6