Day37 贪心part06
738.单调递增的数字
leetcode题目链接:738. 单调递增的数字 - 力扣(LeetCode)
思路:遍历数组,如果前一位i-1比后一位i的数值大,那前一位要-1,这样才能有比后一位小的可能,同时后一位取能取到的最大值,比如9
所以是从前往后还是从后往前
这道题看起来是要从前往后遍历,但是会出现以下问题:例如332,一开始33是符合的,但是到后面的32就不符合了,会变成329,这是这样又需要修改前一位了;所以这样遍历会造成之前的还需要重新变动
这里还有一个小技巧,虽然题目给出的是int类型,但是还是转化为str就可以逐位操作了,这样出现首位0的情况也不用担心,最终再转化位int即可
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
n = str(n)
flag = len(n) # 记录一下从哪一位开始要标记位9
for i in range(len(n)-1, 0, -1):
if n[i] < n[i-1]:
#这里修改不像c++的ascii是连续的 n[i-1] -= 1
n = n[:i-1]+ str(int(n[i-1])-1)+n[i:]
flag = i
i = flag
while i <len(n):
# print(i, n, len(n))
n = n[:i]+ '9'+ n[i+1:]
i+=1
return int(n)
968.监控二叉树
leetcode题目链接:. - 力扣(LeetCode)
思路:
1、贪心思路:发现题目示例中的摄像头都没有放在叶子节点上!这是很重要的一个线索,摄像头可以覆盖上中下三层,如果把摄像头放在叶子节点上,就浪费的一层的覆盖。所以把摄像头放在叶子节点的父节点位置,才能充分利用摄像头的覆盖面积。
2、二叉树的遍历顺序:所以我们要从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!所以应该是后序遍历(左右中)
**3、**情况处理,如何间隔两个节点放一个摄像头:节点状态表示
- 0:该节点无覆盖
- 1:本节点有摄像头
- 2:本节点有覆盖
情况判断:
- 如果两个孩子都是0或者又1个为0,那么父节点一定是1
- 如果两个孩子都是2,那么父节点是0
- Null节点是2
- 左右孩子节点有1个摄像头1,父节点是2
- 最后就是头节点root要是没有覆盖,也应该放置摄像头1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.res = 0
def traversal(self, node):
if node is None:
return 2
left = self.traversal(node.left)
right = self.traversal(node.right)
if left==0 or right == 0:
self.res+=1
return 1
elif left==2 and right == 2:
return 0
elif left==1 or right == 1:
return 2
def minCameraCover(self, root: Optional[TreeNode]) -> int:
value = self.traversal(root)
if value ==0:
self.res+=1
return self.res
还是要再复习一下二叉树