413. Arithmetic Slices
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Author: Huahua # Time complexity: O(n) # Space complexity: O(n) class Solution: def numberOfArithmeticSlices(self, nums: List[int]) -> int: @cache def dp(i: int) -> int: """Number of arithmetic subarrays end with nums[i].""" if i < 2: return 0 if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]: return 1 + dp(i - 1) return 0 return sum(dp(i) for i in range(len(nums))) |
91. Decode Ways
Python3
1 2 3 4 5 6 7 8 9 10 11 12 |
# Author: Huahua # Time complexity: O(n^2) -> O(n) # Space complexity: O(n) class Solution: @cache def numDecodings(self, s: str) -> int: if not s: return 1 if s[0] == '0': return 0 ans = self.numDecodings(s[1:]) if len(s) > 1 and (s[0] == '1' or (s[0] == '2' and s[1] <= '6')): ans += self.numDecodings(s[2:]) return ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment