当前位置 博文首页 > 粽子小黑的博客：leetcode 个人刷题记录（Python）
好久没做题了，数据结构和算法是不能丢下的，因此争取每天做一些题，保持思维和手感。
39. 组合总和
回溯+剪枝
这里学到一个小技巧，把数组切片当作参数传进函数，这样就保证了递归下层选取是不比之前小的。其实就是之前C++写法的传指针。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
ans = []
def fun(target, candidates, now):
# now: list of chose
if target == 0:
ans.append(now)
return
for i, val in enumerate(candidates):
if target >= val:
fun(target-val, candidates[i:], now+[val])
else:
return
fun(target,candidates,[])
return ans
100. 相同的树
注释给了TreeNode的定义，前几天没有看，所以找了半天不会做。注意python中的并是 and 不是 &&。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p != None and q == None:
return False
elif p == None and q != None:
return False
elif p is None and q is None:
return True
elif p.val != q.val:
return False
else:
return ( self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right) )
去打球了，鸽一天咕咕咕咕。
93. 复原IP地址
第一个问题，类内定义函数没有写self,这样会提示错误。
可以直接用int()将string转换为数字，然后要判断前导零。
进入递归时先判断是否够长度。
class Solution:
def __init__(self):
self.ans = []
def isOk(self,s):
if s[0] == '0' and len(s) > 1:
return False
if int(s) <= 255:
return True
else:
return False
def fun(self, res, ans, cnt):
# res 剩余串， ans 已组成的答案, cnt 串数
if cnt > 4:
return
if len(res) == 0 and cnt == 4:
self.ans.append(ans[:-1])
return
if len(res) >= 1:
tmp = res[:1]
if self.isOk(tmp):
self.fun(res[1:], ans + tmp + ".", cnt + 1)
if len(res) >= 2:
tmp = res[:2]
if self.isOk(tmp):
self.fun(res[2:], ans + tmp + ".", cnt + 1)
if len(res) >= 3:
tmp = res[:3]
if self.isOk(tmp):
self.fun(res[3:], ans + tmp + ".", cnt + 1)
return
def restoreIpAddresses(self, s):
self.fun(s, "", 0)
return set(self.ans)
696. 计数二进制子串
垃圾题，垃圾代码
class Solution:
def countBinarySubstrings(self, s: str) -> int:
li = []
begin = s[0]
cnt = 1
for i, char in enumerate(s[1:]):
if char == begin:
cnt += 1
else:
begin = char
li.append(cnt)
cnt = 1
if i == len(s) - 2:
li.append(cnt)
ans = 0
for i, val in enumerate(li):
if i == len(li) - 1:
break
ans += min(val, li[i+1])
return ans
130. 被围绕的区域
简单的BFS
class Solution:
def solve(self, board):
"""
Do not return anything, modify board in-place instead.
"""
if board == []:
return
xPos = [1, 0, -1, 0]
yPos = [0, 1, 0, -1]
n, m = len(board), len(board[0])
vis, color = [([0] * m) for i in range(n)], [([0] * m) for i in range(n)]
# print(n,m)
# vis 用于标记是否访问， color 用于标色
def isOK(x, y):
if x < 0 or x > n - 1:
return False
if y < 0 or y > m - 1:
return False
if board[x][y] == 'X':
return False
if vis[x][y]:
return False
return True
def bfs(x, y):
if not isOK(x, y):
return
vis[x][y], color[x][y] = 1, 1
for xx, yy in zip(xPos, yPos):
bfs(x + xx, y + yy)
for x in range(n):
if board[x][0] == 'O':
bfs(x, 0)
if board[x][m - 1] == 'O':
bfs(x, m - 1)
for y in range(m):
if board[0][y] == 'O':
bfs(0, y)
if board[n - 1][y] == 'O':
bfs(n - 1, y)
for x in range(n):
for y in range(m):
if
