第一题、338.比特位计数
这道题需要计算从 0 到 n 的每个整数的二进制表示中的 1 的数目。
部分编程语言有相应的内置函数用于计算给定的整数的二进制表示中的 1 的数目，例如 Java 的 Integer.bitCount，C++ 的 __builtin_popcount，Go 的 bits.OnesCount 等。下列各种方法均为不使用内置函数的解法。
「一比特数」表示二进制表示中的 1 的数目。
方法一、Brian Kernighan 算法
最直观的做法是对从 0 到 n 的每个整数直接计算「一比特数」。每个 int 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。
利用 Brian Kernighan 算法，可以在一定程度上进一步提升计算速度。Brian Kernighan 算法的原理是：对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
对于给定的 n，计算从 0 到 n 的每个整数的「一比特数」的时间都不会超过 O(logn)，因此总时间复杂度为 O(nlogn)。
与231.2的幂的技巧一思路类似
class Solution:
def countBits(self, n: int) -> List[int]:
def countOnes(x: int) -> int:
ones = 0
while x > 0:
x &= (x - 1)
ones += 1
return ones
bits = [countOnes(i) for i in range(n + 1)]
return bits
时间复杂度：O(nlogn)。需要对从 0 到 n 的每个整数使用计算「一比特数」，对于每个整数计算「一比特数」的时间都不会超过 O(logn)。
空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。
方法二、动态规划——最高有效位
方法一需要对每个整数使用 O(logn) 的时间计算「一比特数」。可以换一个思路，当计算 i 的「一比特数」时，如果存在 0≤j<i，j 的「一比特数」已知，且 i 和 j 相比，i 的二进制表示只多了一个 1，则可以快速得到 i 的「一比特数」。
令 bits[i] 表示 i 的「一比特数」，则上述关系可以表示成：bits[i]=bits[j]+1。
对于正整数 x，如果可以知道最大的正整数 y，使得 y≤x 且 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，此时称 y 为 x 的「最高有效位」。令 z=x−y，显然 0≤z<x，则 bits[x]=bits[z]+1。
为了判断一个正整数是不是 2 的整数次幂，可以利用方法一中提到的按位与运算的性质。如果正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y & (y−1)=0。由此可见，正整数 y 是 2 的整数次幂，当且仅当 y & (y−1)=0。
显然，0 的「一比特数」为 0。使用 highBit 表示当前的最高有效位，遍历从 1 到 n 的每个正整数 i，进行如下操作。
如果 i & (i−1)=0，则令 highBit=i，更新当前的最高有效位。
i 比 i−highBit 的「一比特数」多 1，由于是从小到大遍历每个整数，因此遍历到 i 时，i−highBit 的「一比特数」已知，令 bits[i]=bits[i−highBit]+1。
最终得到的数组 bits 即为答案。
from typing import List # 导入List类型用于类型注解
class Solution:
def countBits(self, n: int) -> List[int]:
bits = [0] # 初始化bits列表，第一个元素为0，因为0的二进制表示中没有1
highBit = 0 # 初始化highBit为0，表示最高有效位的位置
# 从1到n逐一计算每个数字的二进制表示中1的个数
for i in range(1, n + 1):
# 检查当前数字是否是2的幂，是的话则更新highBit
# 当i是2的幂时，i & (i - 1) == 0
if i & (i - 1) == 0:
highBit = i # 更新highBit为当前的i
# bits[i] 的值等于bits[i - highBit] + 1
# 例如，对于数字5（'101'），我们可以用2（'10'）的结果加上1位（'1'）
bits.append(bits[i - highBit] + 1)
return bits # 返回包含0到n每个数字的二进制表示中1的个数的列表
时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。
方法三、动态规划——最低有效位
方法二需要实时维护最高有效位，当遍历到的数是 2 的整数次幂时，需要更新最高有效位。如果再换一个思路，可以使用「最低有效位」计算「一比特数」。
class Solution:
def countBits(self, n: int) -> List[int]:
bits = [0]
for i in range(1, n + 1):
bits.append(bits[i >> 1] + (i & 1))
return bits
时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。
方法四：动态规划——最低设置位
class Solution:
def countBits(self, n: int) -> List[int]:
bits = [0]
for i in range(1, n + 1):
bits.append(bits[i & (i - 1)] + 1)
return bits
时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。
第二题、1122.数组的相对排序
方法一、自定义排序
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
rank = {val: i for i, val in enumerate(arr2)} # 创建一个字典来存储arr2中每个元素的排名
# 对arr1进行排序，使用自定义排序规则
arr1.sort(key=lambda x: (rank.get(x, len(arr2)), x))
# 自定义排序规则：
# 1. rank.get(x, len(arr2)) 会返回元素x在arr2中的位置，如果x不在arr2中，则返回一个较大的默认值len(arr2)。
# 2. 如果x在arr2中，那么就根据它在arr2中的顺序进行排序。
# 3. 如果x不在arr2中，那么根据元素本身的大小进行排序。
return arr1 # 返回排序后的arr1
很多语言支持对「元组」进行排序，即依次比较元组中每一个对应位置的元素，直到比较出大小关系为止。因此，对于元素 x，如果它出现在哈希表中，使用二元组 (0,rank[x])；如果它没有出现在哈希表中，使用二元组 (1,x)，就可以得到正确的排序结果。
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
def mycmp(x: int) -> (int, int):
return (0, rank[x]) if x in rank else (1, x)
rank = {x: i for i, x in enumerate(arr2)}
arr1.sort(key=mycmp)
return arr1
此外，由于题目中给定的元素都是正数，因此可以用 rank[x]−n 和 x 分别代替 (0,rank[x]) 和 (1,x)，其中 n 是数组 arr2 的长度（同时也是哈希表 rank 的大小）。这样做的正确性在于，rank[x]−n 一定是负数，而 x 一定是正数。
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
def mycmp(x: int) -> (int, int):
return rank[x] if x in rank else x
n = len(arr2)
rank = {x: i - n for i, x in enumerate(arr2)}
arr1.sort(key=mycmp)
return arr1
时间复杂度：O(mlogm+n)，其中 m 和 n 分别是数组 arr1 和 arr2 的长度。构造哈希表 rank 的时间复杂度为 O(n)，排序的时间复杂度为 O(mlogm)。
空间复杂度：O(logm+n)，哈希表 rank 需要的空间为 O(n)，排序需要的栈空间为 O(logm)。
方法二：计数排序
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
upper = max(arr1) # 找到arr1中的最大值，用于创建频率数组
frequency = [0] * (upper + 1) # 创建一个大小为upper+1的频率数组，初始值为0
# 统计arr1中每个元素的出现频率
for x in arr1:
frequency[x] += 1
ans = list() # 初始化结果列表
# 按照arr2中的顺序将元素添加到结果列表
for x in arr2:
ans.extend([x] * frequency[x]) # 将x重复frequency[x]次加入结果列表
frequency[x] = 0 # 更新频率数组，将已处理的元素的频率设为0
# 将arr1中剩余不在arr2中的元素按升序加入结果列表
for x in range(upper + 1):
if frequency[x] > 0: # 如果该元素的频率大于0
ans.extend([x] * frequency[x]) # 将x重复frequency[x]次加入结果列表
return ans # 返回排序后的结果列表
第三题、56.合并区间
算法：
用数组 merged 存储最终的答案。
首先，将列表中的区间按照左端点升序排序。然后将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，可以直接将这个区间加入数组 merged 的末尾；
否则，它们重合，需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
正确性证明：
上述算法的正确性可以用反证法来证明：在排完序后的数组中，两个本应合并的区间没能被合并，那么说明存在这样的三元组 (i,j,k) 以及数组中的三个区间 a[i],a[j],a[k] 满足 i<j<k 并且 (a[i],a[k]) 可以合并，但 (a[i],a[j]) 和 (a[j],a[k]) 不能合并。这说明它们满足下面的不等式：
a[i].end<a[j].start(a[i] 和 a[j] 不能合并)
a[j].end<a[k].start(a[j] 和 a[k] 不能合并)
a[i].end≥a[k].start(a[i] 和 a[k] 可以合并)
联立这些不等式（注意还有一个显然的不等式 a[j].start≤a[j].end），可以得到：
a[i].end<a[j].start≤a[j].end<a[k].start
产生了矛盾！这说明假设是不成立的。因此，所有能够合并的区间都必然是连续的。
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 # 返回合并后的区间列表
时间复杂度：O(nlogn)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(nlogn)。
空间复杂度：O(logn)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn) 即为排序所需要的空间复杂度。
第四题、300.最长递增子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 如果输入列表为空，则最长递增子序列长度为0
if not nums:
return 0
# 初始化dp数组，用于存储以每个元素结尾的最长递增子序列的长度
dp = []
# 遍历每个元素，逐一计算以该元素结尾的最长递增子序列长度
for i in range(len(nums)):
# 默认情况下，任何单个元素自身可以构成长度为1的递增子序列
dp.append(1)
# 比较当前元素nums[i]与之前所有元素nums[j]的大小关系
for j in range(i):
# 如果nums[i]大于nums[j]，说明可以在nums[j]后面追加nums[i]形成更长的递增子序列
if nums[i] > nums[j]:
# 更新dp[i]为dp[j] + 1与当前dp[i]的最大值
dp[i] = max(dp[i], dp[j] + 1)
# 返回dp数组中的最大值，即为最长递增子序列的长度
return max(dp)
方法二：贪心 + 二分查找
考虑一个简单的贪心，如果要使上升子序列尽可能的长，则需要让序列上升得尽可能慢，因此希望每次在上升子序列最后加上的那个数尽可能的小。
基于上面的贪心思路，维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]。
同时注意到 d[i] 是关于 i 单调递增的。因为如果 d[j]≥d[i] 且 j<i，考虑从长度为 i 的最长上升子序列的末尾删除 i−j 个元素，那么这个序列长度变为 j ，且第 j 个元素 x（末尾元素）必然小于 d[i]，也就小于 d[j]。那么就找到了一个长度为 j 的最长上升子序列，并且末尾元素比 d[j] 小，从而产生了矛盾。因此数组 d 的单调性得证。
依次遍历数组 nums 中的每个元素，并更新数组 d 和 len 的值。如果 nums[i]>d[len] 则更新 len=len+1，否则在 d[1…len]中找满足 d[i−1]<nums[j]<d[i] 的下标 i，并更新 d[i]=nums[j]。
根据 d 数组的单调性，可以使用二分查找寻找下标 i，优化时间复杂度。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 定义一个数组d，用于维护当前的最长递增子序列
d = []
# 遍历输入数组中的每个数字n
for n in nums:
# 如果d为空或当前数字n大于d的最后一个元素，直接将n追加到d末尾
if not d or n > d[-1]:
d.append(n)
else:
# 否则，使用二分查找找到d中第一个大于等于n的位置，并替换掉那个位置的值
l, r = 0, len(d) - 1
loc = r # 初始化loc为右边界，表示需要更新的位置
# 进行二分查找
while l <= r:
mid = (l + r) // 2 # 计算中间位置mid
if d[mid] >= n:
loc = mid # 如果d[mid]大于等于n，更新loc为mid
r = mid - 1 # 缩小右边界
else:
l = mid + 1 # 否则缩小左边界
# 使用n替换掉位置loc处的值
d[loc] = n
# 返回d的长度，即为最长递增子序列的长度
return len(d)
时间复杂度：O(nlogn)。数组 nums 的长度为 n，依次用数组中的元素去更新 d 数组，而更新 d 数组时需要进行 O(logn) 的二分搜索，所以总时间复杂度为 O(nlogn)。
空间复杂度：O(n)，需要额外使用长度为 n 的 d 数组。
第五题、91.解码方法
class Solution:
def numDecodings(self, s: str) -> int:
# 获取字符串的长度
n = len(s)
# 初始化dp数组f，f[i]表示前i个字符的解码方法数
# f[0]初始化为1，因为空字符串有一种解码方法（即什么都不做）
f = [1] + [0] * n
# 遍历字符串的每个字符
for i in range(1, n + 1):
# 如果当前字符s[i-1]不是'0'，则它可以作为一个单独的数字解码
if s[i - 1] != '0':
f[i] += f[i - 1]
# 如果前一个字符和当前字符组成的双位数字在10到26之间
# 并且前一个字符不是'0'，则它们可以作为一个两位数解码
if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
f[i] += f[i - 2]
# 返回解码方法的总数，即f[n]
return f[n]
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
# 初始化a, b, c分别对应f[i-2], f[i-1], f[i]，用于状态压缩
a, b, c = 0, 1, 0
# 遍历字符串的每个字符
for i in range(1, n + 1):
# 重置c为0，因为每轮需要重新计算f[i]
c = 0
# 如果当前字符s[i-1]不是'0'，则它可以作为一个单独的数字解码
if s[i - 1] != '0':
c += b
# 如果前一个字符和当前字符组成的双位数字在10到26之间
# 并且前一个字符不是'0'，则它们可以作为一个两位数解码
if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
c += a
# 更新状态a和b，准备下一次循环使用
a, b = b, c
# 返回解码方法的总数，即c
return c
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(n) 或 O(1)。如果使用数组进行状态转移，空间复杂度为 O(n)；如果仅使用三个变量，空间复杂度为 O(1)。
