Python程序检查有多少查询找到有效的算术序列

假设我们有一个名为nums的数字列表，还有一个查询列表。其中每个查询元素包含[i, j]。因此，此查询询问nums从[i, j]（包含两端）的子列表是否为算术序列。所以最终我们必须找到返回true的查询数量。

因此，如果输入类似于nums = [2, 4, 6, 8, 7, 6, 5, 2] queries = [[3, 4],[0, 3],[2, 4]]，则输出将为2，因为[2, 4, 6, 8]是算术序列，所以查询[0, 3]为真。并且对于[8, 7]也是算术序列，所以查询[3, 4]也为真。但[6, 8, 7]不是算术序列，所以[2, 4]不为真。

为了解决这个问题，我们将遵循以下步骤：

• 如果nums为空，则
  • 返回0
• n := nums的大小
• diff := 一个包含元素(nums[i + 1] - nums[i])的列表，对于范围0到n - 2中的每个i
• rle := 一个大小为(n - 1)并填充0的列表
• 对于范围0到n - 2中的每个i，执行以下操作：
  • 如果i > 0并且diff[i]与diff[i - 1]相同，则
    • rle[i] := rle[i - 1] + 1
  • 否则，
    • rle[i] := 1
• ans := 0
• 对于queries中的每个(i, j)，执行以下操作：
  • 如果i与j相同，则
    • ans := ans + 1
  • 否则，
    • ans := ans + (如果rle[j - 1] >= (j - i)，则为1，否则为0)
• 返回ans

示例

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

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

Arnab Chakraborty

更新于: 2021年10月16日

201 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习