算法训练营第三十九天 | LeetCode 738 单调递增的数字、LeetCode 968 监控二叉树

LeetCode 738 单调递增的数字

这题类似模拟，可以找出如下规律：

先将数字按位数从高位到低位存到一个整型数组中。在这个数组中，从左往右遍历，如果遇到一个两数相等，并且记录的这个变量之前没有赋过值，那么将前一个数的下标存放到该变量中。这是为了处理后一个数字需要减小造成前一个数字再次比后一个数字大的情况。当然，如果后面有一个数字比这两个数字都要大，那么这个变量就可以再次赋为-1了。如果在赋为前一个数下标之前，该变量已经被赋过值，这说明前面还有数和这两个数一样大，那么该变量的值不变就好。

上述的处理其实有些冗余，但都是方便我们在遇到前一个数大于后一个数时，能够放心地减一，并把后面的数全部置为9，这就是我们找到的规律。感兴趣的小伙伴也可以自行去推导前面一段的推导过程。

代码如下：

class Solution {public int monotoneIncreasingDigits(int n) {if (n == 0) return 0;if (n / 10 == 0 ) return n;int res = 0;int w = 0;int temp = n;while (n > 0) {n /= 10;w++;}n = temp;int[] c = new int[w];int i = w;while (n > 0) {c[i - 1] = n % 10;n/=10; i--;}int index = -1;for (i = 0; i < w; i++) {if (i + 1 < w && c[i + 1] == c[i]) {if (index == -1) index = i;}if (i + 1 < w && c[i + 1] > c[i]) {if (index != -1) index = -1;} if (i + 1 < w && c[i + 1] < c[i]) {if (index != -1) {if (c[i] > c[index]) {c[i]--;while (i + 1 < w) {c[++i] = 9;}} else {c[index]--;i = index + 1;while (i < w) {c[i++] = 9;}}} else {c[i]--;while (i + 1 < w) {c[++i] = 9;}}}}for (i = 0; i < w; i++) {res *= 10;res += c[i];}return res;}
}

LeetCode 968 监控二叉树

本题大致意思是从底往上推，若是从上往下推能节省的数目其实不大。之所以用贪心也是因为这个原因。

一个节点状态去我们分为3种：为0表示无监控也无覆盖，为1表示有覆盖，为2表示是监控。

空姐点视作有覆盖，叶子节点视作无覆盖。

分情况讨论：

左右节点其中一个为0，则当前节点必须要有监控；

左右节点都为1，当前节点无覆盖，等上层节点设监控

左右节点其中一个为2，当前节点有覆盖，返回1

.最后由于上面第二种情况和一些特别的情况，最后根节点还要再判断下。

代码如下：

class Solution {int sum = 0;
public:int state(TreeNode* root) {if (!root) return 1;if (!root->left && !root->right) return 0;int left = state(root->left);int right = state(root->right);if (left == 0 || right == 0) {sum++;return 2;}if (left == 1 && right == 1) return 0;if (left == 2 || right == 2) return 1;return 0;}int minCameraCover(TreeNode* root) {if (!root) return 0;int left = state(root->left);int right = state(root->right);if (left == 0 || right == 0) {sum++; }if (left == 1 && right == 1) sum++;return sum;}
};