????????貪心算法的最后一篇博客！前面兩道題都是比較簡單的思路，重點理解一下最后一道題即可。有一說一，進入到貪心算法這一章節之后，我的博客里和代碼注釋里的內容明顯少了很多，因為很多貪心的題目我覺得不需要很復雜的文字說明，很多題解都是很容易理解的內容，可能更多是一種思路的積累吧
56. 合并區間
? ? ? ? 重疊問題，弄明白：1.如何判斷重疊 2.區間修改邏輯
class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:result = []if len(intervals) == 0:return resultintervals.sort(key = lambda x: x[0])# 默認升序result.append(intervals[0])for i in range(1, len(intervals)):# 左閉右開if result[-1][1] >= intervals[i][0]: # 發現重疊result[-1][1] = max(result[-1][1], intervals[i][1])else:result.append(intervals[i])return result738.單調遞增的數字
????????舉幾個簡單的例子：
- 32->29
- 3323->2999
- 1253463->1249999
????????總結下來就是
- 找到“flag”(前一個小于cur，前-1，cur設為9，前一個為flag，遍歷查找flag)
- 將“flag”后面的數字全部設置為9
class Solution:def monotoneIncreasingDigits(self, n: int) -> int:strNum = str(n) # 轉換為字符串flag = len(strNum)for i in range(len(strNum) -1, 0, -1):# 注意這里是0, 因為循環中會比較前一個位置上的元素if strNum[i - 1] > strNum[i]:flag = i# 切片為左閉右開strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i :]for i in range(flag, len(strNum)):strNum = strNum[:i] + '9' + strNum[i + 1:]return int(strNum)
968.監控二叉樹
????????這道題目應該優先從葉子節點開始思考，要尊重后序遍歷，不要總是自頂（根節點）向下考慮
# 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:# 從下往上安裝攝像頭：跳過leaves這樣安裝數量最少，局部最優 -> 全局最優# 先給leaves的父節點安裝，然后每隔兩層節點安裝一個攝像頭，直到Head# 0: 該節點未覆蓋# 1: 該節點有攝像頭# 2: 該節點有覆蓋def minCameraCover(self, root: Optional[TreeNode]) -> int:result = [0]# 注意使用列表不使用int的原因：python中的參數傳遞機制# 之前博客中講過，就不在贅述if self.traversal(root, result) == 0:# 這個地方可能想不到result[0] += 1return result[0]def traversal(self, cur:TreeNode, result: List[int]) -> int:if not cur:return 2 # none節點返回2, 才能正常在葉子節點的父節點安裝攝像頭left = 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# 情況3if left == 1 or right == 1:return 2
 調研)
)
