算法D37 | 贪心算法6 | 738.单调递增的数字 968.监控二叉树
738.单调递增的数字
代码随想录
(图片来源网络,侵删)
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 = 0 for 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 int: # 0:本节点无覆盖 1:本节点有摄像头 2:本节点有覆盖 if self.traversal(root) == 0: self.result += 1 return 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; } };
总结
可以看看贪心算法的总结,贪心本来就没啥规律,能写出个总结篇真的不容易了。
代码随想录
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。