LeetCode刷题笔记【28】：贪心算法专题-6（单调递增的数字、监控二叉树）

前置知识

参考前文

参考文章：
LeetCode刷题笔记【23】：贪心算法专题-1（分发饼干、摆动序列、最大子序和）
LeetCode刷题笔记【24】：贪心算法专题-2（买卖股票的最佳时机II、跳跃游戏、跳跃游戏II）
LeetCode刷题笔记【25】：贪心算法专题-3（K次取反后最大化的数组和、加油站、分发糖果）
LeetCode刷题笔记【26】：贪心算法专题-4（柠檬水找零、根据身高重建队列、用最少数量的箭引爆气球）
LeetCode刷题笔记【27】：贪心算法专题-5（无重叠区间、划分字母区间、合并区间）

738.单调递增的数字

题目描述

LeetCode链接：https://leetcode.cn/problems/monotone-increasing-digits/description/

解题思路

思路：如果一个数本身是符合“单调递增”的话，那么直接返回其本身
如果其不满足，那么找到其不满足的那一位，将其--，后面的位数都=9
注意找到这一位后，如果这一位和其左侧的数一样，那么还需要找到这一串一样的数的最左边一个，再对其进行上述操作。

这种思路感觉很取巧，但其实是有效的。
哪一位产生的“非递增”的问题，那么就需要对这一位进行--操作，而其后面的那些位，因为题目要求“最大数字”，所以需要都是9.

代码

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string N = to_string(n);
        // cout << "N= " << N << endl;
        for(int i=0; i<N.size()-1; ++i){
            // cout << "i= " << i << endl;
            if(N[i] > N[i+1]){
                int p=i;
                while(p>0 && N[p]==N[p-1])
                    p--;
                N[p]--;
                for(int j=p+1; j<N.size(); ++j){
                    // cout << "j= " << j << endl;
                    N[j] = 9 + '0';
                    // cout << "N[j]= " << N[j] << endl;
                }
                break;
            }
        }
        cout << "N= " << N << endl;
        return stoi(N);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

968.监控二叉树

题目描述

LeetCode链接：https://leetcode.cn/problems/binary-tree-cameras/description/

解题思路

参考<代>, 使用贪心
这里的贪心贪的是叶子节点, 就是我们一定要让叶子节点是没有摄像头, 而叶子节点的父节点是有摄像头的, 才最优

所以这里需要自底向上推导

三种状态: ①没有覆盖 ②有摄像头(也被覆盖) ③没有摄像头, 但是被覆盖

递归过程是先递归左右节点, 然后根据左右节点的结果, 生成本节点的结果, 然后返回本节点的状态
对于根节点, 要注意, 如果最后发现根节点的状态是"没有覆盖", result要再+1

左右任意为1, 本节点为2;
左右任意为2, 本节点为3;
左右都为3, 本节点为1;
1
2
3

为了让达到刚才说的"让叶子节点是没有摄像头, 而叶子节点的父节点是有摄像头", 需要让null节点为3

代码

class Solution {
private:
    int ans=0;
    int helper(TreeNode* root){
        if(root==nullptr)
            return 3;
        int left = helper(root->left);
        int right = helper(root->right);
        if(left==1 || right==1){
            ans++;
            return 2;
        }else if(left==2 || right==2){
            return 3;
        }else{
            return 1;
        }
        return 0;
    }
public:
    int minCameraCover(TreeNode* root) {
        int rootMode = helper(root);
        if(rootMode==1)
            ans++;
        return ans;
    }
};
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

总结

贪心相关题目做到今天也告一段落了, 总结起来, 我依然并不是很赞同"贪心"这一题目分类.

因为归根结底我都感觉"贪心"并不能算是一种"解题方法", 充其量是一种难以捉摸的"解题思想", 甚至被分在这一题目合集下的, 大多是各种奇技淫巧的操作.

这些题目, 对于应试而言, 只能多看几遍, 保持印象;
而对于代码能力的提升而言, 只能说聊胜于无, 略好于纯粹的脑筋急转弯吧.

本文参考：
单调递增的数字
监控二叉树