Leetcode 413：算术切片 Python

Question

嗨，我正在尝试解决 Leetcode 413：算术切片。我正在尝试从强力递归解决方案开始。

 def numberOfArithmeticSlices(self, nums: List[int]) -> int:
      def slices(nums: List[int], i: int):
          if (i < 2):
              return 0
          if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
              return 1 + slices(nums, i -1)
          else:
              return slices(nums, i-1)
        if len(nums) < 3:
            return 0
        return slices(nums, len(nums)-1)

这不适用于测试用例 [1,2,3,4]（它 returns 2 而不是 3）。在我看来，我知道它不起作用，因为当函数被调用时，1 + slices([1,2,3], 2) returns 2. 如何修复我的代码以获取来自整个数组的算术切片 [1,2,3,4] ？

Answer 1

为了解决这个问题，你必须采取两个步骤。

首先你必须找到所有可能的连续sub-arrays
你必须检查它们，如果它们是算术切片。

内存和时间效率不高的可理解解决方案如下：

def numberOfArithmeticSlices(self, nums: List[int]) -> int:
    if len(nums) <= 2:
        return 0
    sub_arrays = self.contiguous_subarray(nums)  # type List[List[int]]  all contiguous sub arrays with length 3 or more
    count = 0
    for subset in sub_arrays:
        count = count + self.is_arithmetic_subset(subset)
    return count

@staticmethod
def is_arithmetic_subset(subset):
    if len(subset) <= 2:
        return 0
    diff = subset[1] - subset[0]
    for i in range(2, len(subset)):
        if subset[i] - subset[i - 1] != diff:
            return 0
    return 1

@staticmethod
def contiguous_subarray(nums):
    return [nums[i:i + j] for i in range(0, len(nums)) for j in range(3, len(nums) - i + 1)]

但是下面是一个更难掌握但内存和时间效率更高的解决方案（您仍然可以用循环替换递归调用，我认为这样做会得到更好的结果）：

def numberOfArithmeticSlices(self, nums: List[int]) -> int:
    array_len = len(nums)
    if array_len <= 2:
        return 0
    count = self.numberOfArithmeticSlices(nums[:array_len - 1])
    diff = nums[array_len - 1] - nums[array_len - 2]
    for i in range(2, array_len):
        if nums[array_len - i ] - nums[array_len - i - 1] == diff:
            count += 1
        else:
            break
    return count

Leetcode 413：算术切片 Python

Leetcode 413: Arithmetic slices Python

python

recursion

dynamic-programming