目录:
一、递归:
1,leetcode-70
2,leetcode-17
3,leetcode-46
二、动态规划:
1,leetcode-131
2,leetcode-132
3,leetcode-198
一、递归:
1,leetcode-70. Climbing Stairs:
https://leetcode.com/problems/climbing-stairs/
# leetcode-70:
''' 斐波那契数列问题:一共n阶台阶,倒数第一步时,无视前面怎么走,有两种走法:
1.走一步
2.走两步
两种走法的走法种数相加就是n阶台阶的情况下的所有种数,即:f(n)=f(n-1)+f(n-2)'''
class Solution: # 战胜78.16%
def climbStairs(self, n: int) -> int:
count = [1, 2]
for i in range(2, n):
count.append(count[i-1] + count[i-2])
return count[n-1]
class Solution: # 战胜78.16%
def climbStairs(self, n: int) -> int:
count = [1, 1]
for i in range(2, n+1): # 与上面解法一致,区别仅在于列表index不同
count.append(count[i-1] + count[i-2])
return count[n]
# 递归解法:不出意料超时了
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
2,leetcode-17. Letter Combinations of a Phone Number:
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
# leetcode-17: 递归
# 列表形式: O(3^n)的时间复杂度,n=len(digits)
class Solution: # 战胜了81.75%
def letterCombinations(self, digits: str) -> list:
l = len(digits)
letters = [' ', '*', 'abc', 'def', 'ghi','jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
if l == 1: # 当递归到digits只有一个数字时,这是一个递归的终结者
return list(letters[int(digits)])
elif l == 0:
return []
res = []
for i in list(letters[int(digits[0])]):
# for j in self.letterCombinations(digits[1:]):
# res.append(i + j)
res.extend([i+j for j in self.letterCombinations(digits[1:])])
return res
class Solution: # 字典形式:算法与上面一致,战胜了81.75%
def letterCombinations(self, digits: str) -> List[str]:
num_str = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
if len(digits) == 0:
return []
if len(digits) == 1: # 当递归到digits只有一个数字时,这是一个递归的终结者
return list(num_str[digits[0]])
res = []
res_after = self.letterCombinations(digits[1:])
for i in num_str[digits[0]]:
res.extend([i+j for j in res_after])
return res
# 非递归形式:时间复杂度与递归形式一样,战胜了81.75%
class Solution:
def letterCombinations(self, digits: str) -> list:
if not digits:
return []
num_str = {"2":"abc","3":"def","4":"ghi","5":"jkl",
"6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
res = [i for i in num_str[digits[0]]]
for i in digits[1:]:
res = [m+n for m in res for n in num_str[i]]
return res
3,leetcode-46. Permutations:
https://leetcode.com/problems/permutations/
# leetcode-46:
# 递归(回溯法):战胜了72.70%
class Solution:
def __init__(self):
self.res = [] # 定义类中的全局变量res,
def permute(self, nums: List[int]) -> List[List[int]]:
self.permutation_recursion([], nums)
return self.res
def permutation_recursion(self, result, nums): # 真正的功能实现函数,在此函数中定义res不容易在外部调用
if (len(nums)==0):
self.res.append(result)
for i in range(len(nums)):
self.permutation_recursion(result+[nums[i]], nums[0:i]+nums[i+1:]) # nums[0:i]+nums[i+1:] = nums - nums[i]
# 非递归方式:战胜了92.28%
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
perms = [[]]
for n in nums:
new_perms = []
for perm in perms:
for i in range(len(perm)+1):
new_perms.append(perm[:i] + [n] + perm[i:]) # insert n
perms = new_perms
return perms
二、动态规划:
1,leetcode-131. Palindrome Partitioning:
https://leetcode.com/problems/palindrome-partitioning/
# leetcode-131:
# 递归(回溯法): 战胜了55.15%
class Solution(object):
def partition(self, s):
self.isPalindrome = lambda s : s == s[::-1]
res = []
self.helper(s, res, [])
return res
def helper(self, s, res, path):
if not s:
res.append(path)
return
for i in range(1, len(s) + 1):
if self.isPalindrome(s[:i]):
self.helper(s[i:], res, path + [s[:i]])
# 递归:战胜了26.86%
def partition(self, s: str) -> List[List[str]]:
if len(s)==1:return [[s]]
array=[]
for i in range(1,len(s)+1):
s_sub,item = s[0:i],[]
if s_sub == s_sub[::-1]:
item.append(s_sub)
if s_sub != s:
item2 = self.partition(s[i:len(s)+1])
if len(item2):
for j in item2:
if len(''.join(item + j)) == len(s):
array.append(item + j)
else:
array.append(item)
return array
2,leetcode-132. Palindrome Partitioning II:
https://leetcode.com/problems/palindrome-partitioning-ii/
# leetcode-132:
# 动态规划:战胜了81.88%
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
dp = [i - 1 for i in range(0, n + 1)] # dp[i]: the minimum cuts needed for s[:i]
for i in range(0, n + 1):
j = 0
while i - j >= 0 and i + j < n and s[i + j] == s[i - j]:
dp[i + j + 1] = min(dp[i + j + 1], dp[i - j] + 1)
j += 1
j = 1
while i - j + 1 >= 0 and i + j < n and s[i - j + 1] == s[i + j]:
dp[i + j + 1] = min(dp[i + j + 1], dp[i - j + 1] + 1)
j += 1
return dp[n]
# 战胜了43.38%
class Solution(object):
def minCut(self, s):
size = len(s)
ans = [i for i in range(size)]
p = [[False for i in range(size)] for j in range(size)]
j = 1
while j < size:
i,ans[j] = j - 1,min(ans[j],ans[j - 1] + 1)
p[j][j] = True
while i >= 0:
if s[i] == s[j] and ((j - i) < 2 or p[i+1][j-1]):
p[i][j] = True
if i == 0:
ans[j] = 0
else:
ans[j] = min(ans[j],ans[i - 1] + 1)
i -= 1
j += 1
return ans[size - 1]
3,leetcode-198. House Robber:
https://leetcode.com/problems/house-robber/
# leetcode-198:
# 动态规划一:时间复杂度为O(n),空间复杂度为O(1), 战胜了80.6%
class Solution:
def rob(self, nums: List[int]) -> int:
yes, no = 0, 0
for i in nums:
no, yes = max(no, yes), no+i
return max(no, yes)
# 动态规划二:战胜了18.44%,与上面的差异仅在于语句:last, now = 0, 0
class Solution:
def rob(self, nums: List[int]) -> int:
last = now = 0 # 将这句改为:last, now = 0, 0后,战胜了80.6%
for i in nums:
last, now = now, max(last+i, now)
return now
本文分享自 MiningAlgorithms 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!