目录
检测循环依赖
def haveCircularDependency(self, n: int, prerequisites):
g = [[]for i in range(n)] #邻接表存储图结构
indeg = [0 for i in range(n)] #每个点的入度
res = [] #存储结果序列
q = deque()
#将依赖关系加入邻接表中g，并各个点入度
for pre in prerequisites:
a, b = pre[0], pre[1]
g[a].append(b)
indeg[b] += 1
#一次性将入度为0的点全部入队
for i in range(n):
if indeg[i] == 0:
q.append(i)
while q:
t = q.popleft()
res.append(t)
#删除边时，将终点的入度-1。若入度为0，果断入队
for j in g[t]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
if len(res) == n:
return res
else:
return []
类似题目 207. 课程表、210. 课程表 II
7. 整数反转
class Solution:
def reverse(self, x: int) -> int:
sx=str(x)
if sx[0]!="-":
xx=int(sx[::-1])
else:
xx=int(sx[:0:-1])
xx=-xx
return xx if -2**31<=xx<=2**31-1 else 0
LCR 170. 交易逆序对的总数
归并排序。
class Solution:
# nums中逆序对的个数等于左半部分逆序对个数+右半部分逆序对个数+跨左右两部分逆序对个数
def merge(self,left,right):
merged=[]
i,j=0,0
count=0
while i<len(left) and j<len(right):
if left[i]<=right[j]:
merged.append(left[i])
i+=1
else:
merged.append(right[j])
j+=1
# 说明 left[i] 及其后面的所有元素都大于 right[j]
count+=len(left)-i
while i<len(left):
merged.append(left[i])
i+=1
while j<len(right):
merged.append(right[j])
j+=1
return merged,count
def merge_sort(self,nums):
if len(nums)<=1:
return nums,0
mid=len(nums)//2
left,count_left=self.merge_sort(nums[:mid])
right,count_right=self.merge_sort(nums[mid:])
merged,count_merge=self.merge(left,right)
return merged,count_merge+count_left+count_right
def reversePairs(self, nums: List[int]) -> int:
return self.merge_sort(nums)[1]
55. 跳跃游戏
class Solution:
def canJump(self, nums: List[int]) -> bool:
if len(nums)==1:
return True
i,cover=0,0
while i<=cover:
cover=max(i+nums[i],cover)
if cover>=len(nums)-1:
return True
i+=1
return False
45. 二叉树的后序遍历
递归
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
lis=[]
def traversal(root):
if not root:
return
traversal(root.left)
traversal(root.right)
lis.append(root.val)
traversal(root)
return lis
非递归
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
WHITE,GRAY=0,1 # 新节点为白色，已访问过的节点为灰色
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
if node is None: continue
# 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
if color == WHITE:
stack.append((GRAY, node))
stack.append((WHITE, node.right))
stack.append((WHITE, node.left))
# 如果遇到的节点为灰色，则将节点的值输出。
else:
res.append(node.val)
return res
50. Pow(x, n)
class Solution:
def myPow(self, x: float, n: int) -> float:
# 快速幂
if x==0.0:
return 0.0
if n<0:
x,n=1/x,-n
res=1
while n:
if n&1:
res*=x
x*=x
n>>=1
return res
40. 组合总和 II
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
path=[]
res=[]
def backtracking(candidates,target,s,startIndex):
if s>target:
return
if s==target:
res.append(path[:])
return res
for i in range(startIndex,len(candidates)):
# 关键
if i>startIndex and candidates[i]==candidates[i-1] and used[i-1]==False:
continue
s+=candidates[i]
path.append(candidates[i])
used[i]=True
backtracking(candidates,target,s,i+1)
s-=candidates[i]
path.pop()
used[i]=False
candidates.sort()
used=[False]*len(candidates)
backtracking(candidates,target,0,0)
return res
74. 搜索二维矩阵
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 二维数组从左往右递增，从上往下递增
# 故想到以二维数组左下角为原点，建立直角坐标轴
m,n=len(matrix),len(matrix[0])
i,j=m-1,0
while i>=0 and j<n:
if target>matrix[i][j]:
j+=1
elif target<matrix[i][j]:
i-=1
else:
return True
return False
26. 删除有序数组中的重复项
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i=0
for num in nums:
if i==0 or nums[i-1]!=num:
nums[i]=num
i+=1
return i
类似题目 27. 移除元素
61. 旋转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return None
n=1
cur=head
while cur.next:
n+=1
cur=cur.next
cur.next=head # 成环
for _ in range(n-k%n):
cur=cur.next
newHead=cur.next
cur.next=None
return newHead