代码随想录算法训练营DAY37|C++贪心算法Part.6|738.单调递增的数字、968.监控二叉树、贪心算法总结

738.单调递增的数字

力扣题目链接

文章链接：738.单调递增的数字

视频链接：贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字

状态：

超时的暴力解法

bool checkNum(int num) {
  int max = 10;
  while (num) {
    int t = num % 10;
    if (max >= t) max = t;
    else return false;
    num = num / 10;
  }
  return true;
}
int monotoneIncreasingDigits(int N) {
  for (int i = N; i < 0; i--) {
    if (checkNum(i)) return i;
  }
  reteurn 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

贪心思路

这里举一个例子32，当我们遇到32时，即碰到十位比个位大，我们需要把十位减1变成2，，个位取最大变成9。这样我们可以取到最大的递增数字，那么我们之后都按照这种逻辑从右到左进行遍历，处理其他数字，比如332，从右到左遍历碰到32变成29,再遍历还是32，再变成29。最终332->229正确。在此基础上，我们推导出贪心决策：

局部最优：从后向前遍历，只要碰到十位数比个位数大的，我们就把十位减1，个位直接变成9；

全局最优：得到最大的递增数字。

CPP代码

代码实现有一个技巧，就是用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]--;
            }
        }
      //这段代码也很精妙，如果直接strNum[flag]会段错误
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

968.监控二叉树

力扣题目链接

文章链接：968.监控二叉树

视频链接：贪心算法，二叉树与贪心的结合，有点难… LeetCode:968.监督二叉树

状态：

思路

首先明确一个，叶子结点相较于头结点，数量是指数级别的，所以我们一定要从下往上去安装摄像头，让摄像头能够更多得去覆盖结点。

局部最优：让叶子结点的父结点安装摄像头

整体最优：全部摄像头数量所用最少。

本题的代码难点：

1. 二叉树的遍历？
2. 怎么放摄像头！

伪代码

确认遍历顺序

很明显一个，后序遍历，可以让我们从底向上去遍历二叉树，这样我们也可以在回溯的过程中从下到上进行推导

int traversal(TreeNode* cur) {
  //空结点，该结点有覆盖
  if (终止条件) return ;
  
  int left = traversal(cur->left); //左
  int right = traversal(cur->right); //右
  
  逻辑处理	//中
  return ;	
}
1
2
3
4
5
6
7
8
9
10

如何隔两个结点放一个摄像头。

我们需要状态转移公式。

首先明确结点的各个状态：

• 0：该节点无覆盖
• 1：本节点有摄像头
• 2：本节点有覆盖

再明确一条，对空结点的处理：将空结点的状态定义为有覆盖，这样是因为我们需要在叶子结点的父结点放摄像头。这样我们可以确定出：

递归的终止条件

//空节点，该节点有覆盖
if (cur == NULL) return 2;
1
2

---

关于单层递归逻辑，主要有以下四类情况：

• 情况1:左右节点都有覆盖，左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。

//0：本节点无覆盖，1：本节点有摄像头，2：本节点有覆盖
//左右结点都有覆盖
if (left == 2 && right == 2) return 0;
1
2
3

• 情况2：左右节点至少有一个无覆盖，这样我们就需要在中间（父）节点放一个摄像头

if (left == 0 || right == 0) {
  result++;
  return 1;
}
1
2
3
4

• 情况3：左右结点至少有一个有摄像头，那么其父节点就是2

if (left == 1 || right == 1) return 2;
1

• 情况4:头节点没有被覆盖

等以上都处理完，递归结束，可能头节点还有一个无覆盖的情况，如图：

递归结束之后，还要判断根节点，如果没有覆盖，result++

int minCameraCover(TreeNode* root) {
    result = 0;
    if (traversal(root) == 0) { // root 无覆盖
        result++;
    }
    return result;
}
1
2
3
4
5
6
7

CPP代码

// 版本一
class Solution {
private:
    int result;
    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
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1) return 2;

        // 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
        // 这个 return -1 逻辑不会走到这里。
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        // 情况4
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};

//精简版
// 版本二
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {
        if (cur == NULL) return 2;
        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右
        if (left == 2 && right == 2) return 0;
        else if (left == 0 || right == 0) {
            result++;
            return 1;
        } else return 2;
    }
public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

贪心算法总结

贪心算法总结

卡哥的贪心总结真的已经很帅了，但是一刷的我并不太能get到，等到二刷个人再总结一波！