做的网站为什么手机上搜不到,网站建设的公司联系方式,如何网站网站做代理,电子商务网站建设与维护实训LeetCode 738 单调递增的数字
这题类似模拟#xff0c;可以找出如下规律#xff1a;
先将数字按位数从高位到低位存到一个整型数组中。在这个数组中#xff0c;从左往右遍历#xff0c;如果遇到一个两数相等#xff0c;并且记录的这个变量之前没有赋过值#xff0c;那么…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;}
};
