随想录一刷Day37——贪心算法

Day37_贪心算法

22. 单调递增的数字

738. 单调递增的数字

为了方便按位判断，将数字转化为字符串，从低位向高位逐个比较，要求高位数字大于低位数字，如果不满足，则低位向高位借1，低位置为9，如此反复至遍历完整个数字的每一位。
为什么不从右往左比较呢？
因为如果有借位出现的话，高位要-1，从左向右利用不到这一处理的结果。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str_num = to_string(n); // 注意数字转为字符串后，低位下标大
        int s_len = str_num.length();
        int flag_start = s_len;
        for (int i = s_len - 1; i > 0; --i) { // 从低位到高位遍历
            if (str_num[i] < str_num[i - 1]) { // 低位小于高位
                flag_start = i;
                str_num[i - 1]--; // 向高位借位
            }
        }
        for (int i = flag_start; i < s_len; ++i) {
            str_num[i] = '9';
        }
        return stoi(str_num);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

23. 买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费

由于加入了手续费，所以要让买入卖出的次数尽可能少，即在低谷买入，在顶峰卖出，可以通过在上升时期连续的买入卖出，消除中间的fee，将多次买入卖出合并为1次。
还需要考虑收益要大于fee才值得买入。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int prices_size = prices.size();
        int min_price = prices[0];
        int income = 0;
        for (int i = 0; i < prices_size; ++i) {
            if (prices[i] < min_price) { // 找股价的低谷入手
                min_price = prices[i];
            }

            if (prices[i] - min_price - fee > 0) { // 如果能收益，则出售。注意：在一个上升期连续出售视为一次出售，减少fee
                income += prices[i] - min_price - fee;
                min_price = prices[i] - fee; // 如果已经收过一次fee，还处于上升阶段，后续的连续买入卖出视为一次，消除中间的fee
            }
        }
        return income;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

24. 监控二叉树

968. 监控二叉树

为了使监控器的数量尽可能少，叶结点应该不放监控器，因为间格一层放监控器的话，最终会是叶结点没有被监控到或者根节点没有被监控到，显然如果根结点没有被监控到，只需要再放一个监控器，而叶结点最坏情况要加$2^{(n-1)}$个监控。所以叶结点不放监控。
根据上面的思路，叶结点的状态已经确定了，所以利用后序遍历，每个访问到的结点，其子节点的状态已知，可以根据子节点是否被监控，或者子节点是否是监控器来判断自己的状态。
代码细节如下：

/**
 * 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 monitor_cnt = 0;

    int postorder_traversal(TreeNode* root) { // 后续遍历,返回前一个结点的状态
        if (root == NULL) return 2; // 空结点不做考虑，只用来判断叶子节点，置为2，方便处理
        int left = postorder_traversal(root->left);
        int right = postorder_traversal(root->right);

        if (left == 2 && right == 2) return 0; // 叶子节点返回 0，不在叶子放监控

        if (left == 0 || right == 0) { // 两个子节点都未被覆盖，需要添加一个monitor，当前结点状态改为 1
            monitor_cnt++;
            return 1; 
        }
        
        if (left == 1 || right == 1) return 2; // 如果子结点有监控，则自己被覆盖
        
        return -1; // 上面覆盖了所有情况，不应该走到这里
    }

    int minCameraCover(TreeNode* root) {
        if (postorder_traversal(root) == 0) monitor_cnt++; // 如果回到根节点，发现根节点没有被监控，则根节点放一个监视器
        else cout << "error0" << endl;
        return monitor_cnt;
    }
};
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