算法D37 | 贪心算法6 | 738.单调递增的数字 968.监控二叉树

代码随想录

Python:

尝试了下写成非string修改的，会复杂一点。

class Solution:def monotoneIncreasingDigits(self, n: int) -> int:str_num = list(str(n))for i in range(len(str_num)-1, 0, -1):if str_num[i-1] > str_num[i]:str_num[i-1] = str(int(str_num[i-1]) - 1)for j in range(i, len(str_num)):str_num[j] = '9'result = 0for s in str_num:result = result*10 + int(s)return result

C++:

优化了一下，第一遍先更新flag指针；第二遍更新后续的9，比python版本稍优。

class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum = to_string(n);int flag = strNum.size();for (int i=strNum.size()-1; i>0; i--) {if (strNum[i-1] > strNum[i]) {flag = i;strNum[i-1]--;}}for (int i=flag; i<strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

968.监控二叉树 （可以跳过）

本题是贪心和二叉树的一个结合，比较难，一刷大家就跳过吧。 

代码随想录

Python:

思路还是比较直接的，动手画一画，需要耐心把不同情况梳理清楚。关键思路是把状态(0, 1, 2)分清楚。

class Solution:def __init__(self):self.result = 0def traversal(self, cur):# 后序遍历# 终止条件：空节点，该节点有覆盖if not cur: return 2left = self.traversal(cur.left)right = self.traversal(cur.right)# 1. 左右节点都有覆盖if left == 2 and right == 2: return 0# 2. 左右节点至少有一个无覆盖if left == 0 or right == 0:self.result += 1return 1# 3. 左右节点至少有一个有摄像头if left == 1 or right == 1: return 2def minCameraCover(self, root: Optional[TreeNode]) -> int:# 0：本节点无覆盖 1：本节点有摄像头 2：本节点有覆盖if self.traversal(root) == 0:self.result += 1return self.result

C++:

class Solution {
public:int result = 0;int traversal(TreeNode* cur) {// 后序遍历// 终止条件：空节点，该节点有覆盖if (cur==NULL) return 2;int left = traversal(cur->left);int right = traversal(cur->right);// 1. 左右节点都有覆盖if (left==2 && right==2) return 0;// 2. 左右节点至少有一个无覆盖if (left==0 || right==0) {result++;return 1;}// 3. 左右节点至少有一个有摄像头if (left==1 || right==1) return 2;return -1; // we shall never get here}int minCameraCover(TreeNode* root) {// 0：本节点无覆盖 1：本节点有摄像头 2：本节点有覆盖if (traversal(root)==0) {result++;}return result;}
};

总结 

可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了。 

代码随想录