Pythonで有効な等差数列を見つけるクエリの数をチェックするプログラム

numsという番号のリストがあり、クエリのリストもあるとします。各クエリ要素に[i、j]が含まれている場合。したがって、このクエリは、[i、j]（両方を含む）からのnumsのサブリストが等差数列であるかどうかを尋ねています。したがって、最後に、trueを返すクエリの数を見つける必要があります。

したがって、入力がnums =[2、4、6、8、7、6、5、2]クエリ=[[3、4]、[0、3]、[2、4]]のようである場合、 [2、4、6、8]は等差数列であるため、出力は2になります。したがって、クエリ[0、3]はtrueです。 [8、7]も等差数列であるため、クエリ[3、4]も真です。ただし、[6、8、7]は等差数列ではないため、[2、4]は正しくありません。

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

• numsが空の場合、
  • 0を返す
• n：=numsのサイズ
• diff：=0からn-2の範囲の各iの要素（nums [i + 1]-nums [i]）のリスト
• rle：=サイズのリスト（n-1）および0で埋める
• 0からn-2の範囲のiの場合、do
  • i>0でdiff[i]がdiff[i-1]と同じである場合、
    • rle [i]：=rle [i-1] + 1
  • それ以外の場合、
    • rle [i]：=1
• ans：=0
• クエリの（i、j）ごとに、
  • iがjと同じ場合、
    • ans：=ans + 1
  • それ以外の場合、
    • ans：=ans +（rle [j --1]> =（j --i）の場合は1、それ以外の場合は0）
• 回答を返す

例

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

def solve(nums, queries):
   if not nums:
      return 0

   n = len(nums)
   diff = [nums[i + 1] - nums[i] for i in range(n - 1)]

   rle = [0] * (n - 1)
   for i in range(n - 1):
      if i > 0 and diff[i] == diff[i - 1]:
         rle[i] = rle[i - 1] + 1
      else:
         rle[i] = 1

   ans = 0
   for i, j in queries:
      if i == j:
         ans += 1
      else:
         ans += rle[j - 1] >= (j - i)
   return ans

nums = [2, 4, 6, 8, 7, 6, 5, 2]
queries = [[3, 4],[0, 3],[2, 4]]
print(solve(nums, queries))

入力

[2, 4, 6, 8, 7, 6, 5, 2], [[3, 4],[0, 3],[2, 4]]

出力

2