嗨，我正在嘗試解決 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]（它回傳 2 而不是 3）。在我的腦海中，我知道它不起作用，因為當呼叫該函式時，1 slices([1,2,3], 2)回傳 2。如何修復我的代碼以獲取來自整個陣列的算術切片[1,2,3,4]？
uj5u.com熱心網友回復：
為了解決這個問題，你必須采取兩個步驟。
首先你必須找到所有可能的連續子陣列
你必須檢查它們，如果它們是算術切片。
一個不節省記憶體和時間的可理解解決方案如下：
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/449671.html
上一篇：MariaDB中的遞回父子問題