代码随想录训练营Day28:贪心算法06

本文主要是介绍代码随想录训练营Day28:贪心算法06，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.738单调递增的数字

贪心策略：如果strNum[i]<strNum[i-1]那么strNum[i] = '9',strNum[i-1]--;//比如87对应的最大的单调递增的就是79.

具体实现：

1. 对于遇到小于的情况：如果strNum[i]<strNum[i-1]那么strNum[i] = '9',strNum[i-1]--;
2. 遍历顺序必须得是一个反向遍历，这样才能保证找到最高位数需要进行改变的地方。（如果从左往右进行便利的话，会出现一种这样的情况，例如N = 999998前面的都相等，那么需要改变的是最右侧那个位置，明显不符合，所以要从右往左进行遍历）
3. 使用flag来确定需要变成9的最左侧的位置

class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行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);}
};

2.968监控二叉树

贪心策略：一个摄像头能够监控到更多的节点。

具体实现：

• 首先要确定的就是遍历顺序，是自顶向下还是自底向上的遍历顺序如果是自顶向下的话，那么就是判断父节点是否被覆盖，此时需要设置的节点就是：2,3,8,9,10,11,12,13,14,15.如果是自底向上的情况那么就是判断左右孩子节点是否被覆盖，此时需要设置的节点就是：4,5,6,7,1.所以确定的遍历顺序就是自底向上的情况。
• 再确定就是状态：分为三种状态：0：未被覆盖，1：存放摄像头，2：被覆盖三种状态。
• 对于空节点的处理：如果空节点的状态为0，那么叶子结点就需要设置为存放摄像头的，明显是不符合的，当空节点的状态为2的时候，此时叶子结点就不需要设置摄像头了，只需要在叶子结点的上方设置摄像头即可，所以空节点设置为2.
• 当前节点为2（被覆盖）：左右孩子中至少有一个是1（设置为节点），且左右孩子不能为0。
• 当前节点为1（设置摄像头）：左右孩子中至少有一个为0（未被覆盖）。
• 当前节点为0（为被覆盖）：左右孩子全都是2（被覆盖状态）。
• 对于最后根节点的处理：因为会出现一种情况就是如果23全都是被覆盖，那么设置的1就是为未覆盖状态（0）退出，但是不符合实际，此时需要将其变成设置摄像头（2），所以最后还需要在主函数里面判断返回值是否为0。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://节点分三种情况：//0:没覆盖；1：该节点存放摄像头；2：该节点被覆盖//当节点为空的时候设置为被覆盖int result;int traversal(TreeNode* cur){if(cur == nullptr) return 2;int left = traversal(cur->left);int right = traversal(cur->right);//该节点为设置为没覆盖：左右节点都被覆盖if(left == 2&&right == 2)return 0;//该节点设置为监控if(left == 0||right == 0){result++;return 1;}//该节点设置为被覆盖//1.left =1,right =1;if(left == 1||right ==1){return 2;}return -1;//代表的知识一个完整性}int minCameraCover(TreeNode* root) {result = 0;if(traversal(root) == 0){//对于最后一个根节点的处理，如果此时设置为0，代表未被覆盖，需要重新设置为1，即result++;result++;}return result;}
};

这篇关于代码随想录训练营Day28:贪心算法06的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---