代码随想录Day37

Day 37 贪心算法 Part06

今日任务

• 738.单调递增的数字
• 968.监控二叉树

代码实现

738.单调递增的数字
做了这么多贪心的题，这是唯一一道自己写出来的，就是思路虽然一开始就对了，感觉没那么难，但是代码还是比较复杂，用的时间也有点长

 public int monotoneIncreasingDigits(int n) {
        LinkedList<Integer> list = new LinkedList<>();
        while (n > 0) {
            list.add(n%10);
            n = n / 10;
        }
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i + 1) > list.get(i)) {
                list.set(i + 1, Math.max(list.get(i + 1) - 1, 0));
                list.set(i, 9);
            }
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i) == 9) {
                while (i >= 0) {
                    list.set(i, 9);
                    i--;
                }
                break;
            }
        }

        int result = 0;
        for (int i = 0; i < list.size(); i++) {
            int x = list.get(i);
            for (int j = 0; j < i; j++) {
                x = x * 10;
            }
            result+=x;
        }
        return result;
    }

968.监控二叉树
直接看题解就完事了，一点思路没有

int result = 0;

    public int minCameraCover(TreeNode root) {
        int traversal = traversal(root);
        if (traversal == 0) return result + 1;
        return result;
    }

    /**
     * 递归
     * 定义有覆盖为2，无覆盖为0，有监控为1
     * @param current
     * @return
     */
    int traversal(TreeNode current) {
        if (current == null) return 2;
        int left = traversal(current.left);
        int right = traversal(current.right);
        if (left == 2 && right == 2) {
            return 0;
        }
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }
        if (left == 1 || right == 1) {
            return 2;
        }
        return -1;
    }

今日总结

1. 两天没有写总结，用昨天和今天两天补上了周二漏的，感觉确实没什么套路，除了几道区间的题比较相似以外，要么是一眼能看出来，要么是不可能看出来
2. 大模型的东西今天也学了一点，但是不多，在Mac上下载了ChatGLM3-6b（大概叫这个吧），非常慢，向量库Milvus也没装好
3. 今天早上我认为是反转，但是到了下午感觉又像反弹，人工智能不知道还能不能持续，汽车也不知道咋回事，懵懵比比。另外，今天小米汽车发布，但是也没找到合适的股票想买的，明天看情况吧。