122. 买卖股票的最佳时机 II
- 思路
- example
-
交易次数无限制 （收盘价买卖）
- 也没有手续费限制
- 假设也可以当天以相同价格先卖后买 （简化模型）
- 抓住每一个上升波段 （长波段可拆分成小波段方便累加），贪心策略：见利就跑
- 注意本题是马后炮方法（已知未来价格），刻舟求剑，不具实际意义。
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for i in range(1, len(prices)):
res += max(0, prices[i]-prices[i-1])
return res
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
res = 0
for i in range(1, n):
res += max(0, prices[i]-prices[i-1])
return res
- DP 方法
- dp[i][0]: 第i天持有股票的最大收益 （注意：持有是一种状态，不代表第i天就一定买入，有可能前几天买入股票一直持有到第i天）
- dp[i][1]: 第i天不持有股票的最大收益 （同理，不持有是一种状态）
- 目标：max(dp[-1][0], dp[-1][1])
- 递推公式
- 第i天持有的最大收益，分两个情况（取最优的情况)：前一天不持有收益 - prices[i]; 前一天持有收益保持到今天。简单来说，分为：第i天买入 和 第i天不买入。
- 第i天不持有的最大收益, 类似。
- 初始化
- dp[0][0] = - prices[0]
- dp[0][1] = 0 (当天买完立马卖，收益=0)
- 可空间优化
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0] * 2 for _ in range(len(prices))]
dp[0][0], dp[0][1] = - prices[0], 0
for i in range(1, len(prices)):
dp[i][0] = max(dp[i-1][1] - prices[i], dp[i-1][0])
dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1])
return max(dp[-1][0], dp[-1][1])
55. 跳跃游戏
- 思路
- example
- 暴力回溯
- 顺推 （Shooting) 贪心，顺序遍历数组，每一次更新可以到达的最远点，如果最远点大于最尾节点，说明末尾可达到。注意，只是遍历数组，不模拟跳跃过程。
- 注意当遍历到一个不可达节点时，不能把该点作为candidate与 end 比较。
if i <= end: end = max(end, i + nums[i])
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def canJump(self, nums: List[int]) -> bool:
end = 0
for i in range(len(nums)):
if i <= end:
end = max(end, i + nums[i])
if end >= len(nums) - 1:
return True
return False
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
right = 0
for i in range(n):
if right >= n-1:
return True
if i > right:
return False
right = max(right, i + nums[i])
class Solution:
def canJump(self, nums: List[int]) -> bool:
right = 0
for i in range(len(nums)):
if i > right:
break
right = max(right, i + nums[i])
if right >= len(nums)-1:
return True
return False
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
right = 0
for i in range(n):
if right < i: # !!!
return False
right = max(right, i+nums[i])
if right >= n-1:
return True
return False
- 稍微不同写法
class Solution:
def canJump(self, nums: List[int]) -> bool:
end = 0
for i in range(len(nums)):
if i <= end:
end = max(end, i + nums[i])
else:
return False
return True
- DP
TBA
45. 跳跃游戏 II
- 思路
- example
- 返回到达 nums[n - 1] 的最小跳跃次数。
-
题目保证可以跳到末尾。
- 用BFS思路 （一层一层或一步一步处理）, 层序方法
- 遍历节点
- 第一步：计算最远终点，把最远终点之前未考虑过的节点(index)加进deque
- 第二步：循环处理当前层的节点，更新最远节点（达到或超过末尾节点 就可以结束）
- 注意corner case, e.g., nums = [0], ans = 0
- 注意return 答案的逻辑。
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def jump(self, nums: List[int]) -> int:
que = collections.deque()
que.append(0)
end = 0
level = -1 # level = step, 首节点是第0步
while que:
level += 1
if end >= len(nums) - 1:
return level
size = len(que)
end_level = -1
for _ in range(size):
index = que.popleft()
end_level = max(end_level, index + nums[index])
if end_level <= end and end != len(nums) - 1:
return -1
else: # end_level > end
for i in range(end, end_level+1):
que.append(i)
end = end_level # update end
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
que = collections.deque()
que.append(0)
right = 0
res = 0
while que:
if right >= n-1:
return res
size = len(que)
right_old = right
res += 1
for _ in range(size):
idx = que.popleft()
right = max(right, idx + nums[idx])
for j in range(right_old+1, right+1):
que.append(j)
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
left, right = 0, 0
cnt = 0
while right < n-1:
cnt += 1
new_right = right
for i in range(left, right+1):
new_right = max(new_right, i+nums[i])
left = right + 1
right = max(right, new_right)
return cnt
- 下面的版本更简洁
class Solution:
def jump(self, nums: List[int]) -> int:
que = collections.deque()
que.append(0)
end = 0
level = -1 # level = step, 首节点是第0步
while que:
level += 1
if end >= len(nums) - 1:
return level
size = len(que)
end_level = -1
for _ in range(size):
index = que.popleft()
end_level = max(end_level, index + nums[index])
if end_level > end:
for i in range(end, end_level+1):
que.append(i)
end = end_level # update end
return -1
空间可优化，不需要把全部待考虑节点加进deque,只需要维护左右边界。
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
left, right = 0, 0 # 取代deque, 当前level的左右边界
level = -1
while right - left >= 0:
level += 1
if right >= n-1:
return level
right_old = right
for i in range(left, right+1):
right = max(right, i + nums[i])
left = right_old + 1
- DP
TBA
