檢測循環依賴

題目鏈接

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] -= 1if indeg[j] == 0:q.append(j)if len(res) == n:return reselse: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=-xxreturn xx if -2**31<=xx<=2**31-1 else 0

LCR 170. 交易逆序對的總數

題目鏈接

歸并排序。

class Solution:# nums中逆序對的個數等于左半部分逆序對個數+右半部分逆序對個數+跨左右兩部分逆序對個數def merge(self,left,right):merged=[]i,j=0,0count=0while i<len(left) and j<len(right):if left[i]<=right[j]:merged.append(left[i])i+=1else:merged.append(right[j])j+=1# 說明 left[i] 及其后面的所有元素都大于 right[j]count+=len(left)-iwhile i<len(left):merged.append(left[i])i+=1while j<len(right):merged.append(right[j])j+=1return merged,countdef merge_sort(self,nums):if len(nums)<=1:return nums,0mid=len(nums)//2left,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_rightdef 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 Truei,cover=0,0while i<=cover:cover=max(i+nums[i],cover)if cover>=len(nums)-1:return Truei+=1return 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:returntraversal(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.0if n<0:x,n=1/x,-nres=1while n:if n&1:res*=xx*=xn>>=1return 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:returnif s==target:res.append(path[:])return resfor i in range(startIndex,len(candidates)):# 關鍵if i>startIndex and candidates[i]==candidates[i-1] and used[i-1]==False:continues+=candidates[i]path.append(candidates[i])used[i]=Truebacktracking(candidates,target,s,i+1)s-=candidates[i]path.pop()used[i]=Falsecandidates.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,0while i>=0 and j<n:if target>matrix[i][j]:j+=1elif target<matrix[i][j]:i-=1else:return Truereturn False

26. 刪除有序數組中的重復項

題目鏈接

class Solution:def removeDuplicates(self, nums: List[int]) -> int:i=0for num in nums:if i==0 or nums[i-1]!=num:nums[i]=numi+=1return 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 Nonen=1cur=headwhile cur.next:n+=1cur=cur.nextcur.next=head # 成環for _ in range(n-k%n):cur=cur.nextnewHead=cur.nextcur.next=Nonereturn newHead