LeetCode Day 37 Greedy Algorithm (6/6)

The last day of greedy algorithm practice!

Question 1

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.

It looks like brute force method can do it, but it will timeout.

With back-to-front traversal, the local optimum can be pushed out to the global optimum, just right for using greed.

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        strNum = str(n)
        flag = len(strNum)
        for i in range(len(strNum) - 1, 0, -1):
          
            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)

Question 2

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.

Place the camera at the position of the parent node of the leaf node in order to make full use of the coverage area of the camera.

Local optimum: let the parent node of the leaf node plant the camera with the least number of cameras used, and overall optimum: the least number of cameras used for the entire number of cameras! This is still the solution to the greedy algorithm.

class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        result = [0] 
        if self.traversal(root, result) == 0:
            result[0] += 1
 
        return result[0]
 
        
    def traversal(self, cur: TreeNode, result: List[int]) -> int:
        if not cur:
            return 2
 
        left = self.traversal(cur.left, result)
        right = self.traversal(cur.right, result)
 
        if left == 2 and right == 2:
            return 0
 
        elif left == 0 or right == 0:
            result[0] += 1
            return 1
 
 
        else:
            return 2