电子商务网站建设自建团队,查网站备案名称,国外设计网站pinterest怎么打不开,wordpress遇到的问题#Java #贪心
开源学习资料
Feeling and experiences#xff1a;
单调递增的数字#xff1a;力扣题目链接
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。
给定一个整数 n #xff0c;返回 小于或等于 n 的最大数字
单调递增的数字力扣题目链接
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。
示例 1:
输入: n 10
输出: 9该题我首先想到的是暴力解法判断这个n是否是满足要求递增的如果不满足就n--
class Solution {public int monotoneIncreasingDigits(int n) {while(n0){if(!isIncrease(n)){n--;}else{return n;}}return n;}public boolean isIncrease(int n){while(n0){int n1 n%10;int n2 (n/10)%10;n/10;if(n1 n2){return false;}}return true;}
}
这样超过了时间限制而且一看效率就很低了。 正确的做法
class Solution {public int monotoneIncreasingDigits(int n) {char[] digits String.valueOf(n).toCharArray();int mark digits.length;for (int i digits.length - 1; i 0; i--) {if (digits[i] digits[i - 1]) {mark i;digits[i - 1]--;}}for (int i mark; i digits.length; i) {digits[i] 9;}return Integer.parseInt(new String(digits));
}}
1. 将数字转换为字符数组首先将输入的整数 n 转换为字符数组以便逐位处理。
2. 从右向左遍历从最低位开始向最高位遍历。这样做的目的是找到第一个违反单调递增规则的点。即找到第一个 digits[i] digits[i - 1] 的位置。
3. 标记并调整数字一旦找到这样的点即 digits[i] digits[i - 1]执行两个操作 • 将 digits[i - 1] 减一因为要保持整体数字的大小尽可能大但又要小于原来的 N。 • 记录当前位置 i这是因为从这一位开始到最低位的所有数字都需要被设置为 9以保证这部分是最大的单调递增数字。
4. 将标记后面的数字全部变成9从标记的位置开始将所有更低位的数字替换为 9。这是因为我们已经减少了前面的一位数字所以可以安全地将这些位设置为最大可能值9以得到最大的单调递增数字。
5. 转换回整数并返回最后将修改后的字符数组转换回整数并返回这个整数。 监控二叉树:力扣题目链接
给定一个二叉树我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。 看了题解贪心的思想没有理解到基本都是以动态规划来写的
先跳过该题等学习完动态规划再来解答。 Fighting
