738. 单调递增的数字
- 思路
- example
89242
2
39
199
8999
88999 (final answer)
332
2
29
299 （final answer)
逆序遍历
nums[i-1] > nums[i]: i-1位减1，后面全变为9 (贪心）
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
s = list(str(n))
idx_9 = len(s)
for i in range(len(s)-1, 0, -1):
if int(s[i-1]) > int(s[i]):
s[i-1] = str(int(s[i-1]) - 1)
idx_9 = i
for i in range(idx_9, len(s)):
s[i] = '9'
# return ''.join(s) 10 --> '09'
return int(''.join(s))
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
s = str(n)
idx = len(s)
pre = int(s[-1])
for i in range(len(s)-2, -1, -1):
num = int(s[i])
if num > pre:
idx = i
pre = num - 1
else:
pre = num
if idx == len(s):
return int(s)
else:
return int(s[:idx] + str(int(s[idx])-1) + '9'*(len(s)-idx-1))
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
s = list(str(n))
idx = len(s) # !!!
for i in range(len(s)-2, -1, -1):
if int(s[i]) > int(s[i+1]):
s[i] = str(int(s[i]) - 1)
idx = i + 1
for i in range(idx, len(s)):
s[i] = '9'
return int(''.join(s))
714. 买卖股票的最佳时机含手续费
- 思路
- example
- 无限次地完成交易
- 每笔交易你只需要为支付一次手续费 (卖出）
- 复杂度. 时间：O(n), 空间: O(n)
- DP
- dp[i][0]: 第i天（收盘后）持有股票的最大收益
- dp[i][1]: 第i天不持有的最大收益
- 可空间优化
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
return dp[-1][1]
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee)
return dp[n-1][1]
- 贪心
第一次买入计入交易费
后面有盈利时卖出，并且更新新的成本价为卖出价（方便累加）
再次买入，需要用新的价格+fee与前一天的成本(pre_price)比较。
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
res = 0
pre_price = float('inf') # 上次卖出价 （成本价：包含手续费）
for i in range(len(prices)):
if prices[i] - pre_price > 0: # 卖出
res += prices[i] - pre_price
pre_price = prices[i]
elif prices[i] + fee < pre_price: # 买入
pre_price = prices[i] + fee
else:
continue
return res
968. 监控二叉树
- 思路
- example
- dfs: 自上而下（前序），自下而上（后序）
- 从底部住上看，贪心思路：叶子节点不加摄像头，加到其父节点，这样可以覆盖到爷爷节点。
- 递归返回值标记节点状态 (根据孩子节点结果分类）
- 0：无覆盖, 无摄像头 （没有被childern覆盖）
- 1：有覆盖， 有摄像头
- 2：有覆盖，无摄像头 （被其中一个child覆盖）
关键：空节点返回2（假设有进一步的child虚拟节点装摄头，从而状态为2)
(0, 0 or 1 or 2) --> 1
(1, 1 or 2) --> 2
(2, 2) --> 0
最后根节点如果返回0，必须把最终结果+1，因为根节点没有parent节点来装摄像头从而达到覆盖该根节点的目的。
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def minCameraCover(self, root: Optional[TreeNode]) -> int:
def traversal(root):
nonlocal res
if root == None:
return 2
left = traversal(root.left)
right = traversal(root.right)
if left == 0 or right == 0: # (0, 0 or 1 or 2) 只要有一个子节点无覆盖，root: 有摄像头
res += 1
return 1
elif left == 1 or right == 1: # (1, 1 or 2)只要有一个子节点装摄像头，root: 被子节点覆盖
return 2
elif left == 2 and right == 2: # (2, 2) 只剩下这种情况
return 0
res = 0
if traversal(root) == 0:
res += 1
return res
# - 0：无覆盖, 无摄像头 （没有**被childern覆盖**）
# - 1：有覆盖， 有摄像头
# - 2：有覆盖，无摄像头 （被其中一个child覆盖）
class Solution:
def minCameraCover(self, root: Optional[TreeNode]) -> int:
def traversal(root):
nonlocal res
if root == None:
return 2
left = traversal(root.left)
right = traversal(root.right)
if left == 0 or right == 0:
res += 1
return 1
if left == 1 or right == 1:
return 2
if left == 2 and right == 2:
return 0
res = 0
if traversal(root) == 0:
res += 1
return res
class Solution:
def minCameraCover(self, root: Optional[TreeNode]) -> int:
def traverse(root):
nonlocal res
if root == None:
return 2 # ???
if root.left == None and root.right == None:
return 0
left = traverse(root.left)
right = traverse(root.right)
if left == 0 or right == 0:
res += 1
return 1
if left == 1 or right == 1:
return 2
if left == 2 and right == 2:
return 0
res = 0
if traverse(root) == 0: # !!!
res += 1
return res
