class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res=[] path=[] def backtracking(nums,index): res.append(path[:]) ifindex>=len(nums): return for i in range(index,len(nums)): path.append(nums[i]) backtracking(nums,i+1) path.pop() backtracking(nums,0) returnres
python 的位运算符;
& :and运算,参与运算的两个值相应位为1,则结果为1
|:or 运算,只要对应的两个二位有一个为1,结果就为1
^: XOR运算,两个对应的相异的时候,结果为1
~:not运算,
<< 左移运算符,
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution: def subsets(self, S: List[int]) -> List[List[int]]: sub_sets=[] n=len(S) # 1<<n 相当于2^n次方,range(1<<n)相当于0~2^n-1 for i in range(1<<n): sub_set=[] for j in range(n): # &1 相当于取最后一位 if i>>j&1: sub_set.append(S[j]) sub_sets.append(sub_set) return sub_sets
class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: # 最大面积的正方形 # 积分图的方式 max_len=0 m,n=len(matrix),len(matrix[0]) dp=[] for i in range(m): sub_dp=[] for j in range(n): matrix[i][j]=int(matrix[i][j]) if matrix[i][j]==1: max_len=1 sub_dp.append(matrix[i][j]) dp.append(sub_dp)
for i in range(1,m): for j in range(1,n): if matrix[i][j]==1 and dp[i-1][j]>=1 and dp[i][j-1]>=1 and dp[i-1][j-1]>=1: dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1 if dp[i][j]>max_len: max_len=dp[i][j] return max_len*max_len
classSolution: defcountPrimes(self, n: int) -> int: is_prime = [True]*(n) ans = 0 for num inrange(2,n): if is_prime[num]: ans+=1 # 右边界:因为数字最大是n-1 所以只需要到(n-1)//num 右边是开区间 所以+1 for k inrange(1,(n-1)//num+1): is_prime[num*k]=False return ans
# 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 generateTrees(self, n: int) -> List[TreeNode]: if n==0: return []
def recursionTree(left,right): # 生成left-right之间的树 if left>right: return [None] trees=[] for i inrange(left,right+1): left_trees=recursionTree(left,i-1) right_trees=recursionTree(i+1,right) for left_tree in left_trees: for right_tree in right_trees: curr_tree=TreeNode(i) curr_tree.left=left_tree curr_tree.right=right_tree trees.append(curr_tree) return trees return recursionTree(1,n)
defcheck(i: int, j: int, k: int) -> bool: if board[i][j] != word[k]: returnFalse if k == len(word) - 1: returnTrue
visited.add((i, j)) result = False for di, dj in directions: newi, newj = i + di, j + dj if0 <= newi < len(board) and0 <= newj < len(board[0]): if (newi, newj) notin visited: if check(newi, newj, k + 1): result = True break
visited.remove((i, j)) return result
h, w = len(board), len(board[0]) visited = set() for i inrange(h): for j inrange(w): if check(i, j, 0): returnTrue
class Solution: def numTilePossibilities(self, tiles: str) -> int: res=set() path=[] hashmap={} for i in range(len(tiles)): if tiles[i] in hashmap: hashmap[tiles[i]]+=1 else: hashmap[tiles[i]]=1
def backtracking(tiles):
temp=''.join(path[:]) if temp!=''and temp not in res: res.add(temp)
for i in range(len(tiles)): while(hashmap[tiles[i]]==0): i=i+1 if i ==len(tiles): return hashmap[tiles[i]]-=1 path.append(tiles[i]) backtracking(tiles) va=path.pop() hashmap[va]+=1 backtracking(tiles) returnlen(res)
nonlocal flag for i inrange(index+1,len(s)+1): if flag>0andint(s[index:i])<=255: if i!=index+1andint(s[index])==0: return path.append(s[index:i]) path.append('.') flag-=1 else: return backtracking(s,i) path.pop() path.pop() flag+=1 backtracking(s,0) return res
for i in range(n): # 根据前面的path可以得出目前行能走的路线 forbid=[] forj in range(len(path)): forbid.append(path[j]) forbid.append(path[j]+len(path)-j) forbid.append(path[j]+j-len(path)) if i not in forbid: path.append(i) backtracking(n) path.pop() backtracking(n)
rest=[] # 翻译 for i in range(len(res)): rest.append([]) forj in range(len(res[0])): temp=['.'for _ in range(n)] temp[res[i][j]]='Q' #合成 ts='' fork in temp: ts+=k rest[-1].append(ts) return rest