代码随想录第32天 | ● 738.单调递增的数字 ● 968.监控二叉树

738.单调递增的数字

/**
 * @param {number} n
 * @return {number}
 */
var monotoneIncreasingDigits = function(n) {
            var str = n.toString();
            let flag=str.length
            var s=str.split("");
     //从后往前遍历<----，若从前往后便利的话---->，会影响前面
     //如果s[i]89
     //100  1-19  099
     //101  101   091
      for(let i=s.length-1;i>0;i--){
          if(s[i]<s[i-1]){
              flag=i
              s[i-1]--
          }
          
      }
      for(let i=flag;i<s.length;i++){
          s[i]=9
      }
      let sum=0
      for(let i=0;i<s.length;i++){
       sum+=s[i]*10**(s.length-i-1)
      }
      return sum
};

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

想法

98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数

968.监控二叉树

var minCameraCover = function (root) {
  let result = 0;
  function traversal(cur) {
    if (cur === null) {
      return 2;
    }

    let left = traversal(cur.left);
    let right = traversal(cur.right);

    // 0：该节点无覆盖
    // 1：本节点有摄像头
    // 2：本节点有覆盖
    if (left === 2 && right === 2) {
      return 0;
    }

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

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

    return -1;
  }
  // 判断root是否有覆盖，若无就加1
  if (traversal(root) === 0) {
    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

想法

// 情况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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21