Chương trình kiểm tra xem có bao nhiêu truy vấn tìm thấy chuỗi số học hợp lệ trong Python

Giả sử chúng ta có một danh sách các số được gọi là num và cũng có danh sách các truy vấn. Trong đó mỗi phần tử truy vấn chứa [i, j]. Vì vậy, truy vấn này hỏi liệu danh sách con của các num từ [i, j] (cả hai đều bao gồm), có phải là một chuỗi số học hay không. Vì vậy, cuối cùng chúng ta phải tìm số lượng truy vấn trả về true.

Vì vậy, nếu đầu vào giống như nums =[2, 4, 6, 8, 7, 6, 5, 2] queries =[[3, 4], [0, 3], [2, 4]], thì đầu ra sẽ là 2, bởi vì [2, 4, 6, 8] là một dãy số học, vì vậy truy vấn [0, 3] là true. và đối với [8, 7] cũng là một dãy số học, vì vậy truy vấn [3, 4] cũng đúng. nhưng [6, 8, 7] không phải là một dãy số học, vì vậy [2, 4] không đúng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu nums trống, thì
  • trả về 0
• n:=kích thước của nums
• diff:=danh sách có các phần tử (nums [i + 1] - nums [i]) cho mỗi i trong phạm vi từ 0 đến n - 2
• rle:=một danh sách có kích thước (n - 1) và điền bằng 0
• đối với tôi trong phạm vi từ 0 đến n - 2, thực hiện
  • nếu i> 0 và diff [i] giống với diff [i - 1] thì
    • rle [i]:=rle [i - 1] + 1
  • nếu không,
    • rle [i]:=1
• ans:=0
• đối với mỗi (i, j) trong các truy vấn, hãy thực hiện
  • nếu tôi giống với j, thì
    • ans:=ans + 1
  • nếu không,
    • ans:=ans + (1 nếu rle [j - 1]> =(j - i), nếu không thì 0)
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

2