LeetCode 0001 两数之和 (简单, 2021-10)LeetCode 0002 两数相加 (中等, 2021-10)LeetCode 0003 无重复字符的最长子串 (中等, 2022-02)LeetCode 0004 寻找两个正序数组的中位数 (困难, 2022-02)LeetCode 0005 最长回文子串 (中等, 2021-10)LeetCode 0010 正则表达式匹配 (困难, 2022-01)LeetCode 0011 盛最多水的容器 (中等, 2021-10)LeetCode 0015 三数之和 (中等, 2021-10)LeetCode 0016 最接近的三数之和 (中等, 2021-10)LeetCode 0019 删除链表的倒数第N个结点 (中等, 2022-01)LeetCode 0020 有效的括号 (简单, 2022-03)LeetCode 0021 合并两个有序链表 (简单, 2021-10)LeetCode 0025 K个一组翻转链表 (困难, 2022-02)LeetCode 0029 两数相除 (中等, 2021-10)LeetCode 0033 搜索旋转排序数组 (中等, 2021-10)LeetCode 0042 接雨水 (困难, 2021-10)LeetCode 0053 最大子数组和 (简单, 2022-01)LeetCode 0064 最小路径和 (中等, 2022-01)LeetCode 0070 爬楼梯 (简单, 2022-01)LeetCode 0072 编辑距离 (困难, 2022-01)LeetCode 0086 分隔链表 (中等, 2021-10)LeetCode 0091 解码方法 (中等, 2022-02)LeetCode 0096 不同的二叉搜索树 (中等, 2022-03)LeetCode 0098 验证二叉搜索树 (中等, 2022-03)LeetCode 0104 二叉树的最大深度 (简单, 2021-10)LeetCode 0110 平衡二叉树 (简单, 2022-02)LeetCode 0111 二叉树的最小深度 (简单, 2021-10)LeetCode 0112 路径总和 (简单, 2022-02)LeetCode 0113 路径总和II (中等, 2022-02)LeetCode 0120 三角形最小路径和 (中等, 2022-01)LeetCode 0121 买卖股票的最佳时机 (简单, 2022-01)LeetCode 0122 买卖股票的最佳时机II (中等, 2022-01)LeetCode 0123 买卖股票的最佳时机III (困难, 2022-01)LeetCode 0124 二叉树中的最大路径和 (困难, 2022-02)LeetCode 0129 求根节点到叶节点数字之和 (中等, 2022-02)LeetCode 0143 重排链表 (中等, 2022-01)LeetCode 0152 乘积最大子数组 (中等, 2022-01)LeetCode 0167 两数之和2(输入有序数组) (简单, 2021-10)LeetCode 0187 重复的DNA序列 (中等, 2021-10)LeetCode 0198 打家劫舍 (中等, 2022-02)LeetCode 0213 打家劫舍II (中等, 2022-02)LeetCode 0240 搜索二维矩阵2 (中等, 2021-10)LeetCode 0257 二叉树的所有路径 (简单, 2022-02)LeetCode 0279 完全平方数 (中等, 2022-02)LeetCode 0300 最长递增子序列 (中等, 2022-01)LeetCode 0322 零钱兑换 (中等, 2022-02)LeetCode 0337 打家劫舍III (中等, 2022-02)LeetCode 0343 整数拆分 (中等, 2021-12)LeetCode 0352 将数据流变为多个不相交区间 (困难, 2021-10)LeetCode 0434 字符串中的单词数 (简单, 2021-10)LeetCode 0437 路径总和III (中等, 2022-02)LeetCode 0441 排列硬币 (简单, 2021-10)LeetCode 0474 一和零 (中等, 2022-02)LeetCode 0496 下一个更大元素 (简单, 2021-11)LeetCode 0518 零钱兑换II (中等, 2022-02)LeetCode 0611 有效三角形的个数 (中等, 2021-10)LeetCode 0859 亲密字符串 (简单, 2021-11)LeetCode 0876 链表的中间结点 (简单, 2022-01)LeetCode 0915 分割数组 (中等, 2022-01)LeetCode 0958 二叉树的完全性检验 (中等, 2022-03)LeetCode 0988 从叶结点开始的最小字符串 (中等, 2022-02)
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。详细描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python3
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]: # noqa
""""""
tmp = dict()
for i in range(len(nums)):
left = target - nums[i] # 减去当前值
if left in tmp: # 如果差值在哈希表中，说明找到了答案
return [tmp[left], i]
tmp[nums[i]] = i # 保存当前值的位置
return []
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。详细描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例2：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None): # noqa
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # noqa
ret = p = ListNode()
s = 0
# 注意遍历条件，当三个都不为真时才会结束
while l1 or l2 or s != 0: # s != 0 表示最后一次相加存在进位的情况
s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
p.next = ListNode(s % 10) # 个位
p = p.next
# 遍历链表
if l1:
l1 = l1.next
if l2:
l2 = l2.next
s = s // 10 # 进位
return ret.next
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。- 维护一个已经出现过的字符集合，详见代码；
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = set()
l = r = 0 # 窗口边界
ret = 0
while r < len(s):
while s[r] in used: # 如果已经出现过则移出
# 注意这里要 while 判断，因为 l 指针不一定刚好指向这个重复的字符，要一直移动直到把 r 指向的字符移出
used.remove(s[l])
l += 1
ret = max(ret, r - l + 1)
used.add(s[r])
r += 1
return ret优化：直接移动 l 指针到重复字符的下一个位置，减少 l 指针移动；
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = dict()
l = r = 0 # [l, r] 闭区间
ret = 0
while r < len(s):
if s[r] in used and l <= used[s[r]]: # l <= used[s[r]] 的意思是重复字符出现在窗口内；
l = used[s[r]] + 1
ret = max(ret, r - l + 1)
used[s[r]] = r
r += 1
return ret
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。-
二分目标：找到最大的
i，使A[i - 1] <= B[j]，其中j = (m + n + 1) / 2 - i，m, n分别为A, B的长度； -
思路简述：将
A, B分别分成如下两组，且保证max(A_i-1, B_j-1) <= min(A_i, B_j)，根据中位数的性质，目标值即max(A_i-1, B_j-1)；- 可证，该条件等价于找到最大的
i，使A[i - 1] <= B[j]（证明详见参考链接）
A_0, .., A_i-1 | A_i, .., A_m-1 B_0, .., B_j-1 | B_j, .., B_n-1 其中 i + j == (m + n + 1) / 2 这里使用 (m + n + 1) / 2 而不是 (m + n) / 2， 是为了使当 m + n 为奇数时，前一半比后一半多一个，即 i + j == (m + n) - (i + j) + 1； 偶数时不影响； - 可证，该条件等价于找到最大的
-
关于
i == 0/m, j == 0/n的处理细节见代码；
Python
class Solution:
def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:
if len(A) > len(B):
return self.findMedianSortedArrays(B, A)
inf = 1e7
m, n = len(A), len(B)
# half 表示一半的数量；+1 是为了使奇数情况时，左侧数量多一个，偶数不影响；
half = (m + n + 1) // 2
l, r = 0, m # [l, r) 左闭右开区间，循环时要始终保持这个开闭原则
while l < r: # 因为是左闭右开区间，所以 l 要始终小于 r
# 这里 i 和 j 指的是数量，而不是下标，即 A 中的前 i 个数，B 中的前 j 个数；
# i + j 共同组成了“前一半”的数
i = (l + r + 1) // 2
j = half - i
# 因为 i 和 j 都是指的数量，所以下标要 -1；具体来说，i 和 j 分别把 A 和 B 划分成了如下两个区间
# 前一半包括 A[0 .. i-1] 和 B[0 .. j-1]
# 后一半包括 A[i .. m-1] 和 B[j .. n-1]
# 二分的目标是找到最大的 i 使 A[i - 1] <= B[j] 成立
if A[i - 1] <= B[j]:
l = i # [l, i-1] 区间满足要求，下一轮在 [i, r) 中继续找更大的，所以使 l = i
else:
r = i - 1 # [i-1, r) 区间不满足要求，下一轮从 [l, i-1) 继续找符合的，所以令 r = i - 1
# 退出循环时 l == r
i = (l + r + 1) // 2
j = half - i
# 根据 i 和 j 的定义，都表述“数量”，所以
# i == 0 表示不从 A 取数，“前一半”数都从 B 中取；
# i == m 表示取 A 中所有数，剩下的从 B 中取；
# j == 0, j == n 含义类似
a_im1 = -inf if i == 0 else A[i - 1]
a_i = inf if i == m else A[i]
b_jm1 = -inf if j == 0 else B[j - 1]
b_j = inf if j == n else B[j]
# m1：前一部分的最大值
# m2：后一部分的最小值
m1, m2 = max(a_im1, b_jm1), min(a_i, b_j)
return (m1 + m2) / 2 if (m + n) % 2 == 0 else m1
给你一个字符串 s，找到 s 中最长的回文子串。详细描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 状态定义：
dp[i][j] := 子串 s[i:j] 是否为回文串； - 状态转移方程：
dp[i][j] := dp[i+1][j-1] == True 且 s[i] == s[j]； - 初始状态
- 单个字符：
dp[i][j] := True当i == j - 两个连续相同字符：
dp[i][j] := True当j == i + 1 && s[i] == s[j]
- 单个字符：
注意：
- 动态规划并不是最适合的解，这里仅提供一个思路；
- 如果要使用动态规划解本题，如何循环是关键，因为回文串的特点，从“双指针”的角度来看，需要从中心往两侧遍历，这跟大多数的 dp 问题略有不同；
C++
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
int max_len = 1; // 保存最长回文子串长度
int start = 0; // 保存最长回文子串起点
// 初始状态1：子串长度为 1 时，显然是回文子串
for (int i = 0; i < n; i++)
dp[i][i] = 1;
//for (int j = 1; j < n; j++) // 子串结束位置
// for (int i = 0; i < j; i++) { // 子串起始位置
// 上述循环方式也是可以的，但在 “最长回文子序列” 一题中会有问题
// 下面的循环方式在两个问题中都正确，这个遍历思路比较像“中心扩散法”
for (int j = 1; j < n; j++) // 子串结束位置
for (int i = j - 1; i >= 0; i--) { // 子串开始位置
if (j == i + 1) // 初始状态2：子串长度为 2 时，只有当两个字母相同时才是回文子串
dp[i][j] = (s[i] == s[j]);
else // 状态转移方程：当上一个状态是回文串，且此时两个位置的字母也相同时，当前状态才是回文串
dp[i][j] = (dp[i + 1][j - 1] && s[i] == s[j]);
// 保存最长回文子串
if (dp[i][j] && max_len < (j - i + 1)) {
max_len = j - i + 1;
start = i;
}
}
return s.substr(start, max_len);
}
};Python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
start = 0
length = 1
for j in range(1, n): # 子串的结束位置
for i in range(j - 1, -1, -1): # 子串的开始位置
if i == j - 1:
dp[i][j] = 1 if s[i] == s[j] else 0
else:
dp[i][j] = 1 if dp[i + 1][j - 1] and s[i] == s[j] else 0
if dp[i][j]:
if j - i + 1 > length:
length = j - i + 1
start = i
return s[start: start + length]- 按照回文串的定义，遍历每个字符作为中点，向两边扩散；
- 官方题解从 DP 的转移方程解释了为什么中心扩散可以得到正确答案（虽然这个结论非常直观），观察状态转移方程，可以看到所有状态在转移时的可能性都是唯一的：
dp[i][j] <- dp[i+1][j-1] <- dp[i+2][j-2] <- ...，也就是说，从每一种边界情况开始「扩展」，都可以得出所有状态对应的答案。
Python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
self.ret = s[0]
# 从 s[l:r] 开始向两侧扩散，开始时，l==r 或者，l+1==r
def process(l, r):
tmp = ''
while l >= 0 and r < n:
if s[l] != s[r]:
break
tmp = s[l: r + 1]
l -= 1
r += 1
if len(tmp) > len(self.ret):
self.ret = tmp
for l in range(n - 1):
process(l, l)
process(l, l + 1)
return self.ret
请实现一个函数用来匹配包含'.'和'*'的正则表达式。- 定义
dp(i, j)表示s[:i]与p[:j]是否匹配； - 难点是要把所有情况考虑全面，尤其是初始化，以及
p[j-1] == '*'的情况；
递归版
class Solution:
def isMatch(self, s: str, p: str) -> bool:
from functools import lru_cache
# 因为本题保证了 p 的合法性，所以可以省略部分边界判断
@lru_cache(maxsize=None)
def dp(i, j):
if i == 0 and j == 0: return True
if j == 0: return False
# 空串的判断，比如 s='', p='a*' 或 'a*b*'
if i == 0: return p[j - 1] == '*' and dp(i, j - 2)
# 情况1：s='abc', p='abc' 或 'ab.'
r1 = (s[i - 1] == p[j - 1] or p[j - 1] == '.') and dp(i - 1, j - 1)
# 情况2：'*'匹配了 0 个字符的情况，比如 s='ab', p='abc*'
r2 = p[j - 1] == '*' and dp(i, j - 2)
# 情况3：'*'匹配了 1 个以上的字符，比如 s='abc', p='abc*' 或 'ab.*'
r3 = p[j - 1] == '*' and (s[i - 1] == p[j - 2] or p[j - 2] == '.') and dp(i - 1, j)
return r1 or r2 or r3
m, n = len(s), len(p)
return dp(m, n)迭代版
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
# 初始化，对应递归中的 base case
# dp[0][0] = True
# for j in range(2, n + 1):
# dp[0][j] = p[j - 1] == '*' and dp[0][j - 2]
# 为了匹配“无缝转换”，把上面的初始化代码也写到了循环里面，两种写法都可以
for i in range(0, m + 1):
for j in range(0, n + 1):
if i == 0 and j == 0: dp[i][j] = True
elif j == 0: continue
elif i == 0: dp[i][j] = p[j - 1] == '*' and dp[0][j - 2]
else:
r1 = (s[i - 1] == p[j - 1] or p[j - 1] == '.') and dp[i - 1][j - 1]
r2 = p[j - 1] == '*' and dp[i][j - 2]
r3 = p[j - 1] == '*' and (s[i - 1] == p[j - 2] or p[j - 2] == '.') and dp[i - 1][j]
dp[i][j] = r1 or r2 or r3
return dp[m][n]
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 首尾双指针遍历
Python
class Solution:
def maxArea(self, height: List[int]) -> int:
""""""
l, r = 0, len(height) - 1
ret = (r - l) * min(height[l], height[r]) # 初始化
while l < r:
if height[l] < height[r]:
l += 1
else:
r -= 1
tmp = (r - l) * min(height[l], height[r])
ret = max(ret, tmp)
return ret
给定一个数组，找出该数组中所有和为 0 的三元组。
详细描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 排序后，问题可以简化成两数之和（LeetCode-167）；
- 先固定一个数，然后利用首尾双指针进行对向遍历；
- 注意跳过相同结果；
Python
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# assert
ret = []
L = len(nums)
if L < 3:
return ret
# 设置目标值
target = 0
# 排序
nums = sorted(nums)
for i in range(L - 2): # 固定第一个数
# 剪枝
if i > 0 and nums[i] == nums[i - 1]: continue
if nums[i] + nums[i + 1] + nums[i + 2] > target: break
if nums[i] + nums[L - 2] + nums[L - 1] < target: continue
# 设置左右指针
l, r = i + 1, L - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < target:
l += 1
elif s > target:
r -= 1
else: # s == target
ret.append([nums[i], nums[l], nums[r]])
# 同时移动双指针
l += 1
r -= 1
# 如果跟上一个值相同，就跳过
while l < r and nums[l] == nums[l - 1]: l += 1
while l < r and nums[r] == nums[r + 1]: r -= 1
return ret
给定一个数组，找出该数组中和最接近指定值的三元组。
详细描述
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 思路跟三数之和基本一致；
- 当找到比当前更接近的结果时更新；
Python
from typing import List
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
""""""
nums = sorted(nums)
L = len(nums)
ret = nums[0] + nums[1] + nums[2] # 初始化，len(nums) >= 3
for i in range(L - 2):
# 跳过重复元素
if i > 0 and nums[i] == nums[i - 1]:
continue
# 利用单调性剪纸
min_s = nums[i] + nums[i + 1] + nums[i + 2] # 最小和
if min_s > target:
if abs(min_s - target) < abs(ret - target):
ret = min_s
break
max_s = nums[i] + nums[L - 2] + nums[L - 1] # 最大和
if max_s < target:
ret = max_s
continue
# 初始化双指针
l, r = i + 1, L - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if abs(s - target) < abs(ret - target):
ret = s
if s < target:
l += 1
while l < r and nums[l] == nums[l - 1]: l += 1
elif s > target:
r -= 1
while l < r and nums[r] == nums[r + 1]: r -= 1
else: # ret == target
return ret
return ret利用单调性剪枝
-
在经过排序后，每轮迭代时，三数之和的最大值和最小值是确定的；
-
所以如果最小值比目标值大，那么后面无论怎么移动双指针，差值都只会越来越大；最大值比目标值小时同理；
-
代码细节：
# 剪枝：利用单调性 min_s = nums[i] + nums[i + 1] + nums[i + 2] # 最小和 if min_s > target: # 如果最小和也大于 target，则剩余部分的差值肯定越来越大 # 容易忽略的一步，注意此时也是有可能出现答案的，比如 ret < 0 < min_s 时 if abs(min_s - target) < abs(ret - target): ret = min_s break max_s = nums[i] + nums[L - 2] + nums[L - 1] # 最大和 if max_s < target: # 如果最大和也小于 target，则剩余部分的差值肯定越来越大 ret = max_s # 此时 ret < max_s < target，所以 max_s 必然比当前 ret 更接近目标值 continue
给定链表，删除链表的倒数第 n 个结点，返回删除后链表的头结点。详细描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0) # 伪头节点
dummy.next = head
k = n + 1 # 获取倒数第 n+1 个节点
lp, fp = dummy, dummy
while fp:
if k <= 0:
lp = lp.next
fp = fp.next
k -= 1
# print(lp.val)
lp.next = lp.next.next
return dummy.next
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。- 利用栈，遇到左括号就压栈，遇到右括号就出栈；
- 无效的情况：栈顶与当前遇到的右括号不匹配，或栈为空；
- 当遍历完所有字符，且栈为空时，即有效；
Python
class Solution:
def isValid(self, s: str) -> bool:
""""""
N = len(s)
# 奇数情况一定无效
if N % 1: return False
# 小技巧，遇到左括号，压入对应的右扩招，这样遇到右括号对比时，直接比较即可
book = {'(': ')', '[': ']', '{': '}'}
stk = []
for c in s:
if c in book:
stk.append(book[c])
else:
# 如果栈为空，或者栈顶不匹配，无效
if not stk or stk[-1] != c:
return False
stk.pop()
return len(stk) == 0
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python：递归
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None): # noqa
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: # noqa
""" 递归 """
if l1 is None: # 尾递归 1
return l2
elif l2 is None: # 尾递归 2
return l1
elif l1.val < l2.val: # 选出头结点较小的一个，余下部分递归
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
Python：迭代
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None): # noqa
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: # noqa
""" 迭代 """
head = ListNode(-1) # 初始化
pre = head
while l1 and l2:
if l1.val < l2.val:
pre.next = l1
l1 = l1.next
else:
pre.next = l2
l2 = l2.next
pre = pre.next
# 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
pre.next = l1 if l1 is not None else l2
return head.next
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。- 每次用 l, r 两个指针框定需要翻转的范围，完成翻转后继续下一组，直到最后一组不足 k 个节点结束；
- 注意节点的拼接；
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 翻转一个子链表
def reverse(l, r):
pre, cur = None, l
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return r, l # 翻转后，头尾交换
dummy = ListNode(0) # 因为头结点可能会变，设置一个伪头结点
dummy.next = head
pre = dummy # pre 定位在 l 的前面
l = head
while l:
r = pre # r 初始化为上一个节点，这样走 k 步后正好划定一个 [l, r] 的闭区间
for _ in range(k):
r = r.next
if not r:
return dummy.next
nxt = r.next
r.next = None # 切断，这里是否切断要看具体的 reverse 是怎么实现的，这里的实现需要切断
l, r = reverse(l, r)
pre.next = l # 重新接入链表
r.next = nxt
# [l, r] 翻转完成后，继续下一组 [l, r]
pre = r # pre 初始化为上一组的 r
l = r.next # l 初始化为上一组 r 的下一个节点
return dummy.next
不使用乘法、除法和 mod 运算符，返回两数相除的整数部分，如 10/3 返回 3。详细描述
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python：二分查找
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
""""""
INT_MIN, INT_MAX = -2 ** 31, 2 ** 31 - 1
# 按照题目要求，只有一种情况会溢出
if dividend == INT_MIN and divisor == -1:
return INT_MAX
sign = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
# 核心操作
def div(a, b):
if a < b:
return 0
cnt = 1
tb = b
while (tb + tb) <= a:
cnt += cnt
tb += tb
return cnt + div(a - tb, b)
ret = div(abs(dividend), abs(divisor))
return ret if sign else -ret核心操作说明，以 60 / 8 为例：
第一轮 div(60, 8): 8 -> 32 时停止，因为 32 + 32 > 60，返回 4
第二轮 div(28, 8): 8 -> 16 时停止，因为 16 + 16 > 28，返回 2
第三轮 div(8, 8): 8 -> 8 时停止，因为 8 + 8 > 8，返回 1
第三轮 div(0, 8): 因为 0 < 8，返回 0
因此结果为 1 + 2 + 4 = 7
在一个旋转过的有序数组中搜索某值，若存在返回下标，否则返回 -1。详细描述
整数数组 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 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。-
“二分”的本质是两段性，而不是单调性；即只要二分后，左边满足某个性质，右边不满足某个性质，即可使用二分；
-
比如本题二分后，有前半段满足 >= nums[0]，而后半段不满足；
Python：二分查找
- 将数组从中间分开成左右两部分时，一定有一部分的数组是有序的。
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
L = len(nums) - 1
l, r = 0, L
while l <= r:
mid = l + (r - l) // 2 # 中点下标
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]: # [0, mid) 是有序的
# 如果目标在[0, mid)，则将搜索范围缩小到 [0,mid-1]，反之 [mid+1,L]
if nums[0] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else: # (mid, L] 是有序的
# 同理，如果目标在(mid, L]，则将搜索范围缩小到 [mid+1,L]，反之 [0,mid-1]
if nums[mid] < target <= nums[L]:
l = mid + 1
else:
r = mid - 1
return -1
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 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 个单位的雨水（蓝色部分表示雨水）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
法1）Python：双指针
class Solution:
def trap(self, height: List[int]) -> int:
""""""
l, r = 0, len(height) - 1
ans = 0
max_l = max_r = 0 # 保存当前位置时，左右最高的柱子
while l <= r:
if height[l] <= height[r]:
if height[l] > max_l:
max_l = height[l]
else:
ans += max_l - height[l]
l += 1
else:
if height[r] > max_r:
max_r = height[r]
else:
ans += max_r - height[r]
r -= 1
return ans法2）C++：左右遍历两次
class Solution {
public:
int trap(vector<int>& H) {
int n = H.size();
vector<int> l_max(H);
vector<int> r_max(H);
for(int i=1; i<n; i++)
l_max[i] = max(l_max[i-1], l_max[i]);
for(int i=n-2; i>=0; i--)
r_max[i] = max(r_max[i+1], r_max[i]);
int ret = 0;
for (int i=1; i<n-1; i++)
ret += min(l_max[i], r_max[i]) - H[i];
return ret;
}
};
给定整数数组 nums ，返回连续子数组的最大和（子数组最少包含一个元素）。详细描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 因为始终只与上一个状态有关，因此可以通过“滚动变量”的方式优化空间
dp = nums[0]
ret = nums[0]
for i in range(1, len(nums)):
dp = max(nums[i], dp + nums[i])
ret = max(ret, dp)
return ret
给定一个非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。详细描述
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if not grid: return 0
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
# 初始化
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j - 1] + grid[0][j]
# print(dp)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
return dp[-1][-1]空间优化：展开循环可以发现，内循环每次遍历实际只会用到上一层的和当前层左边的结果（详见代码）；
Python
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if not grid: return 0
m, n = len(grid), len(grid[0])
dp = [0] * n
# 初始化
dp[0] = grid[0][0]
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j]
# print(dp)
for i in range(1, m):
dp[0] = dp[0] + grid[i][0] # 初始化每一层最左边的结果
for j in range(1, n):
# dp[j - 1] + grid[i][j] 表示从左边移动
# dp[j] + grid[i][j] 表示从上方移动
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
return dp[-1]
规定每次可以爬1级或2级台阶。求爬一个 n 级台阶总共有多少种方法。详细描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
dp1, dp2 = 1, 2
for _ in range(3, n + 1):
dp1, dp2 = dp2, dp1 + dp2
return dp2
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。详细描述
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。-
动态规划经典问题 > 编辑距离 - 力扣官方题解
-
Tips：“插入”和“删除”操作可以认为是同一种操作，因为编辑距离具有对称性，在一方中插入，等价于在另一方删除，这有助于理解代码；
Python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
if m * n == 0: # 其中一个是空串
return m + n
dp = [[0] * (n + 1) for _ in range(m + 1)] # m * n
for i in range(1, m + 1):
dp[i][0] = i
for i in range(1, n + 1):
dp[0][i] = i
for i in range(1, m + 1):
for j in range(1, n + 1):
r1 = dp[i - 1][j] + 1
r2 = dp[i][j - 1] + 1
r3 = dp[i - 1][j - 1]
if word1[i - 1] != word2[j - 1]:
r3 += 1
dp[i][j] = min(r1, r2, r3)
return dp[m][n]优化：利用滚动数组将空间复杂度从 O(MN) 优化到 min(O(N), O(M))
Python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
if m * n == 0: # 其中一个是空串
return m + n
if m < n:
m, n = n, m
word1, word2 = word2, word1
dp_pre = [0] * (n + 1)
for i in range(1, n + 1):
dp_pre[i] = i
for i in range(1, m + 1):
dp_cur = [i] + [0] * n
for j in range(1, n + 1):
r1 = dp_cur[j - 1] + 1
r2 = dp_pre[j] + 1
r3 = dp_pre[j - 1]
if word1[i - 1] != word2[j - 1]:
r3 += 1
dp_cur[j] = min(r1, r2, r3)
dp_pre = dp_cur
return dp_cur[n]
- 快排链表的核心操作；
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 新建两个链表，分别保存小于 x 和大于等于 x 的，最后拼接；
Python3
python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
""""""
# l/r 会进行移动，lo/hi 为头节点
l = lo = ListNode(0)
r = hi = ListNode(0)
while head:
if head.val < x: # 小于 x 的拼到 lo
l.next = head
l = l.next
else: # 大于等于 x 的拼到 hi
r.next = head
r = r.next
head = head.next
# 因为不能保证最后遍历的节点在 hi 中，所以必须加上这一步，切断循坏
r.next = None # 关键步骤
l.next = hi.next
return lo.next
将数字解码成字母，返回可能的解码方法数；
例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)- 定义
dfs(i)表示s[:i]已经固定的情况下，s[i:]的解码方法； - 【递归基】
i=n时，s[:n]都固定了，即表示找到了一种解法方法； - 本题的难点是
dfs(i)不光可以从dfs(i-1)递推，还可以从dfs(i-2)递推；可以看做是有限制的跳台阶问题；
Python
class Solution:
def numDecodings(self, s: str) -> int:
from functools import lru_cache # 记忆化搜索
n = len(s) # 字符长度
@lru_cache(maxsize=None)
def dfs(i): # 表示 s[:i] 已经固定的情况下，s[i:] 的解码方法
if i == n: # s[:n] 都已经固定，即找到了一种有效的解码方法
ret = 1
elif s[i] == '0': # 以 0 开始的字符不存在有效解码
ret = 0
elif s[i] == '1': # 如果以 1 开头，可以尝试两个位置
ret = dfs(i + 1) # 这个 1 已经固定了
if i + 1 < n: # 因为 10 ~ 19 都存在有效解码，因此只要后面存在两个字符，就可以加上 dfs(i + 2)
ret += dfs(i + 2)
elif s[i] == '2': # 如果以 2 开头，可以有条件的尝试两个位置
ret = dfs(i + 1)
if i + 1 < n and '0' <= s[i + 1] <= '6':
ret += dfs(i + 2)
else: # 如果以 3~9 开头，只能尝试一个位置
ret = dfs(i + 1)
return ret
return dfs(0)- 有了递归过程后，就可以脱离原问题，模板化的将其转化为动态规划。
Python
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s) # 字符长度
dp = [0] * (n + 1)
# 初始化（对应递归中的 base case）
# i == n 时 ret = 1，即
dp[n] = 1
# 递推过程：对应递归过程填空
# 下面的写法略有冗余，可以做一些合并，但是为了做到跟递归一一对应，就没有修改
for i in range(n - 1, -1, -1):
# 为什么是倒序遍历，一方面可以从问题理解；
# 另一方面可以从递归过程看，因为最后返回的是 dp[0]，同时 dp[i] 需要从 dp[i + 1] 递推，所以显然需要逆序遍历
if s[i] == '0':
dp[i] = 0 # ret = 0
elif s[i] == '1':
dp[i] = dp[i + 1] # ret = rec(i + 1)
if i + 1 < n:
dp[i] += dp[i + 2] # ret += rec(i + 2)
elif s[i] == '2':
dp[i] = dp[i + 1] # ret = rec(i + 1)
if i + 1 < n and '0' <= s[i + 1] <= '6':
dp[i] += dp[i + 2] # ret += rec(i + 2)
else:
dp[i] = dp[i + 1] # ret = rec(i + 1)
return dp[0] # return rec(0)
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。- 对一个有序数组，无论值是多少，它能构成的方法数都是一样的；
- 对一个长度为
n的有序数组，取第i个值作为根节点，分成左右两个规模分别为l=i-1和r=n-i的子问题；- 则选择该节点作为根节点的方法数
=左子树的方法数*右子树的方法数； - 得递推公式：
dp(n) = sum( dp(i-1) * dp(n-i) )，其中i in [1, n+1)；
- 则选择该节点作为根节点的方法数
- 实际上本题就是一个卡特兰数的实例；
Python：递归写法
class Solution:
def numTrees(self, n: int) -> int:
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(n):
if n in (0, 1): return 1
ret = 0
for i in range(1, n + 1): # 选择第 i 个数字作为根节点
l, r = i - 1, n - i # 此时左右子树的节点个数
ret += dp(l) * dp(r) # 左边 l 个节点的方法数 * 右边 r 个节点的方法数
return ret
return dp(n)Python：迭代写法（略）
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。- 判断二叉搜索树的条件：
- 当前节点的值大于左树的最大值，小于右树的最小值，且左右子树都是二叉搜索树；
Python
# 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 isValidBST(self, root: TreeNode) -> bool:
from dataclasses import dataclass
@dataclass
class Info:
mx: int
mi: int
is_bst: bool
def dfs(x):
if not x: return Info(float('-inf'), float('inf'), True)
l, r = dfs(x.left), dfs(x.right)
mx = max(x.val, r.mx)
mi = min(x.val, l.mi)
is_bst = l.is_bst and r.is_bst and l.mx < x.val < r.mi
return Info(mx, mi, is_bst)
return dfs(root).is_bst
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 递归：当前二叉树的最大深度等于左右子树的最大深度
+ 1
Python
# 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 maxDepth(self, root: TreeNode) -> int:
if not root: # 尾递归
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。- 考虑对以 X 为头结点的树，为了确定其是否为平衡二叉树，需要从左右子树获取哪些信息？
- 根据定义，显然需要知道两个信息：
- 子树是否为平衡二叉树（
is_balanced: bool）； - 子树的高度（
height: int）；
- 子树是否为平衡二叉树（
- 假设子树的这些信息已知，怎么求 X 节点的上述信息：
x_is_balanced = l.is_balanced and r.is_balanced and abs(l.height - r.height) <= 1即左右子树都平衡，且高度差小于等于 1
x_height = max(l.height, r.height) + 1
- 对空节点，有：
is_balanced = True height = 0
Python
# 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 isBalanced(self, root: TreeNode) -> bool:
from collections import namedtuple
# 用一个结构来组织需要的信息，可以直接用 tuple，这里是为了更直观
Info = namedtuple('Info', ['is_balanced', 'height'])
def dfs(x):
if not x: # 空节点
return Info(True, 0)
l, r = dfs(x.left), dfs(x.right)
is_balanced = l.is_balanced and r.is_balanced and abs(l.height - r.height) <= 1
height = max(l.height, r.height) + 1
return Info(is_balanced, height)
return dfs(root).is_balanced # 返回需要的信息
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最小深度 2 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 深度优先搜索，记录过程中的最小深度；
Python：深度优先搜索
# 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 minDepth(self, root: TreeNode) -> int:
""""""
if not root: # 尾递归1
return 0
if not root.left and not root.right: # 尾递归 2 *
return 1
min_depth = 10**5 + 10
if root.left:
min_depth = min(self.minDepth(root.left), min_depth)
if root.right:
min_depth = min(self.minDepth(root.right), min_depth)
return min_depth + 1
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。- 先序遍历，达到叶子节点是进行判断；
- 注意空节点的判断；
Python
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(x, rest):
if not x:
return False
rest -= x.val
if not x.left and not x.right:
return rest == 0
l, r = dfs(x.left, rest), dfs(x.right, rest)
rest += x.val
return l or r
ret = dfs(root, targetSum)
return ret
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。- 先序遍历+回溯；
Python
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
ret = []
tmp = []
def dfs(x, rest):
if not x:
return
rest -= x.val
tmp.append(x.val)
if not x.left and not x.right:
if rest == 0:
ret.append(tmp[:])
dfs(x.left, rest)
dfs(x.right, rest)
rest += x.val
tmp.pop()
dfs(root, targetSum)
return ret
给定一个三角形 triangle ，找出自顶向下的最小路径和。详细描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
输入：triangle = [[-10]]
输出：-10
提示：
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10^4 <= triangle[i][j] <= 10^4
进阶：
你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 思路跟网格版的最小路径和基本相同，就是路线方向略有不同，模拟路线即可；
Python
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if not triangle: return 0
dp = [triangle[0][0]]
for i in range(1, len(triangle)):
dp = [dp[0] + triangle[i][0]] + dp # 加上最左路
for j in range(1, len(triangle[i])):
if j == len(triangle[i]) - 1: # 特殊处理最右路
dp[j] = dp[j] + triangle[i][j]
else: # 因为提前改变了 dp 的长度，所以不能写成 min(dp[j], dp[j - 1])，这里踩了个小坑
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
# print(dp)
return min(dp)
给定数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能进行一次买卖。求最大利润。详细描述
给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。1. 遍历 prices，以 min_p 记录当前的最小值（非全局最小值）；
2. 用当前价格 p 减去 min_p，得到当天卖出的利润；
3. 使用 ret 记录遍历过程中的最大利润。- 以上思路只适用于一次买卖的情况；
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
""""""
ret = 0
min_p = 10001
for p in prices:
min_p = min(p, min_p)
ret = max(ret, p - min_p)
return ret
给定数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。详细描述
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。TODO
Python
- 考虑一共有三种情况：
- 有涨有跌：只有连续两天交易的收益为正，就应该交易；
- 连续上涨：按题意应该在头尾交易一次，但注意到：$p_3-p_1$等价于$(p_3-p_2)+(p_2-p_1)$，换言之，等价于当天买入，次日卖出再买入（实际计算过程不等于交易过程）
- 连续下跌：不交易
- 综上：比较连续两天的价格，只要收益为正，就交易；
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ret = 0
for i in range(1, len(prices)):
dif = prices[i] - prices[i - 1]
if dif > 0:
ret += dif
return ret
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。详细描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1]
输出：0
提示：
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 分别定义前向、后向两个dp，记
dp_f和dp_b，其中：dp_f[i]表示prices[:i]区间内的买卖一次的最大值；dp_b[i]表示prices[i:]区间内的买卖一次的最大值；
- 因为可以只交易一次，所以最终结果为
max(dp_f[-1], max(dp_f[i] + dp_b[i + 1]))
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) < 2: return 0
n = len(prices)
dp_f = [0] * n
dp_b = [0] * n
min_p = prices[0]
for i in range(1, n):
dp_f[i] = max(dp_f[i-1], prices[i] - min_p)
min_p = min(min_p, prices[i])
max_b = 0
max_p = prices[-1]
for i in range(n - 2, -1, -1):
dp_b[i] = max(dp_b[i+1], max_p - prices[i])
max_p = max(max_p, prices[i])
# print(dp_f, dp_b)
return max(dp_f[-1], max(dp_f[i] + dp_b[i + 1] for i in range(0, n - 1)))空间优化：官方提供了一种空间复杂度为 O(1) 的解法：
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
buy1 = buy2 = prices[0]
sell1 = sell2 = 0
for i in range(1, n):
buy1 = min(buy1, prices[i])
sell1 = max(sell1, prices[i] - buy1)
buy2 = min(buy2, prices[i] - sell1)
sell2 = max(sell2, prices[i] - buy2)
return sell2
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。- 考虑对以 X 为头结点的树，为了求得最大路径和，需要从左右子树获取哪些信息？
- 根据要求，显然需要知道：
- 子树能提供的最大和路径，即以子树节点为终点的最大路径，记
h: int；为什么需要这个信息：为了计算经过 X 节点的最大路径，这条路径的特点是：从某一节点出发到达子树节点，经过 X 节点后，再进入另一个子节点的最大和路径；
这是本题除 coding 外最大的难点，能想出这个信息也就基本解决这个问题了；
- 子树中的最大路径和（即子问题）：为了比较得出全局最大路径和，记
s: int；
- 子树能提供的最大和路径，即以子树节点为终点的最大路径，记
- 假设子树的这些信息已知，怎么求 X 节点的上述信息：
x_h = x.val + max(0, l.h, r.h)因为需要经过 X 节点，所以必须加上 x.val，同时如果左右子树提供的 h 小于 0，那么不如舍去；
x_s = max(l.s, r.s, max(l.h, 0) + max(r.h, 0) + x.val)这一步容易写成
x_s = max(l.s, r.s, x_h)或者x_s = max(l.s, r.s, l.h + r.h + x.val)，都是对问题理解不到位；
重申：模板只是帮我们解决怎么组织代码的问题，而写出正确的代码一靠观察，二靠积累；
- 对空节点，有：
h = 0 s = -inf # 因为题目要求至少包含一个节点，如果设为 0，那么当所有节点为负数时，就会出错
Python
# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
from dataclasses import dataclass
@dataclass
class Info:
h: int # 该节点能提供的最大路径（含节点本身）
s: int # 该节点下的最大路径（可能不包含该节点）
# 事实上 Info 里的 s 完全可以用一个全局变量来代替，这里是为了尽量拟合模板；熟练之后就不必这么做了。
def dfs(x):
if not x:
# 对空节点，初始化 h=0, s=负无穷
return Info(0, float('-inf'))
l, r = dfs(x.left), dfs(x.right)
x_h = x.val + max(0, l.h, r.h)
x_s = max(l.s, r.s, max(l.h, 0) + max(r.h, 0) + x.val)
return Info(x_h, x_s)
return dfs(root).s
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。- 先序遍历，每到一个叶节点，add 一次；
- 注意空节点的处理；
Python
# 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 sumNumbers(self, root: TreeNode) -> int:
self.ret = 0
def dfs(x, tmp):
if not x:
return
tmp = tmp * 10 + x.val
if not x.left and not x.right:
self.ret += tmp
return
dfs(x.left, tmp)
dfs(x.right, tmp)
dfs(root, 0)
return self.ret
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。详细描述
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]
示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
提示：
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 先找到中间节点 mid；
- 将链表 mid 反转；
- 然后合并 head 和 mid；
Python：写法1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
def get_mid(p):
lp, fp = p, p
while fp and fp.next:
lp = lp.next
fp = fp.next.next
return lp
def reverse(p):
cur, pre = p, None
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
mid = get_mid(head) # 注意此时还没有断开两个链表
mid = reverse(mid)
# merge
l, r = head, mid
while True:
l_nxt, r_nxt = l.next, r.next
if not r_nxt: # 这是一种写法，另一种写法是在获得 mid 后将 mid 与原链表断开（后移一个节点，结果也是正确的，见写法2）
break
l.next, r.next = r, l_nxt
l, r = l_nxt, r_nxtPython：写法2
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
def get_mid(p):
lp, fp = p, p
while fp and fp.next:
lp = lp.next
fp = fp.next.next
return lp
def reverse(p):
cur, pre = p, None
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
mid = get_mid(head)
mid.next, mid = None, mid.next # 写法2）提前断开 mid
# mid, mid.next = mid.next, None # err
mid = reverse(mid)
# merge
l, r = head, mid
while r:
l_nxt, r_nxt = l.next, r.next
# if not r_nxt:
# break
l.next, r.next = r, l_nxt
l, r = l_nxt, r_nxt
给定整型数组，求乘积最大的非空连续子数组，返回乘积；详细描述
给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 延续连续子数组最大和的思路，定义
dp[i]表示以nums[i]结尾的连续最大乘积； - 区别在于非0值乘以负数时，最大值会变最小值，最小值变最大值；
- 因此可以考虑定义两个 dp：
dp_max[i]和dp_min[i]分别表示最大和最小乘积（详见代码）； - 本题同样可以使用“滚动变量”的方式降低空间复杂度；
Python
class Solution:
def maxProduct(self, nums: List[int]) -> int:
ret = dp_max = dp_min = nums[0]
for x in nums[1:]:
tmp_mx = dp_max # 临时变量
dp_max = max(x, dp_max * x, dp_min * x)
dp_min = min(x, dp_min * x, tmp_mx * x)
ret = max(ret, dp_max)
return ret
找出一个非递减数组中和等于 target 的两个数字，输出它们的下标。
假定题目一定有一个解。详细描述
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
提示：
2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python：双指针
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
""""""
lo, hi = 0, len(numbers) - 1
while lo < hi:
tmp = numbers[lo] + numbers[hi]
if tmp < target:
lo += 1
elif tmp > target:
hi -= 1
else:
return [lo + 1, hi + 1]
找出由 ATCG 构成的字符串中所有重复且长度为 10 的子串；详细描述
所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
提示：
0 <= s.length <= 10^5
s[i] 为 'A'、'C'、'G' 或 'T'
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-dna-sequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 基本思路：哈希表计数；
- 如果直接使用子串本身作为哈希表的 key，那么时间复杂度和空间复杂度都是
O(NL)；而如果使用位运算+滑动窗口手动构造 key，可以把复杂度降为O(N)；
子串作为 key
- 时间&空间复杂度：
O(NL)；
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
""""""
# from collections import defaultdict
L = 10
cnt = defaultdict(int)
ans = []
for i in range(len(s) - L + 1):
subs = s[i: i+L]
cnt[subs] += 1
if cnt[subs] == 2:
ans.append(subs)
return ans位运算+滑动窗口
- 时间&空间复杂度：
O(N)；
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
""""""
# from collections import defaultdict
L = 10
B = {'A': 0, 'T': 1, 'C': 2, 'G': 3} # 分别为 00, 01, 10, 11
if len(s) < L + 1: # assert，否则部分用例会无法通过
return []
# 先计算前 9 位的值
x = 0
for i in range(L - 1):
b = B[s[i]]
x = (x << 2) | b
ans = []
cnt = defaultdict(int)
for i in range(len(s) - L + 1):
b = B[s[i + L - 1]]
# 注意该有的括号不要少，避免运算优先级混乱
x = ((x << 2) | b) & ((1 << (L * 2)) - 1) # 滑动计算子串的 hash 值
cnt[x] += 1
if cnt[x] == 2:
ans.append(s[i: i + L])
return ans位运算说明
(x << 2) | b：# 以为均为二进制表示 设 x = 0010 1011, b = 10: 该运算相当于把 b “拼” 到 x 末尾 x : 0010 1011 x = x << 2: 1010 1100 x = x | b : 1010 1100 | 0000 0010 ----------- 1010 1110
x & ((1 << (L * 2)) - 1)# 该运算把 x 除低 10 位前的所有位置置 0 设 L = 5，x = 1110 1010 1010: y = 1 << (L * 2): 0100 0000 0000 y = y - 1 : 0011 1111 1111 x = x & y : 1110 1010 1010 & 0011 1111 1111 ---------------- 0010 1010 1010
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。- 定义
dfs(i)表示前i家能打劫的最大价值； - 【递归基】
i <= 0时，有dfs(0) = 0；小细节：因为会用到
i-2的状态，所以需要定义i < 0时的状态； - 递推公式：
dfs(i) = max(dfs(i-1), dfs(i-2) + nums[i-1])；对第
i家（nums[i-1]），有两种可能，不抢（dfs(i-1)），抢（dfs(i-2) + nums[i-1]），去其中的较大值；
Python：递归
class Solution:
def rob(self, nums: List[int]) -> int:
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(i):
if i == 0: # 显然
return 0
if i == 1: # 只有一家时，必抢
return nums[0]
r1 = dfs(i - 1) # 不抢
r2 = dfs(i - 2) + nums[i - 1] # 抢
return max(r1, r2)
N = len(nums)
return dfs(N)Python：动态规划
class Solution:
def rob(self, nums: List[int]) -> int:
N = len(nums)
dp = [0] * (N + 1)
dp[1] = nums[0]
for i in range(2, N + 1):
r1 = dp[i - 1] # 不抢
r2 = dp[i - 2] + nums[i - 1] # 抢
dp[i] = max(r1, r2)
return dp[-1]
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。- 与打家劫舍的唯一区别就是不能同时偷首尾两家；
- 因此可以考虑分别计算
nums[1:]和nums[:-1]，求较大值；
Python
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1: return nums[0]
def f(nums):
N = len(nums)
dp = [0] * (N + 1)
dp[1] = nums[0]
for i in range(2, N + 1):
dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
return dp[-1]
return max(f(nums[1:]), f(nums[:-1]))
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。
该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。详细描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
法1）Python：二分查找
- 时间复杂度：
O(MlogN)
from bisect import bisect_left
# 直接层序二分搜索
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
idx = bisect_left(row, target) # 注意这里要用 bisect_left
if idx < len(row) and row[idx] == target:
return True
return False
# 稍微做一些优化
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
if target < matrix[0][0] or target > matrix[m - 1][n - 1]:
return False
lo, hi = 0, n
for row in matrix:
idx = bisect_left(row, target, lo, hi)
# 逐步缩小每层遍历的范围
if idx < len(row):
if row[idx] == target:
return True
elif row[idx] < target:
lo = idx
elif row[idx] > target:
hi = idx
return False法2）Python：模拟二分
- 二分搜索的核心是将搜索区域分成两个部分，且这两个部分具有相反的性质，每次可以排除一半左右搜索区域；
- 对本题来说，如果从右上角开始遍历，则有：所有左边的值都比当前值小，所有下方的值都比当前值大；
- 时间复杂度：
O(M+N)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
i, j = 0, n - 1
while i < m and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target: # 比当前值大，横向往左进一格
j -= 1
else: # matrix[i][j] < target 比当前值小，纵向往下进一格
i += 1
return False
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。- 先序遍历，特殊处理叶子节点；
Python
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
ret = []
tmp = []
def dfs(x):
if not x: return
tmp.append(str(x.val))
if not x.left and not x.right:
ret.append('->'.join(tmp))
dfs(x.left)
dfs(x.right)
tmp.pop()
dfs(root)
return ret
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。- 定义
dfs(i, j)表示用1~i的完全平方数凑出j需要的最小数量； - 不能 AC，仅离线验证了正确性；
Python：递归
class Solution:
def numSquares(self, n: int) -> int:
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(i, j):
if i == 0 and j == 0: return 0 # 显然
if i == 0: return float('inf') # 凑不出的情况，返回不可能，注意此时 j != 0
# if i == 1: return j
ret = j # 最大值为 j，因为任意数字最差都可以用 1 组成
times = 0 # i 使用的次数，0 次也考虑在内
while (x := (i ** 2) * times) <= j:
ret = min(ret, dfs(i - 1, j - x) + times)
times += 1
return ret
N = int(n ** 0.5) # 可以使用数字的范围
return dfs(N, n)Python：动态规划（从递归修改而来）
class Solution:
def numSquares(self, n: int) -> int:
from functools import lru_cache
N = int(n ** 0.5)
dp = [[0] * (n + 1) for _ in range(N + 1)]
dp[0] = [float('inf')] * (n + 1)
dp[0][0] = 0
for i in range(1, N + 1):
for j in range(1, n + 1):
dp[i][j] = j
times = 0
while (x := i * i * times) <= j:
dp[i][j] = min(dp[i][j], dp[i - 1][j - x] + times)
times += 1
return dp[-1][-1]- 定义
dfs(j)表示目标和为j时需要完全平方数的最少个数；这里隐含了完全平方数的范围
i*i <= j； - 【递归基】
j == 0时，返回0；
Python：递归
class Solution:
def numSquares(self, n: int) -> int:
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(j):
if j == 0: return 0
# 这里设置初始化为一个上界
# 本题中初始化为无穷大、j（全部 1）、4（四平方和定理）都可以；
# 为了使解法更通用，故初始化为无穷大
ret = float('inf')
i = 1
while (x := i * i) <= j:
ret = min(ret, dfs(j - x) + 1)
i += 1
return ret
return dfs(n)Python：动态规划（从递归修改而来）
class Solution:
def numSquares(self, n: int) -> int:
dp = [i for i in range(n + 1)]
dp[0] = 0
for j in range(1, n + 1):
i = 1
while (x := i * i) <= n:
dp[j] = min(dp[j], dp[j - x] + 1)
i += 1
return dp[-1]Python：动态规划（更快的写法）
- 交换内外层遍历顺序（本题无影响），减小
j的遍历范围；关于遍历“物品”和“容量”的顺序影响，见：零钱兑换 - 代码随想录
class Solution:
def numSquares(self, n: int) -> int:
dp = [i for i in range(n + 1)]
dp[0] = 0
i = 1
while (x := i * i) <= n:
for j in range(x, n + 1):
dp[j] = min(dp[j], dp[j - x] + 1)
i += 1
return dp[-1]- 数学（时间复杂度
$O(\sqrt{n})$ ）：完全平方数 - 力扣官方题解四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和；
- BFS：完全平方数 - 自来火
给定整数数组 nums，返回最长严格递增子序列的长度；
进阶：
你可以设计时间复杂度为 O(N^2) 的解决方案吗？
你能把时间复杂度降到 O(NlogN) 吗?详细描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度；
不能将
dp[i]定义nums[:i]子数组中的最长递增子序列长度，虽然这样定义很直观，但它不满足最优子结构的条件，简单来说，就是你无法通过dp[i-1]得到dp[i]。
Python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
ret = 1
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]: # 如果要求非严格递增，将 '>' 改为 '>=' 即可
dp[i] = max(dp[i], dp[j] + 1)
ret = max(ret, dp[i])
return ret- 考虑新的状态定义：
dp[i]表示长度为i + 1的最长递增子序列末尾的最小值；dp序列一定时单调递增的，可用反证法证明，详见：最长递增子序列（动态规划 + 二分查找，清晰图解） - Krahets该怎么想出这个定义？——多看多做
- 是否满足最优子结构？
- 即已知
dp[i - 1]能否递推得到dp[i]；显然是可以的，当nums[i] > dp[i - 1]时，长度+1，否则，长度不变；
- 即已知
- 如何更新
dp？- 当
nums[i] > dp[i - 1]时，直接添加到末尾； - 否则，要看是否需要更新
dp。根据dp递增的性质，找到nums[i]在dp中应该插入的位置，记idx；比较dp[idx]与nums[i]的大小，如果dp[idx] > nums[i]根据定义，更新dp[idx] = nums[i]；
- 当
从“贪心”角度来解释以上过程：如果我们要使上升子序列尽可能的长，则应该让序列上升得尽可能慢，即每次在上升子序列最后加上的那个数尽可能的小。
Python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
# from bisect import bisect_left
# 手写二分查找
def bisect_left(ls, x):
l, r = 0, len(ls)
while l < r:
m = (l + r) // 2
if ls[m] < x: # 注意这里要 <，如果是 <= 就是 bisect_right 了，不满足题意
l = m + 1
else:
r = m
return l
dp = [nums[0]] # dp[i] 表示长度为 (i+1) 的 LIS 的最后一个元素的最小值
for x in nums[1:]:
if x > dp[-1]:
dp.append(x)
else:
idx = bisect_left(dp, x) # 不能使用 bisect/bisect_right
# if dp[idx] > x:
# dp[idx] = x
dp[idx] = x # 因为 bisect_left 返回的定义就是 dp[idx] <= x，所以可以直接赋值
return len(dp)
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。- 定义
dfs(a)表示凑成金额a需要的最少硬币数； - 递归基：1）显然
dfs(0) = 0；2）当a小于币值时，返回无穷大，表示无效结果；
Python：递归
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
from functools import lru_cache
N = len(coins)
@lru_cache(maxsize=None)
def dfs(a):
if a == 0: return 0
if a < 0: return float('inf')
ret = float('inf')
for i in range(N):
if a >= coins[i]:
ret = min(ret, dfs(a - coins[i]) + 1)
return ret
ret = dfs(amount)
return -1 if ret == float('inf') else retPython：动态规划 写法1）根据递归过程改写
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
N = len(coins)
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for i in range(N):
if a >= coins[i]:
dp[a] = min(dp[a], dp[a - coins[i]] + 1)
return -1 if dp[-1] == float('inf') else dp[-1]Python：动态规划 写法2）先遍历“物品”，在遍历“容量”
关于先后遍历两者的区别见完全背包 - 代码随想录，本题中没有区别；
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
N = len(coins)
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(N):
for a in range(coins[i], amount + 1):
dp[a] = min(dp[a], dp[a - coins[i]] + 1)
return -1 if dp[-1] == float('inf') else dp[-1]
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。- 树形 DP 问题，就是否抢劫当前节点分两种情况讨论，详见代码；
Python
# 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 rob(self, root: TreeNode) -> int:
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(x):
# 空节点
if not x: return 0
# 叶节点
if not x.left and not x.right: return x.val
# 不抢当前节点
r1 = dfs(x.left) + dfs(x.right)
# 抢当前节点
r2 = x.val
if x.left:
r2 += dfs(x.left.left) + dfs(x.left.right)
if x.right:
r2 += dfs(x.right.left) + dfs(x.right.right)
return max(r1, r2)
return dfs(root)
给定一个正整数 n，将其拆分为至少两个正整数的和，使这些整数的乘积最大化。返回最大乘积。详细描述
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 在不使用任何数学结论的前提下，可以把本题当做纯 DP 来做：
Python（写法1）
LeetCode 官方题解中的写法：整数拆分
class Solution:
def integerBreak(self, n: int) -> int:
dp = [1] * (n + 1)
for i in range(2, n + 1):
for j in range(1, i):
# 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>=1）
# j * (i - j) 表示将 i 拆分成 j 和 i-j，且 i-j 不再拆分
# j * dp[i - j] 表示将 i 拆分成 j 和 i-j，且 i-j 会继续拆分，dp[i-j] 即为继续拆分的最优结果（最优子结构）
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
return dp[n]Python（写法2）
《剑指Offer》中的写法
class Solution:
def cuttingRope(self, n: int) -> int:
# 对于 n = 2、3 的情况，直接硬编码
if n == 2:
return 1
if n == 3:
return 2
# 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>3）
# 当 i <= 3 时，不满足该定义，此时不拆效率最高
# 初始状态（dp[0] 仅用于占位）
dp = [0,1,2,3] + [0] * (n - 3)
for i in range(4, n + 1):
for j in range(2, i):
dp[i] = max(dp[i], dp[i-j] * dp[j])
return dp[n]-
数学上可证：尽可能按长度为 3 切，如果剩余 4，则按 2、2 切；
-
简述：当
x >= 4时，有2(x-2) = 2x - 4 >= x；简言之，对任意大于等于 4 的因子，都可以拆成 2 和 x-2 而不损失性能；因此只需考虑拆成 2 或 3 两种情况（1除外）；而由于2*2 > 3*1和3*3 > 2*2*2，可知最多使用两个 2；
Python
class Solution:
def cuttingRope(self, n: int) -> int:
import math
if n <= 3:
return n - 1
a, b = n // 3, n % 3
if b == 1:
return int(math.pow(3, a - 1) * 4)
elif b == 2:
return int(math.pow(3, a) * 2)
else:
return int(math.pow(3, a))
给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。
实现 SummaryRanges 类：
SummaryRanges() 使用一个空数据流初始化对象。
void addNum(int val) 向数据流中加入整数 val 。
int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。
进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。“进阶”：在插入过程中完成合并操作；
示例
输入：
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
输出：
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
解释：
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1); // arr = [1]
summaryRanges.getIntervals(); // 返回 [[1, 1]]
summaryRanges.addNum(3); // arr = [1, 3]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
summaryRanges.addNum(7); // arr = [1, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2); // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
提示：
0 <= val <= 10^4
最多调用 addNum 和 getIntervals 方法 3 * 10^4 次
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。法1）Python：暴力求解
- 每次
getIntervals时，先对数组排序，然后依次找出每个不相交的区间；
class SummaryRanges:
def __init__(self):
self.ls = []
def addNum(self, val: int) -> None:
""""""
self.ls.append(val)
def getIntervals(self) -> List[List[int]]:
""""""
ls = sorted(self.ls)
ret = []
l = ls[0]
for i in range(1, len(ls)):
if ls[i] - ls[i-1] > 1: # 判断是否需要合并
ret.append([l, ls[i-1]])
l = ls[i]
ret.append([l, ls[-1]])
return ret法2）Python：模拟，分情况讨论
-
明确每次
addNum时，区间会发生那些变化：- 情况1：存在一个区间
[l, r]满足l <= val <= r； - 情况2：存在一个区间
[l, r]满足r + 1 == val； - 情况3：存在一个区间
[l, r]满足l - 1 == val； - 情况4：存在两个个区间
[l0, r0]和[l1, r1]满足r0 + 1 == val == l1 - 1，即加入 val 后，会合并为一个区间[l0, r1] - 情况5：以上均不满足，加入后 val 单独成为一个区间；
- 情况1：存在一个区间
-
这里使用了
SortedDict降低了代码难度，也可以使用一个有序数组来模拟； -
时间复杂度:
addNum O(NlgN)、getIntervals O(N)； -
空间复杂度:
O(N)；
from sortedcontainers import SortedDict
from bisect import bisect_right, bisect_left
class SummaryRanges:
def __init__(self):
self.ret = SortedDict() # {l: r}
# 加入首尾两个哨兵，防止区间不存在的情况，这样会徒增很多判断
self.ret[-10] = -10
self.ret[10010] = 10010
def addNum(self, val: int) -> None:
ret = self.ret
L = list(self.ret.keys())
R = list(self.ret.values())
# 二分找出 val 的相邻区间
idx = bisect_left(L, val) # idx = ret.bisect_left(val)
pre = L[idx - 1], R[idx - 1]
nxt = L[idx], R[idx]
if pre[0] <= val <= pre[1] or nxt[0] <= val <= nxt[1]: # 情况1
pass
elif pre[1] + 1 == val == nxt[0] - 1: # 情况4
ret.pop(nxt[0])
ret[pre[0]] = nxt[1]
elif pre[1] + 1 == val: # 情况2
ret[pre[0]] = val
elif nxt[0] - 1 == val: # 情况3
ret.pop(nxt[0])
ret[val] = nxt[1]
else: # 情况5
ret[val] = val
def getIntervals(self) -> List[List[int]]:
return list(self.ret.items())[1:-1] # 去除两个哨兵- 上面的代码中用到了
SortedDict，示例：
>>> d = SortedDict()
>>> d[3] = 33
>>> d[2] = 22
>>> d[4] = 44
>>> d[6] = 66
>>> d[7] = 77
>>> d
SortedDict({2: 22, 3: 33, 4: 44, 6: 66, 7: 77})
>>> d.bisect_left(4) # 二分查找返回的是插入位置
2
>>> d.bisect_right(4) # left 和 right 的区别是如果插入值已存在，则 left 会插到前面，right 会插到后面
3
统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
请注意，你可以假定字符串里不包括任何不可打印的字符。
示例:
输入: "Hello, my name is John"
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-segments-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python3
class Solution:
def countSegments(self, s):
# 针对第一个字符初始化，注意处理空串
ans = 0 if s == '' or s[0] == ' ' else 1
for i in range(1, len(s)):
if s[i] != ' ' and s[i - 1] == ' ':
ans += 1
return ans
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。- 先序遍历每个节点，每个节点再先序遍历找目标值；
Python
# 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 pathSum(self, root: TreeNode, targetSum: int) -> int: # noqa
""""""
if root is None:
return 0
def dfs(x, rest):
if not x:
return 0
ans = 0 if x.val != rest else 1 # 如果相等说明，从头结点开始到该节点可以形成一条路径
# 继续遍历左右子树
rest -= x.val
ans += dfs(x.left, rest)
ans += dfs(x.right, rest)
rest += x.val # 回溯
return ans
# dfs 是一个先序遍历
ret = dfs(root, targetSum)
# pathSum 本身也是一个先序遍历，相当于对每个点都做一次 dfs
ret += self.pathSum(root.left, targetSum)
ret += self.pathSum(root.right, targetSum)
return retPython
# 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 pathSum(self, root: TreeNode, targetSum: int) -> int:
from collections import defaultdict
self.prefix = defaultdict(int) # 保存前缀和
self.prefix[0] = 1
self.targetSum = targetSum
def dfs(x, preSum):
if not x: return 0
ret = 0
preSum += x.val
ret += self.prefix[preSum - targetSum]
self.prefix[preSum] += 1
ret += dfs(x.left, preSum)
ret += dfs(x.right, preSum)
self.prefix[preSum] -= 1
return ret
return dfs(root, 0)Python
# 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 pathSum(self, root: TreeNode, targetSum: int) -> int:
from collections import defaultdict
self.prefix = defaultdict(int) # 保存前缀和
self.prefix[0] = 1
self.targetSum = targetSum
def dfs(x, preSum):
if not x: return 0
ret = 0
preSum += x.val
ret += self.prefix[preSum - targetSum]
self.prefix[preSum] += 1
ret += dfs(x.left, preSum)
ret += dfs(x.right, preSum)
self.prefix[preSum] -= 1
return ret
return dfs(root, 0)
你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。
示例 1：
输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。
提示：
1 <= n <= 2^31 - 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arranging-coins
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
法1）Python：二分查找
- 因为时间复杂度为
O(logN)，所以直接在[1, n]的范围里找即可
class Solution:
def arrangeCoins(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = (left + right + 1) // 2
if mid * (mid + 1) <= 2 * n:
left = mid
else:
right = mid - 1
return left法2）Python：数学公式
- 解方程
$(1+x)*x/2 = n$ ； - 去掉小于 0 的解，保留：$x=(-1+\sqrt{8n+1})/2$
class Solution:
def arrangeCoins(self, n: int) -> int:
return int((-1 + (8 * n + 1) ** 0.5) / 2)
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。- 定义
dfs(i, rest_z, rest_o)表示剩余容量为rest_z,rest_o情况下，前i个元素的最大子集长度（子问题）； - 【递归基】显然
i=0时，返回0； - 然后分是否加入当前元素，返回其中的最大值；
- 记得预处理所有字符串；
Python
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
from functools import lru_cache
def get_zo(s):
z, o = 0, 0
for c in s:
if c == '0': z += 1
else: o += 1
return z, o
# 预处理
tb = dict()
for s in strs:
tb[s] = get_zo(s)
@lru_cache(maxsize=None)
def dfs(i, rest_z, rest_o): # 剩余容量为 rest_z, rest_o 情况下，strs[:i] 下的最大子集长度
if i == 0:
return 0
c1 = dfs(i - 1, rest_z, rest_o) # 不要
c2 = 0
z, o = tb[strs[i - 1]]
if rest_z >= z and rest_o >= o: # 要
c2 = dfs(i - 1, rest_z - z, rest_o - o) + 1
return max(c1, c2)
N = len(strs)
return dfs(N, m, n)优化：通过递归转动态规划
实际上，记忆化搜索的速度要更快；
Python
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
from functools import lru_cache
def get_zo(s):
z, o = 0, 0
for c in s:
if c == '0': z += 1
else: o += 1
return z, o
N = len(strs)
# 预处理
tb = dict()
for s in strs:
tb[s] = get_zo(s)
# dp[N][m][n]
dp = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
for rest_z in range(m + 1):
for rest_o in range(n + 1):
c1 = dp[i - 1][rest_z][rest_o]
c2 = 0
z, o = tb[strs[i - 1]]
if rest_z >= z and rest_o >= o:
c2 = dp[i - 1][rest_z - z][rest_o - o] + 1
dp[i][rest_z][rest_o] = max(c1, c2)
return dp[N][m][n]空间优化（略）
找出 nums1 中每个元素在 nums2 中的下一个比其大的值，不存在输出 -1；
其中 nums1 是 nums2 的子集。
本题实际上就是模拟了**单调栈**最常见的使用场景；详细描述
给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中 nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-element-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Python：单调栈
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = {} # 保存结果
stack = [] # 模拟单调栈
for num in reversed(nums2): # 逆序遍历
while stack and num >= stack[-1]: # 当栈不为空，且当前值大于栈顶值时
stack.pop() # 弹出栈顶值（list.pop 默认弹出最后一个值）
res[num] = stack[-1] if stack else -1 # 如果此时栈不为空，那么栈顶值就是下一个比当前大的值
stack.append(num) # 把当前值入栈
return [res[num] for num in nums1] # 遍历完 nums2 中的所有元素后，就得到了 nums1 中每个元素下一个比它大的值，因为 num1 是 nums2 的子集
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 - 定义
dfs(a, i)表示目标钱数为a且从第i种硬币开始取能得到的组合数；“从第
i种硬币开始取”具体指第i种之后的硬币可以任意取，前面的i-1种不能取，详见代码； - 递归基
- 规定
dfs(0,i) == 1； - 隐含中止条件：当
coins[i] > j时，dfs(a,i) == 0；
- 规定
Python
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
from functools import lru_cache
N = len(coins)
@lru_cache(maxsize=None)
def dfs(a, i): # 目标钱数为 `a` 且从第 `i` 种硬币开始取能得到的组合数
if a == 0: return 1
ret = 0
while i < N:
if (x := coins[i]) <= a:
ret += dfs(a - x, i)
i += 1
return ret
return dfs(amount, 0)- 定义
dp[a]表示构成目标值i的组合数； - 转移方程
dp[a] += dp[a - coins[i]]，当a >= coins[i]时； - 初始状态
dp[0] = 1； - 关键点：先遍历“物品”（这里是硬币），在遍历“容量”（这里是金额）；
关于先后遍历两者的区别见完全背包 - 代码随想录；
Python：动态规划
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
from functools import lru_cache
N = len(coins)
dp = [0] * (amount + 1)
dp[0] = 1
for i in range(N):
x = coins[i]
for j in range(x, amount + 1):
dp[j] += dp[j - x]
return dp[amount]
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
详细描述
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-triangle-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 排序 + 首尾双指针；
- 相当于计算两数之和大于目标值的个数；
Python
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
""""""
nums = sorted(nums)
cnt = 0
for i in range(2, len(nums)): # 注意：循环区间
lo, hi = 0, i - 1
while lo < hi:
s = A[lo] + A[hi]
if s > A[i]:
cnt += hi - lo # 范围剪枝
hi -= 1
else:
lo += 1
return cnt
给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false。
例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。详细描述
给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。
示例 1：
输入：s = "ab", goal = "ba"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。
示例 2：
输入：s = "ab", goal = "ab"
输出：false
解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。
示例 3：
输入：s = "aa", goal = "aa"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。
示例 4：
输入：s = "aaaaaaabc", goal = "aaaaaaacb"
输出：true
提示：
1 <= s.length, goal.length <= 2 * 10^4
s 和 goal 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/buddy-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。-
当
len(s) != len(goal)时：False -
当
len(s) == len(goal)时：- 当
s != goal时：当且仅当不同的字符数量等于 2，且交换后满足条件； - 当
s == goal时：s中存在出现至少 2 次的字符；
- 当
-
s == goal的情况比较容易被忽略；
Python：模拟
class Solution:
def buddyStrings(self, s: str, goal: str) -> bool:
""""""
if len(s) != len(goal):
return False
dif = []
cs = set()
for i, c in enumerate(s):
cs.add(c)
if s[i] != goal[i]:
dif.append(i)
# 存在字符出现过 2 次
if s == goal and len(cs) < len(s):
return True
# 只存在两个位置字符不同，且交换后满足条件
if len(dif) == 2 and (s[dif[0]], s[dif[1]]) == (goal[dif[1]], goal[dif[0]]):
return True
return False
给定非空链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。详细描述
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
lp, fp = head, head
while fp and fp.next:
fp = fp.next.next
lp = lp.next
return lp
给定整数数组 nums，将其划分为 left 和 right 两部分，要求：
1. left 中的每个元素都小于或等于 right 中的每个元素；
2. left 的长度要尽可能小。
返回 left 的长度，题目保证 left 和 right 都非空；
要求：
时间复杂度 O(n)
空间复杂度 O(n) 或 O(1)- 记
lmax[i]表示nums[:i]中的最大值，rmin[i]表示nums[i:]中的最小值； - 返回使
lmax[i - 1] <= rmin[i]的最小i；这里要
<=，否则意味着所有相同的最小值会被分到 left，不符合题意；
Python
class Solution:
def partitionDisjoint(self, nums: List[int]) -> int:
n = len(nums)
# 计算 lmax
lmax = [float('-inf')] * n
lmax[0] = nums[0]
for i in range(1, n):
lmax[i] = max(lmax[i - 1], nums[i])
# 计算 rmin
rmin = [float('inf')] * n
for i in range(n - 2, -1, -1):
rmin[i] = min(rmin[i + 1], nums[i])
for i in range(1, n):
if lmax[i - 1] <= rmin[i]: # 注意这里要 <=；如果是 <，意味着所有相同的最小值会分到 left，不符合题意
return i
return -1优化：计算 lmax 和比较的过程都是顺序遍历，可以合并到一起，节省部分空间；
Python：优化1
class Solution:
def partitionDisjoint(self, nums: List[int]) -> int:
n = len(nums)
rmin = [float('inf')] * n
for i in range(n - 2, -1, -1):
rmin[i] = min(rmin[i + 1], nums[i])
# 合并计算 lmax 和比较过程
lmax = nums[0]
for i in range(1, n):
if lmax <= rmin[i]:
return i
lmax = max(lmax, nums[i])
return -1时间复杂度
O(n)，空间复杂度O(1)
- 使用
lmax记录已划分 left 中的最大值；- 根据题意，left 的中至少会存在一个元素，因此可以初始化
lmax=nums[0]；
- 根据题意，left 的中至少会存在一个元素，因此可以初始化
- 使用
amax记录遍历过程中的最大值； - 当
nums[i] < lmax时，说明需要扩充 left，即需要把i之前的所有元素都添加到 left；同时更新lmax=amax；
以 nums=[3,4,1,5,6] 为例，下面是：
初始化：
amax = 3
lmax = 3
ret = 1
for i in range(1, len(nums)):
i amax lmax ret
1 3 3 1
2 4 3 1
3 5 4 3
4 6 4 3
返回：
ret = 3
Python
class Solution:
def partitionDisjoint(self, nums: List[int]) -> int:
lmax = amax = nums[0]
ret = 1
for i in range(1, len(nums)):
amax = max(amax, nums[i])
if nums[i] < lmax:
ret = i + 1
lmax = amax
return ret
给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。- 判断完全二叉树的条件：
- 左右子树都是满二叉树，且高度相同（满二叉树）；
- 左右子树都是满二叉树，且左子树的高度+1；
- 左子树是满二叉树，右子树是完全二叉树，且高度相同；
- 左子树是完全二叉树，右子树是满二叉树，且左子树的高度+1；
- 综上：
- 我们需要存储信息有：高度、是否满二叉树、是否完全二叉树；
- 对空节点，初始化为：0、是、是；
Python：后序遍历
# 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 isCompleteTree(self, root: TreeNode) -> bool:
from dataclasses import dataclass
@dataclass
class Info:
height: int # 树的高度
is_full: bool # 是否满二叉树
is_cbt: bool # 是否完全二叉树
def dfs(x):
if not x: return Info(0, True, True)
l, r = dfs(x.left), dfs(x.right)
# 利用左右子树的info 构建当前节点的info
height = max(l.height, r.height) + 1
is_full = l.is_full and r.is_full and l.height == r.height
is_cbt = is_full \
or l.is_full and r.is_full and l.height - 1 == r.height \
or l.is_full and r.is_cbt and l.height == r.height \
or l.is_cbt and r.is_full and l.height - 1 == r.height
return Info(height, is_full, is_cbt)
return dfs(root).is_cbt- 给每个节点标号，如果是完全二叉树，存在以下性质：
- 记根节点
id为1； - 若父节点的
id为i，则其左右子节点分别为2*i和2*i + 1； - 如果是完全二叉树则有最大的
id == n，其中n为总节点数；
- 记根节点
Python 写法1：DFS：前序+后序遍历
class Solution:
def isCompleteTree(self, root: TreeNode) -> bool:
from dataclasses import dataclass
@dataclass
class Info:
n: int # 总节点数
mx_id: int # 最大 id
is_cbt: bool # 是否完全二叉树
def dfs(x, i):
if not x: return Info(0, float('-inf'), True)
# 前序遍历向下传递 id
l, r = dfs(x.left, i * 2), dfs(x.right, i * 2 + 1)
# 后序遍历计算是否完全二叉树
n = l.n + r.n + 1
mx_id = max(i, l.mx_id, r.mx_id)
is_cbt = n == mx_id # and l.is_cbt and r.is_cbt
return Info(n, mx_id, is_cbt)
return dfs(root, 1).is_cbtPython 写法2：BFS
class Solution:
def isCompleteTree(self, root: TreeNode) -> bool:
# if not root: return True
from collections import deque
q = deque()
q.append([root, 1])
n = 1 # 记录节点数
mx_id = 1 # 记录最大 id
while q:
node, id_ = q.popleft()
if node.left:
n += 1
q.append([node.left, id_ * 2])
if node.right:
n += 1
q.append([node.right, id_ * 2 + 1])
mx_id = id_ # max(mx_id, id_)
return n == mx_id
给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。- 自顶向下先序遍历即可，使用一个全局变量记录最小值；
- 踩坑：第一眼想到的是后序遍历，即贪心的查找每个节点的最小值，但在这里局部最优不能推出全局最优；
用例1：
[4,0,1,1]错误:"be"预期:"bae"
用例2：[25,1,null,0,0,1,null,null,null,0]错误:"abz"预期:"ababz"
Python：写法1）回溯（推荐）
# 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 smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
from collections import deque
self.ret = '~' # '~' > 'z'
def get_c(v): # 数字转字母
return chr(97 + v)
def dfs(x, buf): # 先序遍历
if not x: return
buf.appendleft(get_c(x.val))
if not x.left and not x.right: # 当达到叶子节点时比较
self.ret = min(self.ret, ''.join(buf))
dfs(x.left, buf)
dfs(x.right, buf)
buf.popleft() # 记得回溯
dfs(root, deque())
return self.retPython：写法2）不回溯，直接修改实参
# 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 smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
self.ret = '~' # '~' > 'z'
def get_c(v): # 数字转字母
return chr(97 + v)
def dfs(x, buf): # 先序遍历
if not x: return
if not x.left and not x.right: # 当达到叶子节点时比较
self.ret = min(self.ret, get_c(x.val) + buf)
# 不回溯，直接修改实参
dfs(x.left, get_c(x.val) + buf)
dfs(x.right, get_c(x.val) + buf)
dfs(root, '')
return self.ret