题目解析
* 输入输出:输入一个正整数 nnn;输出一个整数,表示在区间 [1,n][1, n][1,n] 中所有数位都相同的"优美正整数"的个数。
* 数据范围:1≤n≤20251 \leq n \leq 20251≤n≤2025,数值范围较小,最多为四位数。
* 复杂度要求:时间复杂度 O(n⋅d)O(n \cdot d)O(n⋅d)(ddd 为数字位数,最大为 444),空间复杂度 O(d)O(d)O(d),均在可接受范围内。
* 算法知识点:字符串处理、模拟枚举、数位特性判断
思路解析
1. 优美数字的判定:一个正整数是优美的,当且仅当其十进制表示的每一位数字都相同(如 6,99,11116, 99, 11116,99,1111)。
2. 字符串比对法:将整数转换为字符串,构造一个与原字符串等长、且全部由首字符填充的新字符串。若两字符串相等,则说明原数字所有数位相同。
3. 暴力枚举:由于 n≤2025n \leq 2025n≤2025,直接遍历 111 到 nnn 的每个整数,调用判定函数统计符合条件的个数即可。
完整代码