# Python3刷题系列（五）

1，leetcode-200（岛屿的个数）

2，leetcode-36（有效的数独）

3，leetcode-146（LRU）

4，leetcode-10（正则表达式匹配）

5，leetcode-64（最小路径和）

6，leetcode-322（零钱兑换）

7，leetcode-121（买卖股票的最佳时机）

8，leetcode-152（乘积最大子序列）

9，leetcode-120（三角形最小路径和）

1，Number of Islands（岛屿的个数）：

```class Solution:
def numIslands(self, grid):
res = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == "1":
self.dfs(grid, r, c)
res += 1
return res

def dfs(self, grid, i, j):
dirs = [[-1, 0], [0, 1], [0, -1], [1, 0]]
grid[i][j] = "0"
for dir in dirs:
nr, nc = i + dir[0], j + dir[1]
if nr >= 0 and nc >= 0 and nr < len(grid) and nc < len(grid[0]):
if grid[nr][nc] == "1":
self.dfs(grid, nr, nc)
```

2，Valid Sudoku（有效的数独）：

```class Solution:
def isValidSudoku(self, board):
raw = [{},{},{},{},{},{},{},{},{}]
col = [{},{},{},{},{},{},{},{},{}]
cell = [{},{},{},{},{},{},{},{},{}]
for i in range(9):
for j in range(9):
num = (3*(i//3) + j//3)#找单元
temp = board[i][j]
if temp != ".":
if temp not in raw[i] and temp not in col[j] and temp not in cell[num]:
raw [i][temp] = 1
col [j][temp] = 1
cell [num][temp] =1
else:
return False
return True```

3，leetcode-146：“最近最少使用”算法

```class LRUCache(object):

def __init__(self, capacity):
self.capacity = capacity
self._cache = []
self._cache_look_up = {}

def get(self, key):
if key not in self._cache_look_up:
return -1

self._cache.remove(key)
self._cache.append(key)

return self._cache_look_up[key]

def put(self, key, value):
if key in self._cache_look_up:
self._cache_look_up[key] = value
self._cache.remove(key)
self._cache.append(key)
return
else:
if len(self._cache) == self.capacity:
del_key = self._cache[0]
self._cache = self._cache[1:]
del self._cache_look_up[del_key]

self._cache.append(key)
self._cache_look_up[key] = value```

4，Regular Expression Matching（正则表达式匹配）

```# leetcode-10:
class Solution(object):
def isMatch(self, s, p):
""" :type s: str :type p: str :rtype: bool """
dp = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
dp[0][0] = True
for j in range(2,len(p) + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
for i in range(1,len(s) + 1):
for j in range(1,len(p) + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j-1] or dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
elif p[j-1] == '.' or s[i-1] == p[j - 1]:
dp[i][j] = dp[i-1][j-1]

return dp[len(s)][len(p)]
# reference:http://www.voidcn.com/article/p-zioiffqq-mm.html```

5，Minimum Path Sum（最小路径和）

```# leetcode-64: O(m*n),逐步更新grid元素为最短路径值，是一种时间复杂度对高的解法
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)  # 行数
n = len(grid[0])  # 列数
# 更新第一列元素这为路径值
for i in range(1,m):
grid[i][0] += grid[i-1][0]
# 更新第一行值为路径值
for j in range(1, n):
grid[0][j] += grid[0][j-1]
# 从第二行第二列开始更新[i][j]数值为路径值
for i in range(1, m):
for j in range(1, n):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]```

6，Coin Change （零钱兑换）

```# leetcode-322: BFS广度优先搜索，怎么保证路径最短的？
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount == 0:
return 0
value1 = [0]
value2 = []
nc =  0
visited = [False]*(amount+1)  # 记录是否来过这里
visited[0] = True  # 已经来过amount=0这个数额的money
while value1:
nc += 1  # 记录步数
for v in value1:
for coin in coins:   # 广度搜索：遍历一遍cions中的元素
newval = v + coin
if newval == amount:
return nc  # 出口一：存在路径
elif newval > amount:
continue   # 跳出for coin循环，但是，仍然在外层的for循环中，继续遍历下一个value1中的元素v
elif not visited[newval]:
visited[newval] = True
value2.append(newval)
value1, value2 = value2, []   # 当value2=[]时，跳出while循环，执行return -1 语句

return -1   # 出口二：不存在路径```

7，Best Time to Buy and Sell Stock（买卖股票的最佳时机）

```# leetcode-121:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) < 2:
return 0
prof = 0
min_p = prices[0]
for i in prices:
min_p = min(i, min_p)
prof = max(i - min_p, prof)
return prof

# 暴力解法（超时）：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0   # 如果prices为空[]，则返回0.

l = len(prices)
res = []

for i in range(l):
for j in range(i+1, l):
res.append(prices[j] - prices[i])

if not res:
return 0   # 如果res为空[]，则返回0.
else：
return max(max(res), 0)```

8，Maximum Product Subarray（乘积最大子序列）

```# leetcode-152：动态优化，与上题leetcode-121极其相似
class Solution:  # O(n)
def maxProduct(self, nums: List[int]) -> int:
max_p = min_p = nums[0]
res = nums[0]
for i in range(1, len(nums)):
lastmax = max_p
max_p = max(min_p*nums[i], lastmax*nums[i], nums[i])
min_p = min(min_p*nums[i], lastmax*nums[i], nums[i])
res = max(res, max_p)
return res

# 暴力解法：O(n^2)
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]

l = len(nums)
res = []
element = 1
for i in range(l):
for j in range(i+1, l):
for r in range(i, j+1):
element = element * nums[r]
res.append(element)
element = 1
if not res:
return 0
else:
return max(max(res), max(nums))```

9，Triangle（三角形最小路径和）

```# leetcode-120: O(n(n-1)/2):时间复杂度仍为O(n^2),逐个修改矩阵元素值为最短路径值，时间复杂度最高的一种解法，但让然战胜了82.66%
class Solution:  # 自顶向下更新矩阵
def minimumTotal(self, triangle: List[List[int]]) -> int:
l = len(triangle)
if l == 0:
return 0
if l == 1:
return triangle[0][0]
for i in range(1, l):
for j in range(1, i):
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
triangle[i][i] += triangle[i-1][i-1]  # 需要注意矩阵行向量的index=0，-1 的元素，要单独更新
triangle[i][0] += triangle[i-1][0]
return min(triangle[l-1])

# 法二：自底向上更新矩阵, 时间复杂度与上面一样，但是，之战胜了24.81%
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
l = len(triangle)
if l == 0:
return 0
if l == 1:
return triangle[0][0]
for i in range(l-2, -1, -1):
for j in range(0, i+1):
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])

return triangle[0][0]```

Reference：

https://blog.csdn.net/fuxuemingzhu/article/details/81126995

https://blog.csdn.net/weixin_42304045/article/details/80600022

https://blog.csdn.net/laughing2333/article/details/70231547

0 条评论

• ### 生信（七）生信中常用命令

（说明：我们拿到的bed文件时常是客户在Windows系统下编辑好的，其行尾是\r\n，在进行NGS分析前最好将其转换为Unix风格的行尾\n。）

• ### 【趣学程序】集群之间配置SSH无密码登录

注意 假设以上配置是在A机器上配置的，目标机器为B。那么我们就可以在A机器上通过 ssh B的IP 访问B这台机器了 如果你想在B电脑上也可以免密登录A机器，那...

• ### 【趣学程序】Linux基础命令

常用：/home /etc /mnt /root /opt /tmp /usr /var

• ### Shell（一）好的操作习惯

前一段时间顺丰运维人员将生产数据库删除的传闻着实成为了新闻热词，如果传闻是真的，相信那位运维也是无心之过，可能只是一瞬的手误。但是代价太大了，业内人员都懂的。

• ### 通过脚本在Docker环境中一键安装mysql主从环境

其中hostip是必须修改的,其他配置可以酌情修改. 注意: 如果你的Docker环境是通过Docker Toolbox,且是安装在windows环境,建议将...

• ### 如何在Linux中发现IP地址冲突

你们都知道什么是IP地址，是吧？它们被分配给网络上的设备来代表它们。它们通过DHCP服务器分配并且会经常改变。现在有两种IP地址。动态的一种会经常改变（几天一次...

• ### Flume安装及部署

注意：Namenode 和 ResourceManger 如果不是同一台机器，不能在 NameNode 上启动 yarn，应该在 ResouceManager ...