之后的代码都用Python3编写。。
第一题、367.有效的完全平方数
此题和昨天刷的69题本质一样，并且都有相同的方法二分查找和牛顿迭代法
先看使用内置的库函数如何解此题
根据完全平方数的性质，只需要直接判断 num 的平方根 x 是否为整数即可。对于不能判断浮点数的值是否等于整数的语言，则可以通过以下规则判断：
class Solution:
def isPerfectSquare(self, num: int) -> bool:
return float.is_integer(pow(num, 0.5))
代码中使用的 pow 函数的时空复杂度与 CPU 支持的指令集相关
方法一、暴力法
如果 num 为完全平方数，那么一定存在正整数 x 满足 x×x=num。于是可以从 1 开始，从小到大遍历所有正整数，寻找是否存在满足 x×x=num 的正整数 x。在遍历中，如果出现正整数 x 使 x×x>num，那么更大的正整数也不可能满足 x×x=num，不需要继续遍历了。
class Solution:
def isPerfectSquare(self, num: int) -> bool:
x = 1
square = 1
while square <= num:
if square == num:
return True
x += 1
square = x * x
return False
时间复杂度：O(根号n)，其中 n 为正整数 num 的最大值。最多需要遍历 根号n+1 个正整数。
空间复杂度：O(1)。
方法二、二分查找
使用二分查找来优化方法一中的搜索过程。因为 num 是正整数，所以若正整数 x 满足 x×x=num，则 x 一定满足 1≤x≤num。于是可以将 1 和 num 作为二分查找搜索区间的初始边界。
因为在移动左侧边界 left 和右侧边界 right 时，新的搜索区间都不会包含被检查的下标 mid，所以搜索区间的边界始终是没有检查过的。因此，当left=right 时，仍需要检查 mid=(left+right)/2。
class Solution:
def isPerfectSquare(self, num: int) -> bool:
# 初始化左右边界，left为0，right为num
left, right = 0, num
# 当左边界小于等于右边界时，继续循环
while left <= right:
# 计算中间值
mid = (left + right) // 2
# 计算中间值的平方
square = mid * mid
# 如果平方小于num，说明平方根在右半部分
if square < num:
left = mid + 1
# 如果平方大于num，说明平方根在左半部分
elif square > num:
right = mid - 1
# 如果平方等于num，说明num是完全平方数
else:
return True
# 如果退出循环仍未找到，说明num不是完全平方数
return False
时间复杂度：O(logn)，其中 n 为正整数 num 的最大值。
空间复杂度：O(1)。
方法三、牛顿迭代法（了解）
思路：
如果 num 为完全平方数，那么一定存在正整数 x 满足 x×x=num。得出如下方程：
y=f(x)=x^2 −num
如果方程能够取得整数解，则说明存在满足 x×x=num 的正整数 x。这个方程可以通过牛顿迭代法求解。
算法：
class Solution:
def isPerfectSquare(self, num: int) -> bool:
# 初始化x0为num，用来作为迭代的初始值
x0 = num
# 不断迭代逼近平方根
while True:
# 计算新的迭代值x1，使用牛顿迭代法公式
x1 = (x0 + num / x0) / 2
# 如果x0和x1之间的差距小于1e-6，认为已经收敛，退出循环
if x0 - x1 < 1e-6:
break
# 更新x0为新的迭代值x1，继续迭代
x0 = x1
# 将x0转换为整数，以消除小数部分的误差
x0 = int(x0)
# 检查x0的平方是否等于num，如果相等，返回True，否则返回False
return x0 * x0 == num
空间复杂度：O(1)。
第二题、33.搜索旋转排序数组
我的想法：第一反应这不是遍历一遍数组就可以解决的问题吗，为啥要描述那么多。然后看到你必须设计一个时间复杂度为 O(log n) 的算法解决此问题，所以前面铺垫了那么多旋转，其实是为了突出这是一个局部有序的数组，O(log n) 又是很明显的二分查找会有的时间复杂度，因此此题是考察二分查找的。
方法、二分查找
官方题解说的思路感觉有点啰嗦（应该是他在第五层而我在第一层），下面的思路更清晰易懂：
1.将数组一分为二。（其中有一个一定是有序的；另一个则是有序或部分有序的）
2.此时如果target在有序部分里，则用二分法查找。
3.否则进入无序部分查找，返回1。
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 如果数组为空，直接返回-1，表示未找到
if not nums:
return -1
# 初始化左右指针，l为左边界，r为右边界
l, r = 0, len(nums) - 1
# 当左指针小于等于右指针时，继续循环
while l <= r:
# 计算中间位置
mid = (l + r) // 2
# 如果中间值等于目标值，返回其索引
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
# 如果循环结束还未找到目标值，返回-1
return -1
时间复杂度： O(logn)，其中 n 为 nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
空间复杂度： O(1) 。只需要常数级别的空间存放变量。
第三题、74.搜索二维矩阵
方法一、两次二分查找
由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。
可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 在矩阵的第一列使用二分查找确定目标值可能所在的行
rowIndex = self.binarySearchFirstColumn(matrix, target)
# 如果返回的行索引小于0，表示目标值不在矩阵的范围内
if rowIndex < 0:
return False
# 在确定的行中使用二分查找目标值
return self.binarySearchRow(matrix[rowIndex], target)
def binarySearchFirstColumn(self, matrix: List[List[int]], target: int) -> int:
# 初始化low为-1，high为最后一行的索引
low, high = -1, len(matrix) - 1
# 二分查找第一列，找到最后一个小于或等于目标值的行
while low < high:
# 计算中间位置mid
mid = (high - low + 1) // 2 + low
# 如果mid行的第一个元素小于或等于目标值，移动low到mid
if matrix[mid][0] <= target:
low = mid
# 否则，移动high到mid - 1
else:
high = mid - 1
# 返回最后找到的行索引
return low
def binarySearchRow(self, row: List[int], target: int) -> bool:
# 初始化low为0，high为行的最后一个元素的索引
low, high = 0, len(row) - 1
# 在行中使用二分查找目标值
while low <= high:
# 计算中间位置mid
mid = (high - low) // 2 + low
# 如果mid位置的值等于目标值，返回True
if row[mid] == target:
return True
# 如果mid位置的值大于目标值，移动high到mid - 1
elif row[mid] > target:
high = mid - 1
# 如果mid位置的值小于目标值，移动low到mid + 1
else:
low = mid + 1
# 如果未找到目标值，返回False
return False
时间复杂度：O(logm+logn)=O(logmn)，其中 m 和 n 分别是矩阵的行数和列数。
空间复杂度：O(1)。
此代码需要注意的几个点：
①binarySearchFirstColumn中初始化low = -1
②binarySearchFirstColumn中while循环的条件是low < high
③mid = (high - low + 1) // 2 + low 和常规的二分查找的中间值计算有区别
方法二、一次二分查找
若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，可以在该数组上二分找到目标元素。
代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 获取矩阵的行数m和列数n
m, n = len(matrix), len(matrix[0])
# 初始化二分查找的左右边界
low, high = 0, m * n - 1
# 开始二分查找
while low <= high:
# 计算中间位置mid
mid = (high - low) // 2 + low
# 将一维索引转换为二维矩阵中的行列索引
x = matrix[mid // n][mid % n]
# 如果x小于目标值target，移动low到mid + 1
if x < target:
low = mid + 1
# 如果x大于目标值target，移动high到mid - 1
elif x > target:
high = mid - 1
# 如果x等于目标值，返回True
else:
return True
# 如果遍历完仍未找到目标值，返回False
return False
时间复杂度：O(logmn)，其中 m 和 n 分别是矩阵的行数和列数。
空间复杂度：O(1)。
两种方法殊途同归，都利用了二分查找，在二维矩阵上寻找目标值。值得注意的是，若二维数组中的一维数组的元素个数不一，方法二将会失效，而方法一则能正确处理。
第四题、153.寻找旋转排序数组中的最小值
方法、二分查找（思路很妙）
class Solution:
def findMin(self, nums: List[int]) -> int:
# 初始化二分查找的左右边界
low, high = 0, len(nums) - 1
# 开始二分查找
while low < high:
# 计算中间位置pivot
pivot = low + (high - low) // 2
# 如果中间元素小于右边界元素，说明最小值在左侧（包括pivot）
if nums[pivot] < nums[high]:
high = pivot
# 否则，最小值在右侧（不包括pivot）
else:
low = pivot + 1
# 循环结束时，low指向最小值位置，返回最小值
return nums[low]
时间复杂度：O(logn)，其中 n 是数组 nums 的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为 O(logn)。
空间复杂度：O(1)。
第五题、70.爬楼梯
方法一、动态规划
class Solution:
def climbStairs(self, n: int) -> int:
# 初始化变量p, q, r，分别表示前两步及当前步的方案数
p, q, r = 0, 0, 1
# 从第1阶楼梯到第n阶楼梯逐步计算
for i in range(1, n + 1):
# 将q的值赋给p，即更新前两步的方案数
p = q
# 将r的值赋给q，即更新上一步的方案数
q = r
# 计算当前步的方案数，等于前两步方案数之和
r = p + q
# 返回到达第n阶楼梯的方案数
return r
时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。
方法二、矩阵快速幂（了解）
class Solution:
def climbStairs(self, n: int) -> int:
# 定义矩阵q，用于Fibonacci数列的矩阵形式
q = [[1, 1], [1, 0]]
# 计算q的n次幂，返回的矩阵存储在res中
res = self.pow(q, n)
# 返回矩阵res中的第一个元素，即Fibonacci数列的第n个数
return res[0][0]
def pow(self, a: List[List[int]], n: int) -> List[List[int]]:
# 初始化单位矩阵ret，作为结果矩阵的初始值
ret = [[1, 0], [0, 1]]
# 使用快速幂算法计算矩阵a的n次幂
while n > 0:
# 如果n是奇数，则将当前的a矩阵乘到ret上
if (n & 1) == 1:
ret = self.multiply(ret, a)
# n右移一位，相当于除以2
n >>= 1
# 将矩阵a自乘，准备计算下一个更高次幂
a = self.multiply(a, a)
# 返回最终的幂矩阵
return ret
def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
# 初始化2x2结果矩阵c
c = [[0, 0], [0, 0]]
# 进行矩阵乘法运算
for i in range(2):
for j in range(2):
# 计算矩阵c的第[i][j]个元素，c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j]
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
# 返回乘法结果矩阵c
return c
时间复杂度：同快速幂，O(logn)。
空间复杂度：O(1)。
方法三、通项公式
为什么递推方程 f(n) = f(n-1) + f(n-2) 会导出特征方程 x^2 = x + 1？
递推方程 f(n) = f(n-1) + f(n-2) 是一个线性齐次递推关系，这意味着每一项可以用前几项的线性组合来表示。为了解这个递推方程，假设一个解的形式为：
f(n) = r^n
这里， r^n 表示的是某种形式的解（类似于指数函数）。假设 f(n) 是这种形式，然后代入递推方程：
r^n = r^{n-1} + r^{n-2}
之后将这个方程两边都除以 r^{n-2}（假设 r 不为零）：r^2 = r + 1这就是特征方程。
这个方法数学思维比较强，我没理解为什么通解要那样设置，只能了解此思路。
class Solution:
def climbStairs(self, n: int) -> int:
# 计算√5的值
sqrt5 = math.sqrt(5)
# 使用斐波那契数列的通项公式计算第n个斐波那契数
fibn = math.pow((1 + sqrt5) / 2, n + 1) - math.pow((1 - sqrt5) / 2, n + 1)
# 将结果除以√5并四舍五入取整，返回结果作为爬楼梯的总方法数
return int(round(fibn / sqrt5))
第六题、120.三角形最小路径和
在本题中，给定的三角形的行数为 n，并且第 i 行（从 0 开始编号）包含了 i+1 个数。如果将每一行的左端对齐，那么会形成一个等腰直角三角形，如下所示：
[2]
[3,4]
[6,5,7]
[4,1,8,3]
方法一、动态规划
用 f[i][j] 表示从三角形顶部走到位置 (i,j) 的最小路径和。这里的位置 (i,j) 指的是三角形中第 i 行第 j 列（均从 0 开始编号）的位置。
由于每一步只能移动到下一行「相邻的节点」上，因此要想走到位置 (i,j)，上一步就只能在位置 (i−1,j−1) 或者位置 (i−1,j)。在这两个位置中选择一个路径和较小的来进行转移，状态转移方程为：
f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]
其中 c[i][j] 表示位置 (i,j) 对应的元素值。
注意第 i 行有 i+1 个元素，它们对应的 j 的范围为 [0,i]。当 j=0 或 j=i 时，上述状态转移方程中有一些项是没有意义的。例如当 j=0 时，f[i−1][j−1] 没有意义，因此状态转移方程为：
f[i][0]=f[i−1][0]+c[i][0]
即当在第 i 行的最左侧时，只能从第 i−1 行的最左侧移动过来。当 j=i 时，f[i−1][j] 没有意义，因此状态转移方程为：
f[i][i]=f[i−1][i−1]+c[i][i]
即当在第 i 行的最右侧时，只能从第 i−1 行的最右侧移动过来。
最终的答案即为 f[n−1][0] 到 f[n−1][n−1] 中的最小值，其中 n 是三角形的行数。
状态转移方程的边界条件是什么？由于已经去除了所有「没有意义」的状态，因此边界条件可以定为：
f[0][0]=c[0][0]
即在三角形的顶部时，最小路径和就等于对应位置的元素值。这样一来，从 1 开始递增地枚举 i，并在 [0,i] 的范围内递增地枚举 j，就可以完成所有状态的计算。
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# 获取三角形的行数
n = len(triangle)
# 初始化一个与三角形相同大小的二维数组 f
f = [[0] * n for _ in range(n)]
# 设置顶部元素的初始值
f[0][0] = triangle[0][0]
# 从第二行开始处理
for i in range(1, n):
# 处理每行的第一个元素
f[i][0] = f[i - 1][0] + triangle[i][0]
# 处理每行中间的元素
for j in range(1, i):
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]
# 处理每行的最后一个元素
f[i][i] = f[i - 1][i - 1] + triangle[i][i]
# 返回最后一行的最小值
return min(f[n - 1])
时间复杂度：O(n^2)，其中 n 是三角形的行数。
空间复杂度：O(n^2)。需要一个 n∗n 的二维数组存放所有的状态。
方法二、动态规划+空间优化（有点难）
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# 获取三角形的行数
n = len(triangle)
# 初始化一个只有两行的二维数组 f，用于动态规划
f = [[0] * n for _ in range(2)]
# 设置顶部元素的初始值
f[0][0] = triangle[0][0]
# 从第二行开始处理
for i in range(1, n):
# 当前行和上一行的索引计算
curr, prev = i % 2, 1 - i % 2
# 处理每行的第一个元素
f[curr][0] = f[prev][0] + triangle[i][0]
# 处理每行中间的元素
for j in range(1, i):
f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j]
# 处理每行的最后一个元素
f[curr][i] = f[prev][i - 1] + triangle[i][i]
# 返回最后一行的最小值
return min(f[(n - 1) % 2])
上述方法的空间复杂度为 O(n)，使用了 2n 的空间存储状态。还可以继续进行优化吗？
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# 获取三角形的行数
n = len(triangle)
# 初始化一维数组 f，用于存储当前行的最小路径和
f = [0] * n
# 设置顶部元素的初始值
f[0] = triangle[0][0]
# 从第二行开始处理
for i in range(1, n):
# 处理当前行的最后一个元素
f[i] = f[i - 1] + triangle[i][i]
# 从当前行的倒数第二个元素开始，更新当前行的每个元素
for j in range(i - 1, 0, -1):
f[j] = min(f[j - 1], f[j]) + triangle[i][j]
# 处理当前行的第一个元素
f[0] += triangle[i][0]
# 返回最后一行的最小值
return min(f)
时间复杂度：O(n^2)，其中 n 是三角形的行数。
空间复杂度：O(n)。
本题还有一些其它的动态规划方法，例如：
从三角形的底部开始转移，到顶部结束；
直接在给定的三角形数组上进行状态转移，不使用额外的空间。
第七题、53.最大子数组合
方法一、动态规划
class Solution:
def maxSubArray(self, nums):
# 初始化变量pre为0，表示当前子数组的最大和
pre = 0
# 初始化变量maxAns为数组中的第一个元素，表示目前为止找到的最大子数组和
maxAns = nums[0]
# 遍历数组中的每一个元素x
for x in nums:
# 更新当前子数组的最大和pre，选择当前元素x自身，或是包含当前元素x的子数组的最大和
pre = max(pre + x, x)
# 更新全局最大子数组和maxAns
maxAns = max(maxAns, pre)
# 返回找到的最大子数组和
return maxAns
时间复杂度：O(n)，其中 n 为 nums 数组的长度。只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。只需要常数空间存放若干变量。
注意动态规划有无后效性：
为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」。
方法二、分治
class Solution:
# 定义状态类，包含四个属性：lSum, rSum, mSum, iSum
class Status:
def __init__(self, lSum, rSum, mSum, iSum):
self.lSum = lSum # 左边最大子数组和
self.rSum = rSum # 右边最大子数组和
self.mSum = mSum # 整个区间的最大子数组和
self.iSum = iSum # 区间的总和
# 合并两个子区间的状态
def pushUp(self, l, r):
iSum = l.iSum + r.iSum # 合并区间的总和
lSum = max(l.lSum, l.iSum + r.lSum) # 左边最大子数组和
rSum = max(r.rSum, r.iSum + l.rSum) # 右边最大子数组和
mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum) # 整个区间的最大子数组和
return self.Status(lSum, rSum, mSum, iSum)
# 递归求解区间[l, r]的状态
def get(self, a, l, r):
if l == r: # 基本情况：只有一个元素
return self.Status(a[l], a[l], a[l], a[l])
m = (l + r) // 2 # 计算中点
lSub = self.get(a, l, m) # 递归求解左子区间
rSub = self.get(a, m + 1, r) # 递归求解右子区间
return self.pushUp(lSub, rSub) # 合并两个子区间的状态
# 主函数：求解最大子数组和
def maxSubArray(self, nums):
return self.get(nums, 0, len(nums) - 1).mSum
难懂点详解：
lSum = max(l.lSum, l.iSum + r.lSum) # 左边最大子数组和
示例
考虑数组 a = [2, -1, 3, 4, -2, 1, -1]。计算区间 [0, 5] 的 lSum，即这个区间的最大左边子数组和。
步骤 1: 分割区间
将区间 [0, 5] 分成两个子区间：
- 左子区间
[0, 2] - 右子区间
[3, 5]
步骤 2: 计算子区间的状态
对于左子区间 [0, 2]：
- 元素：
[2, -1, 3] -
iSum（总和）：2 + (-1) + 3 = 4 -
lSum（左边最大子数组和）：这是左子区间的最大子数组和，并且它的子数组是[2, -1, 3]。可以计算出：-
[2]的和是2 -
[2, -1]的和是1 -
[2, -1, 3]的和是4 -
[3]的和是3
所以lSum = max(2, 1, 4, 3) = 4
对于右子区间[3, 5]：
-
- 元素：
[4, -2, 1] -
iSum（总和）：4 + (-2) + 1 = 3 -
lSum（左边最大子数组和）：这是右子区间的最大子数组和，并且它的子数组是[4, -2, 1]。可以计算出：-
[4]的和是4 -
[4, -2]的和是2 -
[4, -2, 1]的和是3 -
[1]的和是1
所以lSum = max(4, 2, 3, 1) = 4
-
步骤 3: 计算整个区间 [0, 5] 的 lSum
将这两个子区间的结果合并，以计算整个区间 [0, 5] 的 lSum。lSum 可以来源于两种情况：
-
左子区间的
lSum：即[0, 2]的lSum，已经计算出它是4。 -
跨越边界的子数组：
- 这种情况下，最大左边子数组和可能涉及到整个区间的一部分，可能从左子区间的某个位置扩展到右子区间的某个位置。
- 计算方式是：左子区间的
iSum加上右子区间的lSum。- 左子区间的
iSum为4 - 右子区间的
lSum为4 - 它们的和为：
4 + 4 = 8
- 左子区间的
结果
- 从左子区间得到的
lSum是4 - 从跨越边界的子数组得到的
lSum是8
因此，整个区间[0, 5]的lSum为这两者中的最大值： lSum = max(4, 8) = 8
总结
lSum 的两种情况可以总结为：
-
左子区间的
lSum：当最大子数组仅位于左子区间内时使用。 -
左子区间的
iSum加上右子区间的lSum：当最大子数组跨越了左右子区间的边界时使用。
