百度竞价推广联系方式,seo优化推广,零基础源码建设网站,怎么给网站添加站点统计视频讲解#xff1a; 贪心算法#xff0c;思路不难想#xff0c;但代码不好写#xff01;LeetCode:738.单调自增的数字_哔哩哔哩_bilibili 贪心算法#xff0c;二叉树与贪心的结合#xff0c;有点难...... LeetCode:968.监督二叉树_哔哩哔哩_bilibili 738. 单调递增的数字… 视频讲解 贪心算法思路不难想但代码不好写LeetCode:738.单调自增的数字_哔哩哔哩_bilibili 贪心算法二叉树与贪心的结合有点难...... LeetCode:968.监督二叉树_哔哩哔哩_bilibili 738. 单调递增的数字
思路本题的关键在于降位。对于数n如果其本身满足题目的单调要求那么直接返回结果即可如果不满足那么他就要通过降位来寻找最大且合适的数这里的降位的意思就是十位以上的位数大小进行缩减。通过观察个位数字总是可以取到9但是十位就需要在原来n十位的k基础上在k-1与9之间选择一个合适的这里的k-1就是降位他将一个十位借给了个位从而可以让个位取到9并且也满足了个位一定大于等于十位我们采用这种降维的思路以及位数越大持续递增的思路不断进行解题。
但是我最后的时间开销明显非常大对其进行优化。我们可以看出在进行降位总是当前的某一位与其前一位出现了单调性不满足因此需要大的一位降低1使得后一位可以取得更多的数然后满足单调增的需求。因此我们的目标就是找所以不满足单调性的地方并且不满足单调性的k位置开始k与k-1出现不满足之后的数全部可以取9然后k-1位进行降位。那么反复寻找出现错误的地方然后不断更新或者降位即可输出结果。那么我们归结一下最快的贪心策略就是找到第一个出现不满足单调的位数t然后t1到末尾全部可以赋值为9然后t位降位降位后不满足大小的话则从t位按照这个思路再继续向前。
降位位置之后可以全部取9是本题的关键。
// 时间复杂度O(n^2)n是n这个数的位数
// 空间复杂度O(n)class Solution {ListInteger list new ArrayList();public int monotoneIncreasingDigits(int n) {if(judge(n)){return n;}char[] ch new char[list.size()];boolean flag true;int back 9;int len list.size()-1;// 最后一位肯定是9ch[len--] 9;// 由于自降一个10位所以十位上一定需要比先前的十位来的小for(int ilen; i0; i--){int num flagtrue? Math.min(list.get(i)-1, back):Math.min(list.get(i), back);if(i0 list.get(i-1) num){ch[len--] (char) (0num);back num;flag false;}else if(i0 list.get(i-1) num){for(int jlen; jlist.size(); j)ch[j] 9;ch[len--] 9;back 9;flag true;}else if(i0)ch[len--] (char) (0num);}return Integer.parseInt(new String(ch));}public boolean judge(int n){boolean flag true;int cur 0;int back -1;while(n1){if(back -1){back n%10;list.add(0, back);n/10;continue;}cur n%10;list.add(0, cur);if(cur back)flag false;back cur;n/10;}return flag;}
}
968.监控二叉树
思路本题是看了题解写的这道题很明显可以得到自底向上遍历树来确定什么节点该设置监控。另外确定遍历的方式非常的重要我初始采用层次遍历的方式确实可以满足测试用例但是在验证所有测试用例的时候发现简单的层次遍历规律根本无法满足所有的情况还是应该自底向上采用深度遍历的方式实现。本题直接自我多多记忆多多体会。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
// 时间复杂度O(n)n是节点的个数
// 空间复杂度O(1)class Solution {int res0;public int minCameraCover(TreeNode root) {// 对根节点的状态做检验,防止根节点是无覆盖状态 .if(minCame(root)0){res;}return res;}/**节点的状态值0 表示无覆盖1 表示 有摄像头2 表示有覆盖后序遍历根据左右节点的情况,来判读 自己的状态*/public int minCame(TreeNode root){if(rootnull){// 空节点默认为 有覆盖状态避免在叶子节点上放摄像头return 2;}int leftminCame(root.left);int rightminCame(root.right);// 左右节点都覆盖了的话, 本节点状态是无覆盖则位于监控节点父节点的父节点if(left2 right2){//(2,2)return 0;}else if(left0||right0){// 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头// (0,0) (0,1) (0,2) (1,0) (2,0)// 状态值为 1 摄像头数 ;res;return 1;}else{// 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头// 那么本节点就是处于被覆盖状态return 2;}}
}
