DFS+回溯
17. [m]电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = “23” 输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
class Solution:def letterCombinations(self, digits: str) -> List[str]:dic=['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']def dfs(res,cur,idx):if idx==len(digits):res.append(''.join(cur))returndigit=ord(digits[idx])-ord('0')letters=dic[digit]for i in range(len(letters)):cur.append(letters[i])dfs(res,cur,idx+1)cur.pop()if not digits: return []res=[]dfs(res,[],0)return res
94. [e]二叉树的中序遍历
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res=[]
def dfs(root):
if not root: return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res
46.[m]全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res=[]
def dfs(x,n):
if x==n:
res.append(nums[:])
return
for i in range(x,n):
nums[i],nums[x]=nums[x],nums[i]
dfs(x+1,n)
nums[i],nums[x]=nums[x],nums[i]
dfs(0,len(nums))
return res
39. [m]组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res,cur=[],[]
n=len(candidates)
def dfs(start,total):
nonlocal res,cur
if total==target:
res.append(cur[:])
return
for i in range(start,n):
if total+candidates[i]<=target:
cur.append(candidates[i])
total+=candidates[i]
dfs(i,total) # 重复或者不重复使用需要注意这里
total-=candidates[i]
cur.pop()
dfs(0,0)
return res
22. [m]括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res=[]
def dfs(l,r,n,cur):
if l==n and r==n:
res.append(''.join(cur))
return
if l<n:
cur.append('(')
dfs(l+1,r,n,cur)
cur.pop()
if r<l:
cur.append(')')
dfs(l,r+1,n,cur)
cur.pop()
dfs(0,0,n,[])
return res
301. [h]删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。返回所有可能的结果。答案可以按 任意顺序 返回。
输入：s = “()())()” 输出：[“(())()”,”()()()”]
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
res = []
lremove, rremove = 0, 0
for c in s:
if c == '(':
lremove += 1
elif c == ')':
if lremove == 0:
rremove += 1
else:
lremove -= 1
def isValid(str):
cnt = 0
for c in str:
if c == '(':
cnt += 1
elif c == ')':
cnt -= 1
if cnt < 0:
return False
return cnt == 0
def helper(s, start, lremove, rremove):
if lremove == 0 and rremove == 0:
if isValid(s):
res.append(s)
return
for i in range(start, len(s)):
if i > start and s[i] == s[i - 1]:
continue
# 如果剩余的字符无法满足去掉的数量要求，直接返回
if lremove + rremove > len(s) - i:
break
# 尝试去掉一个左括号
if lremove > 0 and s[i] == '(':
helper(s[:i] + s[i + 1:], i, lremove - 1, rremove);
# 尝试去掉一个右括号
if rremove > 0 and s[i] == ')':
helper(s[:i] + s[i + 1:], i, lremove, rremove - 1);
# 统计当前字符串中已有的括号数量
helper(s, 0, lremove, rremove)
return res
51.[h] N皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
输入：n = 4 输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
solutions=[]
queens=[-1]*n # 每一行中queen的位置
columns=set()
row=['.']*n # 行
diagonal1=set()
diagonal2=set()
def generateBoard():
board=[]
for i in range(n):
row[queens[i]]='Q'
board.append(''.join(row))
row[queens[i]]='.'
return board
def backtrack(row:int):
if row==n:
board=generateBoard()
solutions.append(board)
return
for i in range(n):
if i in columns or row-i in diagonal1 or row+i in diagonal2:
continue
queens[row]=i
columns.add(i)
diagonal1.add(row-i)
diagonal2.add(row+i)
backtrack(row+1)
columns.remove(i)
diagonal1.remove(row-i)
diagonal2.remove(row+i)
backtrack(0)
return solutions
79.[m]单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i,j,k):
if i<0 or j<0 or i>=len(board) or j>=len(board[0]) or board[i][j]!=word[k]:
return False
if k==len(word)-1: return True
board[i][j]=""
res=dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i,j+1,k+1)
# 注意这里需要回退
board[i][j]=word[k]
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i,j,0):return True
return False
动态规划
70. [e]爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
class Solution:
def climbStairs(self, n: int) -> int:
if n<4:return n
a,b,c=1,2,3
for i in range(4,n+1):
a=b
b=c
c=a+b
return c
62. [m]不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp=[[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
dp[i][0]=1
for i in range(n):
dp[0][i]=1
for i in range(1,m):
for j in range(1,n):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[-1][-1]
64.[m]最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
class Solution:
# 动态规划即可
def minPathSum(self, grid: List[List[int]]) -> int:
m,n=len(grid),len(grid[0])
for i in range(1,n):
grid[0][i]+=grid[0][i-1]
for i in range(1,m):
grid[i][0]+=grid[i-1][0]
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[-1][-1]
338.[e]比特位计数
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
输入：n = 2 输出：[0,1,1] 解释： 0 —> 0 1 —> 1 2 —> 10
class Solution:
def countBits(self, n: int) -> List[int]:
# 动态规划递推 y=x&(x-1) 则y为x最低为1置为0后的数，有0<=y<x
res=[0]*(n+1)
for i in range(1,n+1):
res[i]=res[i&(i-1)]+1
return res
3. [m]无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s: return 0
ans,cur=0,0
dic=dict()
for j,v in enumerate(s):
i=dic.get(v,-1)
dic[v]=j
cur=cur+1 if cur<j-i else j-i
ans=max(ans,cur)
return ans
53. [e]最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans,cur=-inf,-inf
for v in nums:
cur=max(cur+v,v) # 让nums[i]单独称为一段还是和前面算在一起？
ans=max(ans,cur)
return ans
55.[m] 跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover,n=0,len(nums)
for i in range(n):
if i<=cover: # 要始终保证当前索引能够到达，也就是小于等于最远距离
cover=max(cover,i+nums[i])
if i>=n-1:return True
return False
72.[h]编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m,n=len(word1),len(word2)
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
for i in range(1,m+1):
for j in range(1,n+1):
left=dp[i][j-1]+1
top=dp[i-1][j]+1
top_left=dp[i-1][j-1]
if word1[i-1]!=word2[j-1]: top_left+=1
dp[i][j]=min(left,top,top_left)
return dp[m][n]
198.[m] 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
class Solution:
def rob(self, nums: List[int]) -> int:
# dp[i]=max(dp[i-1],dp[i-2]+nums[i])
n=len(nums)
if n<3: return max(nums)
first,second=nums[0],max(nums[0],nums[1])
for i in range(2,n):
first,second=second,max(first+nums[i],second)
return second
300.[m]最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# dp[i]=dp[j]+1 if nums[i]>nums[j]
n=len(nums)
dp=[1]*n
for i in range(n):
for j in range(i):
if nums[i]>nums[j]:
dp[i]=max(dp[i],dp[j]+1)
return max(dp)
101.[e]对称二叉树
判断一个二叉树是否轴对称
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
return self.isMirror(root,root)
def isMirror(self,p1,p2):
if not p1 and not p2: return True
if not p1 or not p2: return False
return p1.val==p2.val and self.isMirror(p1.left,p2.right) and self.isMirror(p1.right,p2.left)
104.[e]二叉树最大深度
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root: return 0
return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))
279. [m]完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
class Solution {
public:
int numSquares(int n) {
# dp[i]=1+{min(1,sqrt(i)}dp[i-j*j]
vector<int> dp(n+1);
for(int i=1;i<n+1;i++){
int minn=INT_MAX;
for(int j=1;j*j<=i;j++){
minn=min(minn,dp[i-j*j]);
}
dp[i]=minn+1;
}
return dp[n];
}
};
322. [m]零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
class Solution:
# 背包问题
def coinChange(self, coins: List[int], amount: int) -> int:
dp=[inf for _ in range(amount+1)]
dp[0]=0
for coin in coins:
for x in range(coin,amount+1):
dp[x]=min(dp[x],dp[x-coin]+1)
return dp[amount] if dp[amount]!=inf else -1
栈和队列
20. [e]有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
class Solution: def isValid(self, s: str) -> bool: if len(s)%2==1: return False dic={')':'(',']':'[','}':'{'} stk=[] for c in s: if c in dic: # 当没有匹配的左括号或者左右括号不匹配直接返回false if not stk or stk[-1]!=dic[c]: return False stk.pop() else: stk.append(c) return not stk
32.[h]最长有效括号
给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
class Solution:
def longestValidParentheses(self, s: str) -> int:
stk=[-1]
ans=0
for i,c in enumerate(s):
if c=='(':
stk.append(i) # 遇到左括号则将索引放入栈中
elif c==')':
stk.pop() # 遇到右括号弹出栈顶索引
if not stk: # 若栈为空，将当前右括号索引放入栈中
stk.append(i)
else: # 栈不为空的话更新答案
ans=max(ans,i-stk[-1])
return ans
4. [h]寻找两个正序数组的中位数
根据中位数的定义，当 m+n 是奇数时，中位数是两个有序数组中的第 (m+n)/2 个元素，当 m+n 是偶数时，中位数是两个有序数组中的第 (m+n)/2 个元素和第 (m+n)/2+1 个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第 k 小 的数，其中 k 为 (m+n)/2 或 (m+n)/2+1。
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def getKthElement(k):
"""
- 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
- 这里的 "/" 表示整除
- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 计 k/2-1 个
- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
- 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
- 这样 pivot 本身最大也只能是第 k-1 小的元素
- 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
- 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
- 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
"""
index1, index2 = 0, 0
while True:
# 特殊情况
if index1 == m:
return nums2[index2 + k - 1]
if index2 == n:
return nums1[index1 + k - 1]
if k == 1:
return min(nums1[index1], nums2[index2])
# 正常情况
newIndex1 = min(index1 + k // 2 - 1, m - 1)
newIndex2 = min(index2 + k // 2 - 1, n - 1)
pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
if pivot1 <= pivot2:
k -= newIndex1 - index1 + 1
index1 = newIndex1 + 1
else:
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
m, n = len(nums1), len(nums2)
totalLength = m + n
if totalLength % 2 == 1:
return getKthElement((totalLength + 1) // 2)
else:
return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2
23.[h] 合并k个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
from heapq import heappop,heappush
dummy=ListNode() # 设置空节点
curr=dummy
n=len(lists) # 链表的个数
pq=[]
for i in range(n):
if not lists[i]: continue # 当某个链表为空直接跳过
heappush(pq,(lists[i].val,i)) # 将不为空的第一层加入优先队列中，保存值包含链表的索引
while pq:
_,minIdx=heappop(pq) # 弹出堆顶的最小值和索引
curr.next=lists[minIdx] # 连接前面的节点
curr=curr.next # 更新当前指针
lists[minIdx]=lists[minIdx].next # 链表中对应节点后移
if lists[minIdx]: # 对应索引的链表节点不为空，将值和索引加入堆中
heappush(pq,(lists[minIdx].val,minIdx))
return dummy.next
347. [m]前k个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
dic=collections.Counter(nums) # 先统计所有元素的次数
pq=[]
for key,val in dic.items(): # 所有元素入小顶堆，保持k个即为结果
heapq.heappush(pq,(val,key))
if len(pq)>k:
heapq.heappop(pq)
ans=[]
for i in range(k):
fre,key=heapq.heappop(pq)
ans.append(key)
return ans
394. [m]字符串编码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
输入：s = “3[a]2[bc]” 输出：“aaabcbc” 输入：s = “abc3[cd]xyz” 输出：“abccdcdcdxyz”
class Solution:
def decodeString(self, s: str) -> str:
stk,res,multi=[],'',0
for c in s:
if '0'<=c<='9':
multi=multi*10+int(c)
elif c=='[':
stk.append([multi,res])
res,multi='',0
elif c==']':
cur_multi,last_res=stk.pop()
res=last_res+cur_multi*res
else:
res+=c
return res
406.[m]根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释： 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x:(-x[0],x[1])) # hi降序，ki升序
res=[]
for p in people:
# 只需要将其插入队列中，使得他的前面恰好有ki个即可
res.insert(p[1],p)
return res
链表集合
141.[e]环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next: return False
slow,fast=head,head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if fast==slow: return True
return False
142.[m]环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 走a+nb步一定是在环入口
# 第一次相遇时慢指针已经走了nb步
slow,fast=head,head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
if fast==slow:
fast=head
while fast!=slow:
slow=slow.next
fast=fast.next
return slow
return None
2. [m]两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy=ListNode(0)
cur=dummy
carry=0
while l1 or l2 or carry:
x=l1.val if l1 else 0
y=l2.val if l2 else 0
curSum=x+y+carry
carry=curSum//10
cur.next=ListNode(curSum%10)
cur=cur.next
if l1: l1=l1.next
if l2: l2=l2.next
return dummy.next
148. [m]排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
# 思路： 使用归并排序
# 1. 寻找链表中点，将链表分为两部分
# 2. 对子链表分别排序
# 3. 排序合并
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 空节点或者只剩一个节点退出
if not head or not head.next: return head
dummy=ListNode(0,head)
slow,fast=dummy,head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
head2=slow.next
slow.next=None # 断开节点
# 递归将两部分合并
return self.merge(self.sortList(head),self.sortList(head2))
def merge(self,l1,l2):
# 合并两个有序链表
dummy=ListNode(0)
cur=dummy
while l1 and l2:
if l1.val<l2.val:
cur.next=l1
l1=l1.next
else:
cur.next=l2
l2=l2.next
cur=cur.next
if l1:cur.next=l1
if l2:cur.next=l2
return dummy.next
242.[e]回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head or not head.next: return True
res=True
slow,fast=head,head.next
while fast and fast.next:
slow=slow.next
fast=fast.next.next
tmp=slow.next
p1,p2=head,self.reverseList(tmp)
rev=p2
while p1 and p2:
if p1.val!=p2.val: res=False
p1,p2=p1.next,p2.next
slow.next=self.reverseList(rev)
return res
def reverseList(self,head):
pre,cur=None,head
while cur:
nxt=cur.next
cur.next=pre
pre=cur
cur=nxt
return pre
24. [m]两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next: return head
newHead=head.next
head.next=self.swapPairs(newHead.next)
newHead.next=head
return newHead
25. [h]k个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy=ListNode(0) # 用于记录链表的第一个节点
dummy.next=head
pre=dummy
while head:
tail=pre
# 查看剩余部分长度是否大于等于k
for i in range(k):
tail=tail.next
if not tail: return dummy.next
# 剩余节点够k个
nxt=tail.next # 记录下一组的第一个节点
head,tail=self.reverse(head,tail)
# 把子链表重新接回原链表
pre.next=head
tail.next=nxt
pre=tail
head=tail.next
return dummy.next
def reverse(self,head,tail):
# 子链表从head到tail反转
pre=tail.next
cur=head
while pre!=tail:
nxt=cur.next
cur.next=pre
pre=cur
cur=nxt
return tail,head
岛屿问题集合
200.[h]岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入：grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ] 输出：1
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i,j):
if i<0 or i>=m or j<0 or j>=n or grid[i][j]!='1':
return
grid[i][j]='0'
dfs(i+1,j)
dfs(i-1,j)
dfs(i,j+1)
dfs(i,j-1)
m,n=len(grid),len(grid[0])
count=0
for i in range(m):
for j in range(n):
if grid[i][j]=='1':
dfs(i,j)
count+=1
return count
463.[e]岛屿的周长
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
if not grid: return 0
m,n=len(grid),len(grid[0])
ans=0
for x in range(m):
for y in range(n):
if grid[x][y]==1:
# 从左上角出发，当遇到1就周长就加4，如果右下方出现粘连则-2
ans+=4
if x<m-1 and grid[x+1][y]==1:
ans-=2
if y<n-1 and grid[x][y+1]==1:
ans-=2
return ans
695.[m]岛屿的最大面积
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0
class Solution:
def maxAreaOfIsland(self, grid):
m, n = len(grid), len(grid[0])
def dfs(i, j):
if i<0 or j<0 or i>=m or j>=n or grid[i][j]!=1:
return 0
grid[i][j] = 0
return 1 + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i + 1, j) + dfs(i, j - 1)
areas = [dfs(i, j) for i in range(m) for j in range(n) if grid[i][j]]
return max(areas) if areas else 0
高级数据结构
146.[m] LRU缓存机制
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
思路：
要想随机访问O(1) 复杂度，需要使用哈希表，如果哈希表的值存储链表的位置，则可以用O(1)时间访问链表，由于链表记录了访问顺序，需要存储键
class LRUCache:
def __init__(self, capacity: int):
self.dic=collections.OrderedDict()
self.remain=capacity
def get(self, key: int) -> int:
if key not in self.dic:
return -1
v= self.dic.pop(key)
self.dic[key]=v # 添加到字典末尾
return v
def put(self, key: int, value: int) -> None:
if key in self.dic:
self.dic.pop(key)
else:
if self.remain>0:
self.remain-=1
else: # self.dic is full
self.dic.popitem(last=False) # 弹出第一个元素
self.dic[key]=value
208.[m] 实现Trie(前缀树）
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
- Trie() 初始化前缀树对象。
- void insert(String word) 向前缀树中插入字符串 word 。
- boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false ```python class Trie:
def init(self):
self.root={} self.end_of_word="#"def insert(self, word: str) -> None:
node=self.root for ch in word: node=node.setdefault(ch,{}) node[self.end_of_word]=self.end_of_word
def search(self, word: str) -> bool:
node=self.root
for ch in word:
if ch not in node:
return False
node=node[ch]
return self.end_of_word in node
def startsWith(self, prefix: str) -> bool:
node=self.root
for ch in prefix:
if ch not in node:
return False
node=node[ch]
return True
<a name="PMlrq"></a>
### 547. [m]省份数量(并查集)
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。<br />省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。<br />给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。<br />返回矩阵中 省份 的数量。
```python
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
if not isConnected: return 0
n=len(isConnected)
self.parent=[i for i in range(n)]
for i in range(n):
for j in range(n):
if isConnected[i][j]==1:
self.union(i,j)
return len(set([self.find(i) for i in range(n)]))
def find(self, p: int) -> int:
root = p
while root != self.parent[root]: # 找领头元素
root = self.parent[root]
while self.parent[p] != p: # 路径压缩
x = p
p = self.parent[p]
self.parent[x] = root
return root
def union(self, p: int, q: int):
p1 = self.find(p)
p2 = self.find(q)
if p1 == p2:
return
self.parent[p1] = p2
双指针
11. [m]盛水最多的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
class Solution:
def maxArea(self, height: List[int]) -> int:
l,r=0,len(height)-1
ans=0
while l<r:
ans=max(ans,(r-l)*min(height[l],height[r]))
if height[l]<height[r]:
l+=1
else:
r-=1
return ans
42. [h]接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
class Solution:
def trap(self, height: List[int]) -> int:
if not height: return 0
n=len(height)
leftMax=[height[0]]+[0]*(n-1) # 记录每个位置左边最大值
for i in range(1,n):
leftMax[i]=max(leftMax[i-1],height[i])
rightMax=[0]*(n-1)+[height[n-1]] # 记录每个位置右边最大值
for i in range(n-2,-1,-1):
rightMax[i]=max(rightMax[i+1],height[i])
# 每个位置能够接的雨水等于左侧和右侧最大值中的较小值减去高度
ans=sum(min(leftMax[i],rightMax[i])-height[i] for i in range(n))
return ans
31. [m]下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
- 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
- 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 1. 从后向前寻找a[i]<a[i+1]的较小数a[i]
i=len(nums)-2
while i>=0 and nums[i]>=nums[i+1]:
i-=1
# 2. 从后向前寻找a[i]<a[j]的较大数a[j]
if i>=0:
j=len(nums)-1
while j>=0 and nums[i]>=nums[j]:
j-=1
nums[i],nums[j]=nums[j],nums[i]
# 3. 交换a[i]a[j]后，[i+1,n)必为降序，可以使用双指针翻转
l,r=i+1,len(nums)-1
while l<r:
nums[l],nums[r]=nums[r],nums[l]
l,r=l+1,r-1
15. [m]三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if not nums: return []
res=[]
nums.sort()
n=len(nums)
for first in range(n): # 枚举第一个数
if first>0 and nums[first]==nums[first-1]: continue # 跳过重复数字
third=n-1 # 第三个数对应数组最右端
target=-nums[first]
# 第一个数固定，接下来使用双指针遍历第二三个数
for second in range(first+1,n):
if second>first+1 and nums[second]==nums[second-1]:continue# 跳过重复数字
# 固定第二个数，第三个数从右往左遍历
while second<third and nums[second]+nums[third]>target:
third-=1
# 若第二个和第三个重合，则后面不会有a+b+c=0的结果
if second==third:break
if nums[second]+nums[third]==target:
res.append([nums[first],nums[second],nums[third]])
return res
647. [m]回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
输入：s = “abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”
class Solution:
def countSubstrings(self, s: str) -> int:
ans,n=0,len(s)
# n个字母组成的字符串共有2n-1个回文中心
for i in range(2*n-1):
l,r=i//2,i//2+i%2
while l>=0 and r<n and s[l]==s[r]:
l,r=l-1,r+1
ans+=1
return ans
287.[m]寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
本题和环形链表II相似，使用floyd判圈算法
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow,fast=0,0
n=len(nums)
while True:
slow=nums[slow]
fast=nums[nums[fast]]
if fast==slow:break
fast=0
while fast!=slow:
fast=nums[fast]
slow=nums[slow]
return slow
75.[m]颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n=len(nums)
p0,p1=0,0
for i in range(n):
if nums[i]==1:# 找到1则换到p1的位置上，并后移指针
nums[i],nums[p1]=nums[p1],nums[i]
p1+=1
elif nums[i]==0:# 找到0则换到p0位置上，
nums[i],nums[p0]=nums[p0],nums[i]
if p0<p1:# 将1所在的位置放在头部的末端
nums[i],nums[p1]=nums[p1],nums[i]
p0+=1
p1+=1
图像处理
48.[m]旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# 先水平翻转
m,n=len(matrix),len(matrix[0])
for i in range(m//2):
for j in range(n):
matrix[i][j],matrix[m-i-1][j]=matrix[m-i-1][j],matrix[i][j]
# 再对角线翻转
for i in range(m):
for j in range(i,n):
matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
二分查找
11. [m]旋转数组中的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
示例1
输入：numbers = [3,4,5,1,2] 输出：1
示例2
输入：numbers = [2,2,2,0,1] 输出：0
class Solution:
def minArray(self, numbers: [int]) -> int:
i, j = 0, len(numbers) - 1
while i < j:
m = (i + j) // 2
if numbers[m] > numbers[j]: i = m + 1
elif numbers[m] < numbers[j]: j = m
# nums[m]=nums[j]时无法判断x在[i,m]还是[m+1,j]
# 执行j-=1 缩小范围
else: j -= 1
return numbers[i]
33. [m]搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
class Solution:
def search(self, nums: List[int], target: int) -> int:
l,r=0,len(nums)-1
while l<=r:
mid=(l+r)>>1
if nums[mid]==target: return mid
if nums[0]<=nums[mid]:
if nums[0]<=target<nums[mid]:
r=mid-1
else:
l=mid+1
else:
if nums[mid]<target<=nums[len(nums)-1]:
l=mid+1
else:
r=mid-1
return -1
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l,r=0,len(nums)-1
while l<=r: # 查找右边界
mid=(l+r)>>1
if nums[mid]<=target:
l=mid+1
else:
r=mid-1
right=l-1
l=0
while l<=r: # 查找左边界
mid=(l+r)>>1
if nums[mid]>=target:
r=mid-1
else:
l=mid+1
left=r+1
if 0<=left<len(nums) and 0<=right and left<=right:
return [left,right]
return [-1,-1]
滑动窗口
56. [m]合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x:x[0])
merged=[]
for interval in intervals:
# 若合并列表为空或者合并列表尾部小于当前左端点说明不重合，直接加入结果中
if not merged or merged[-1][1]<interval[0]:
merged.append(interval)
else: # 否则就和上一个区间进行合并
merged[-1][1]=max(merged[-1][1],interval[1])
return merged
76. [h]最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”
class Solution:
def minWindow(self, s: str, t: str) -> str:
"""
步骤1：令滑动窗口包含目标的所有元素
步骤2：不断增加i，排除多余元素，直到碰到一个必须包含的元素
步骤3：让i增加一个位置，开始寻找下一个满足条件的滑动窗口
"""
# 统计目标字符个数，缺失字符个数
need, missing = collections.Counter(t), len(t)
i = start = end = 0
for j, c in enumerate(s, 1):
# 如果该字符在目标字符串中，则 missing -1
missing -= need[c] > 0
# 目标字符串对应字符个数-1
need[c] -= 1
if not missing: # 已经目标字符全部包含在内，此时多余的为负数
while need[s[i]] < 0: # need为负数代表这个元素时多余的，数量为0代表刚刚好
need[s[i]] += 1 # 遇到多余的元素，令其+1 达到0，然后右移
i += 1
# 到这里条件满足
if not end or j - i < end - start:
start, end = i, j
return s[start:end]
49. [m]字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dic=collections.defaultdict(list)
for s in strs:
counts=[0]*26
for ch in s:
counts[ord(ch)-ord('a')]+=1
dic[tuple(counts)].append(s)
return list(dic.values())
581.[m]最短无序连续子数组
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
n=len(nums)
# 分别从两侧寻找左右边界，数组分为numsA,numsB,numsC
# 寻找右边界，numsA,numsB 元素均小于numsC元素
maxn,r=float('-inf'),-1 # maxn记录左边的最大值，定位右边界
minn,l=float('inf'),-1 # minn记录右边的最小值，定位左边界
for i in range(n):
if nums[i]<maxn:#maxn:表示前一项;nums[i]:表示当前项
# 可理解为:前一项比当前项大时,该数组不为升序数组,并记录当前项.
# 遍历一次后，r即为最后一个使之不为升序数组的数. left同理
r=i
else:
maxn=nums[i]
if nums[n-i-1]>minn:
l=n-i-1
else:
minn=nums[n-i-1]
return 0 if r==-1 else r-l+1
5. [m]最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
class Solution:
def longestPalindrome(self, s: str) -> str:
n=len(s)
start,end=0,0
for i in range(2*n-1):
l,r=i//2,i//2+i%2
l1,r1=self.expand(s,l,r)
if r1-l1>end-start:
start,end=l1,r1
return s[start:end+1]
def expand(self,s,l,r):
while l>=0 and r<len(s) and s[l]==s[r]:
l,r=l-1,r+1
return l+1,r-1
二叉树
617.[e]合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
# 若两个二叉树对应节点都为空，则合并后也为空
# 若只有一个为空，则合并后为其中的非空节点
# 若都不为空，则合并后为两个节点之和
if not t1: return t2
if not t2: return t1
merged=TreeNode(t1.val+t2.val)
merged.left=self.mergeTrees(t1.left,t2.left)
merged.right=self.mergeTrees(t1.right,t2.right)
return merged
226. [e]翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root: return None
root.left,root.right=root.right,root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
102.[m]二叉树层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
que=collections.deque()
que.append(root)
res=[]
while que:
tmp,n=[],len(que)
for i in range(n):
node=que.popleft()
tmp.append(node.val)
if node.left:que.append(node.left)
if node.right: que.append(node.right)
res.append(tmp[:])
return res
若有收获，就点个赞吧
0 人点赞
