# Python3刷题系列（六）

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.走两步

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```

0 条评论

• ### 利用java自带的MD5加密

使用混淆的字符串是：{'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}

• ### 002.DNS-BIND简介

Bind是Berkeley Internet Name Domain Service的简写，它是一款实现DNS服务器的开放源码软件。已经成为世界上使用最为广泛的...

• ### c# 利用AForge.NET组件操作摄像头

private FilterInfoCollection videoDevices;

• ### Liunx命令行：vi详解

进入vi的命令 vi filename :打开或新建文件，并将光标置于第一行首 vi +n filename ：打开文件，并将光标置于第n行首 vi + ...

• ### springmvc整合axis2 过程

项目需要使用springmvc发布一个对外的服务，原来使用spring+cxf的结合，使用axis2的客户端调用，没有任何问题，但是使用pb9的客户端调用，一直...

• ### 001.常见监控简介

主动模式：客户端主动上报数据到服务器端，对服务器的开销较小，适合大规模的监控环境。

• ### 002.NFS相关配置项

<输出目录> [客户端1 选项（访问权限,用户映射,其他）] [客户端2 选项（访问权限,用户映射,其他）]

• ### linux应用之wget命令详解

wget是linux最常用的下载命令, 一般的使用方法是: wget + 空格 + 要下载文件的url路径

• ### NGINX 配置文件 fastcgi_pass

语法：fastcgi_pass fastcgi-server 默认值：none 使用字段：http, server, location 指定FastCGI...