第一题、860.柠檬水找零（简单）
方法、贪心
由于顾客只可能给三个面值的钞票，而且一开始没有任何钞票，因此拥有的钞票面值只可能是 5 美元，10 美元和 20 美元三种。基于此，有如下的分类讨论：
5 美元，由于柠檬水的价格也为 5 美元，因此直接收下即可。
10 美元，需要找回 5 美元，如果没有 5 美元面值的钞票，则无法正确找零。
20 美元，需要找回 15 美元，此时有两种组合方式，一种是一张 10 美元和 5 美元的钞票，一种是 3 张 5 美元的钞票，如果两种组合方式都没有，则无法正确找零。当可以正确找零时，两种找零的方式中更倾向于第一种，即如果存在 5 美元和 10 美元，就按第一种方式找零，否则按第二种方式找零，因为需要使用 5 美元的找零场景会比需要使用 10 美元的找零场景多，需要尽可能保留 5 美元的钞票。
基于此，需要维护两个变量 five 和 ten 表示当前手中拥有的 5 美元和 10 美元钞票的张数，从前往后遍历数组分类讨论即可。
class Solution(object):
def lemonadeChange(self, bills):
five = 0 # 初始化5美元的计数
ten = 0 # 初始化10美元的计数
for bill in bills: # 遍历每一个顾客支付的金额
if bill == 5: # 如果顾客支付5美元
five += 1 # 增加5美元的计数
elif bill == 10: # 如果顾客支付10美元
if five == 0: # 如果没有5美元可以找零
return False # 返回False，表示不能找零
five -= 1 # 用一个5美元找零
ten += 1 # 增加10美元的计数
else: # 如果顾客支付20美元
if five > 0 and ten > 0: # 如果有5美元和10美元可以组合找零
five -= 1 # 用一个5美元
ten -= 1 # 用一个10美元
elif five >= 3: # 如果没有10美元但有至少三个5美元
five -= 3 # 用三个5美元找零
else: # 如果既没有10美元也没有足够的5美元
return False # 返回False，表示不能找零
return True # 如果所有顾客都成功找零，返回True
时间复杂度：O(N)，其中 N 是 bills 的长度。
空间复杂度：O(1)。
第二题、455.分发饼干（简单）
方法一、排序 + 双指针 + 贪心
为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。证明如下：
class Solution(object):
def findContentChildren(self, g, s):
g.sort() # 将孩子的胃口列表从小到大排序
s.sort() # 将饼干的尺寸列表从小到大排序
m, n = len(g), len(s) # 分别获取孩子数量和饼干数量
i = j = count = 0 # 初始化孩子和饼干的指针，以及计数器
while i < m and j < n: # 当孩子和饼干都有剩余时，继续分配
while j < n and g[i] > s[j]: # 找到能满足当前孩子胃口的最小的饼干
j += 1 # 如果当前饼干尺寸太小，尝试下一块饼干
if j < n: # 如果找到合适的饼干
count += 1 # 满足的孩子数加一
i += 1 # 继续尝试下一个孩子
j += 1 # 当前饼干已经使用，指针移动到下一块饼干
return count # 返回能满足的最多孩子数量
时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是数组 g 和 s 的长度。对两个数组排序的时间复杂度是 O(mlogm+nlogn)，遍历数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。
空间复杂度：O(logm+logn)，其中 m 和 n 分别是数组 g 和 s 的长度。空间复杂度主要是排序的额外空间开销。
第三题、122.买卖股票的最佳时机2（中等）
方法一、动态规划
「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。
定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）。
考虑 dp[i][0] 的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即 dp[i−1][0]，或者前一天结束的时候手里持有一支股票，即 dp[i−1][1]，这时候要将其卖出，并获得 prices[i] 的收益。因此为了收益最大化，有如下的转移方程：
dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]}
再来考虑 dp[i][1]，按照同样的方式考虑转移状态，那么可能的转移状态为前一天已经持有一支股票，即 dp[i−1][1]，或者前一天结束时还没有股票，即 dp[i−1][0]，这时候要将其买入，并减少 prices[i] 的收益。可以列出如下的转移方程：
dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}
对于初始状态，根据状态定义可以知道第 0 天交易结束的时候 dp[0][0]=0，dp[0][1]=−prices[0]。
因此，只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n−1][0] 的收益必然是大于 dp[n−1][1] 的，最后的答案即为 dp[n−1][0]。
class Solution(object):
def maxProfit(self, prices):
n = len(prices) # 获取价格列表的长度
dp = [[0] * 2 for _ in range(n)] # 初始化dp数组，大小为n×2
dp[0][0] = 0 # 第一天不持有股票的利润为0
dp[0][1] = -prices[0] # 第一天持有股票的利润为负的当天股票价格
for i in range(1, n):
# 第i天不持有股票的利润为前一天不持有股票的利润和当天卖出股票后的利润两者的最大值
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
# 第i天持有股票的利润为前一天持有股票的利润和当天买入股票后的利润两者的最大值
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[n - 1][0] # 返回最后一天不持有股票的最大利润
优化：注意到上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此不必存储这些无关的状态，只需要将 dp[i−1][0] 和 dp[i−1][1] 存放在两个变量中，通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量，以便于第 i+1 天的状态转移即可。
class Solution(object):
def maxProfit(self, prices):
n = len(prices) # 获取价格列表的长度
dp0 = 0 # 初始化不持有股票时的利润为0
dp1 = -prices[0] # 初始化持有股票时的利润为负的第一天股票价格
for i in range(1, n):
newDp0 = max(dp0, dp1 + prices[i]) # 计算当天不持有股票的最大利润
newDp1 = max(dp1, dp0 - prices[i]) # 计算当天持有股票的最大利润
dp0 = newDp0 # 更新dp0为当前最大不持有股票的利润
dp1 = newDp1 # 更新dp1为当前最大持有股票的利润
return dp0 # 返回最后一天不持有股票的最大利润
时间复杂度：O(n)，其中 n 为数组的长度。一共有 2n 个状态，每次状态转移的时间复杂度为 O(1)，因此时间复杂度为 O(2n)=O(n)。
空间复杂度：O(n)。需要开辟 O(n) 空间存储动态规划中的所有状态。如果使用空间优化，空间复杂度可以优化至 O(1)。
方法二、贪心
class Solution(object):
def maxProfit(self, prices):
ans = 0 # 初始化最大利润为0
n = len(prices) # 获取价格列表的长度
for i in range(1, n):
# 如果今天的价格比昨天高，则卖出股票并累加利润
ans += max(0, prices[i] - prices[i - 1])
return ans # 返回总的最大利润
时间复杂度：O(n)，其中 n 为数组的长度。只需要遍历一次数组即可。
空间复杂度：O(1)。只需要常数空间存放若干变量。
第四题、874.模拟行走机器人（中等）
方法、哈希表
题目给出一个在点 (0,0) ，并面向北方的机器人。现在有一个大小为 n 的命令数组 commands 来操作机器人的移动，和一个大小为 m 的障碍物数组 obstacles。现在通过 commands 来模拟机器人的移动，并用一个哈希表来存储每一个障碍物放置点。当机器人的指令为向前移动时，尝试往前移动对应的次数——若往前一个单位不为障碍物放置点（即不在哈希表中），则机器人向前移动一个单位，否则机器人保持原位不变。
在机器人移动的过程中记录从原点到机器人所有经过的整数路径点的最大欧式距离的平方即为最后的答案。
在代码实现的过程中，对于机器人转向和向前移动的操作，可以用一个方向数组 dirs={[−1,0],[0,1],[1,0],[0,−1]} 来现实。若当前机器人的坐标为 (x,y)，当前方向的标号为 d，则往前移动一单位的操作为 x=x+dirs[d][0]，y=y+dirs[i][1]。向左转的操作为 d=(d+3)mod4，向右转的操作为 d=(d+1)mod4。
class Solution(object):
def robotSim(self, commands, obstacles):
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]] # 定义四个方向：上、右、下、左
px, py, d = 0, 0, 1 # 机器人初始位置在原点，初始方向为向右（d=1）
mp = set([tuple(i) for i in obstacles]) # 将障碍物列表转换为集合（哈希表），方便查询
res = 0 # 初始化最大欧几里得距离为0
for c in commands: # 遍历每一个命令
if c < 0: # 如果命令是改变方向的
d += 1 if c == -1 else -1 # -1表示向右转，-2表示向左转
d %= 4 # 保证方向在0到3之间循环
else: # 如果命令是前进的步数
for i in range(c): # 按步数逐步移动
# 检查下一步是否会遇到障碍物
if tuple([px + dirs[d][0], py + dirs[d][1]]) in mp:
break # 如果遇到障碍物，则停止移动
# 更新机器人位置
px, py = px + dirs[d][0], py + dirs[d][1]
# 更新最大欧几里得距离
res = max(res, px * px + py * py)
return res # 返回机器人行走过程中到原点的最大欧几里得距离
时间复杂度：O(C×n+m)，其中 n 为数组 commands 的大小，C 为每次可以向前的步数最大值，在该题目中 C=9，m 为数组 obstacles 的大小。时间开销主要为模拟机器人移动和哈希表存储每一个障碍物的坐标的开销。
空间复杂度：O(m)，其中 m 为数组 obstacles 的大小，主要为哈希表存储 obstacles 的空间开销。
疑难杂症：
①、d=1为什么表示向右
在代码中，d 代表方向的索引，用来指示机器人当前朝向的方向。dirs 数组定义了四个可能的移动方向，分别是：
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
这个数组中的每个元素代表了机器人在该方向上的移动增量，分别是：
-
[-1, 0]表示向上移动一格（y轴增加） -
[0, 1]表示向右移动一格（x轴增加） -
[1, 0]表示向下移动一格（y轴减少） -
[0, -1]表示向左移动一格（x轴减少）
初始时，d = 1对应dirs[1]，也就是[0, 1]，这表示机器人最初面向“向右”的方向。所以，d = 1表示机器人一开始朝向右边。
②、
d += 1 if c == -1 else -1
这行代码是用来处理机器人在接收到转向命令时，更新它的朝向方向。
c是当前的命令值。如果
c == -1，表示机器人要向右转。-
如果
c == -2，表示机器人要向左转。
c == -1(向右转):- 如果当前命令
c是-1，意味着机器人需要向右转 90 度。 -
d += 1表示将d增加 1，向右转一次。
c == -2(向左转): - 如果当前命令
c是-2，意味着机器人需要向左转 90 度。 -
else -1表示将d减少 1，向左转一次。
- 如果当前命令
假设
d初始值为 1，表示机器人一开始面向右方。如果
c == -1，表示向右转，d += 1使得d从 1 变成 2，表示机器人现在面向下方。如果
c == -2，表示向左转，d -= 1使得d从 1 变成 0，表示机器人现在面向上方。
在执行完这行代码后，d可能会超出范围（0-3），因此需要通过d %= 4来确保d的值在[0, 3]范围内循环变化，表示机器人朝向四个基本方向中的一个。
第五题、55.跳跃游戏（中等）
方法、贪心
对于数组中的任意一个位置 y，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x+nums[x]，这个值大于等于 y，即 x+nums[x]≥y，那么位置 y 也可以到达。
换句话说，对于每一个可以到达的位置 x，它使得 x+1,x+2,⋯,x+nums[x] 这些连续的位置都可以到达。
这样以来，依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么就可以从起点通过若干次跳跃到达该位置，因此可以用 x+nums[x] 更新 最远可以到达的位置。
在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，就返回 False 作为答案。
示例一：
[2, 3, 1, 1, 4]
一开始在位置 0，可以跳跃的最大长度为 2，因此最远可以到达的位置被更新为 2；
遍历到位置 1，由于 1≤2，因此位置 1 可达。用 1 加上它可以跳跃的最大长度 3，将最远可以到达的位置更新为 4。由于 4 大于等于最后一个位置 4，因此直接返回 True。
示例二：
[3, 2, 1, 0, 4]
一开始在位置 0，可以跳跃的最大长度为 3，因此最远可以到达的位置被更新为 3；
遍历到位置 1，由于 1≤3，因此位置 1 可达，加上它可以跳跃的最大长度 2 得到 3，没有超过最远可以到达的位置；
位置 2、位置 3 同理，最远可以到达的位置不会被更新；
遍历到位置 4，由于 4>3，因此位置 4 不可达，也就不考虑它可以跳跃的最大长度了。
在遍历完成之后，位置 4 仍然不可达，因此返回 False。
class Solution(object):
def canJump(self, nums):
n, rightmost = len(nums), 0 # n为数组长度，rightmost为当前能够到达的最远位置
for i in range(n): # 遍历数组中的每一个位置
if i <= rightmost: # 如果当前位置在当前能够到达的最远位置之内
rightmost = max(rightmost, i + nums[i]) # 更新能够到达的最远位置
if rightmost >= n - 1: # 如果能够到达或超过最后一个位置
return True # 返回True，表示可以跳到最后一个位置
return False # 如果遍历结束后仍不能到达最后一个位置，返回False
时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。
空间复杂度：O(1)，不需要额外的空间开销。
第六题、45.跳跃游戏2
此题用贪心，通过局部最优解得到全局最优解，有以下两种不同策略的贪心
方法一、反向查找出发位置
目标是到达数组的最后一个位置，因此可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。
如果有多个位置通过跳跃都能够到达最后一个位置，可以「贪心」地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，可以从左到右遍历数组，选择第一个满足要求的位置。
找到最后一步跳跃前所在的位置之后，继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。
官方说使用这种方法编写的 C++ 和 Python 代码会超出时间限制，Java 和 Go 代码不会。。以下是Java
class Solution {
public int jump(int[] nums) {
int position = nums.length - 1;
int steps = 0;
while (position > 0) {
for (int i = 0; i < position; i++) {
if (i + nums[i] >= position) {
position = i;
steps++;
break;
}
}
}
return steps;
}
}
时间复杂度：O(n^2 )，其中 n 是数组长度。有两层嵌套循环，在最坏的情况下，例如数组中的所有元素都是 1，position 需要遍历数组中的每个位置，对于 position 的每个值都有一次循环。
空间复杂度：O(1)。
方法二、正向查找可到达的最大位置
方法一虽然直观，但是时间复杂度比较高
如果「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。
例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。
从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。
在具体的实现中，维护当前能够到达的最大下标位置，记为边界。从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。
在遍历数组时，不访问最后一个元素，这是因为在访问最后一个元素之前，边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，会增加一次「不必要的跳跃次数」，因此不必访问最后一个元素。
class Solution(object):
def jump(self, nums):
n = len(nums)
# 初始化最远可达位置、当前遍历的边界和跳跃次数
maxPos, end, step = 0, 0, 0
for i in range(n - 1): # 遍历到倒数第二个元素
if maxPos >= i: # 如果当前位置i在之前跳跃能到达的范围内
# 更新最远可达位置
maxPos = max(maxPos, i + nums[i])
# 如果遍历到了当前跳跃的边界
if i == end:
# 更新边界为新的最远可达位置
end = maxPos
# 跳跃次数加1
step += 1
# 如果能到达最后一个位置，返回跳跃次数；否则，原始代码假设总是能到达，这里不处理-1的情况
return step
时间复杂度：O(n)，其中 n 是数组长度。
空间复杂度：O(1)。
第七题、69.x的平方根（简单）
此题为经典常见面试题，一般的思路会有以下几种：通过其它的数学函数代替平方根函数得到精确结果，取整数部分作为答案；通过数学方法得到近似结果，直接作为答案。
方法一、袖珍计算器算法
class Solution(object):
def mySqrt(self, x):
# 如果输入x为0，则直接返回0，因为0的平方根是0
if x == 0:
return 0
# 使用对数和指数运算来近似计算x的平方根，并转换为整数
# 这里利用了数学恒等式：sqrt(x) = exp(0.5 * log(x))
# 其中exp表示指数函数，log表示自然对数函数
ans = int(math.exp(0.5 * math.log(x)))
# 判断ans+1的平方是否小于等于x
# 如果是，说明ans+1更接近x的平方根（且不超过x的平方根），因此返回ans+1
# 如果不是，说明ans就是x的平方根（向下取整），因此返回ans
return ans + 1 if (ans + 1) ** 2 <= x else ans
时间复杂度：O(1)，由于内置的 exp 函数与 log 函数一般都很快，在这里将其复杂度视为 O(1)。
空间复杂度：O(1)。
方法二、二分查找
由于 x 平方根的整数部分 ans 是满足 k^2≤x 的最大 k 值，因此可以对 k 进行二分查找，从而得到答案。
二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。由于所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 ans 后，也就不需要再去尝试 ans+1 了。
class Solution(object):
def mySqrt(self, x):
# 初始化左边界l为0，右边界r为x（因为平方根肯定小于等于x）
# ans用于记录当前找到的最大平方根（初始化为-1，但实际上这个初始值不会被使用，因为第一轮循环就会更新它）
l, r, ans = 0, x, -1
# 当左边界小于等于右边界时，进行循环
while l <= r:
# 计算中间值mid，使用整除来避免整数溢出
mid = (l + r) // 2
# 如果mid的平方小于等于x，说明真实的平方根要么等于mid，要么大于mid
# 更新ans为mid（因为要求的是整数部分），并将左边界移动到mid+1，以尝试找到更大的平方根
if mid * mid <= x:
ans = mid
l = mid + 1
# 如果mid的平方大于x，说明真实的平方根一定小于mid，因此将右边界移动到mid-1
else:
r = mid - 1
# 循环结束时，ans将包含最接近x的平方根的整数部分（向下取整）
return ans
时间复杂度：O(logx)，即为二分查找需要的次数。
空间复杂度：O(1)。
方法三、牛顿迭代（此方法了解）
class Solution(object):
def mySqrt(self, x):
# 如果输入x为0，则直接返回0，因为0的平方根是0
if x == 0:
return 0
# 将输入x转换为浮点数，以便进行小数运算
# 同时，将x0初始化为x的浮点数形式，作为迭代的初始猜测值
C, x0 = float(x), float(x)
# 使用牛顿迭代法来逼近平方根
# 牛顿迭代法的迭代公式为：xi = 0.5 * (x0 + C / x0)，其中C是要开平方的数，x0是当前的猜测值
while True:
# 根据牛顿迭代公式计算下一个猜测值xi
xi = 0.5 * (x0 + C / x0)
# 检查当前猜测值x0与下一个猜测值xi的差的绝对值是否小于一个很小的数（如1e-7）
# 如果是，则认为已经足够接近真实的平方根，跳出循环
if abs(x0 - xi) < 1e-7:
break
# 更新x0为xi，为下一次迭代做准备
x0 = xi
# 将最终的猜测值x0（此时已经非常接近真实的平方根）转换为整数并返回
# 注意：由于使用的是浮点数运算，这里可能会有轻微的精度损失
# 但由于检查了两个猜测值之间的差是否小于一个很小的数，因此这种精度损失是可以接受的
return int(x0)
时间复杂度：O(logx)，此方法是二次收敛的，相较于二分查找更快。
空间复杂度：O(1)。
