738. Monotone Increasing Digits
An integer has?monotone increasing digits單調遞增數字?if and only if each pair of adjacent digits?x?and?y?satisfy?x <= y.
Given an integer?n, return?the largest number that is less than or equal to?n?with?monotone increasing digits.
?violent solution:
Time complexity: O(n × m)? ? ? m is the length of the number n
Space complexity: O(1)
class Solution:def monotoneIncreasingDigits(self, n: int) -> int:for i in range(n, -1, -1):if self.check_num(i):return i#return 0def check_num(self, n):max = 10while n:t = n % 10if max >= t:max = telse:return Falsen = n//10return True
greedy:
1. A local optimum leads to a global
2. traversal from right to the left
class Solution:def monotoneIncreasingDigits(self, n: int) -> int:n_str = list(str(n))for i in range(len(n_str) - 1, 0, -1):if n_str[i] < n_str[i - 1]: #string can compare the value, but you can still use int()n_str[i - 1] = str(int(n_str[i - 1]) - 1)for j in range(i, len(n_str)):n_str[j] = '9'return int(''.join(n_str))Time complexity: O(n),? ?n is the length of the number
Space complexity: O(n), need a string, it is more convenient to convert to string operation
968. Binary Tree Cameras
You are given the?root?of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor監控 its parent, itself, and its immediate children.
Return?the minimum number of cameras needed to monitor all nodes of the tree.
Local optimization: let the parent of a leaf node plant a camera, the least number of cameras used.
Overall optimization: minimize the number of cameras used for all.?
Case 1: Both left and right nodes are covered
?Case 2: At least one of the left and right nodes is uncovered
?Case 3: At least one of the left and right nodes has a camera
?Case 4: Header node not covered
?
class Solution:# Greedy Algo:# 從下往上安裝攝像頭：跳過leaves這樣安裝數量最少，局部最優 -> 全局最優# 先給leaves的父節點安裝，然后每隔兩層節點安裝一個攝像頭，直到Head# 0: 該節點未覆蓋# 1: 該節點有攝像頭# 2: 該節點有覆蓋def minCameraCover(self, root: TreeNode) -> int:# 定義遞歸函數result = [0] # 用于記錄攝像頭的安裝數量if self.traversal(root, result) == 0:result[0] += 1return result[0]def traversal(self, cur: TreeNode, result: List[int]) -> int:if not cur:return 2left = self.traversal(cur.left, result)right = self.traversal(cur.right, result)# 情況1: 左右節點都有覆蓋if left == 2 and right == 2:return 0# 情況2:# left == 0 && right == 0 左右節點無覆蓋# left == 1 && right == 0 左節點有攝像頭，右節點無覆蓋# left == 0 && right == 1 左節點無覆蓋，右節點有攝像頭# left == 0 && right == 2 左節點無覆蓋，右節點覆蓋# left == 2 && right == 0 左節點覆蓋，右節點無覆蓋if left == 0 or right == 0:result[0] += 1return 1# 情況3:# left == 1 && right == 2 左節點有攝像頭，右節點有覆蓋# left == 2 && right == 1 左節點有覆蓋，右節點有攝像頭# left == 1 && right == 1 左右節點都有攝像頭if left == 1 or right == 1:return 2?
)
