目录

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

给定正整数 n，返回在 [1, n] 范围内具有至少 1 位重复数字的正整数的个数。

示例 1：
输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。

示例 2：
输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。

示例 3：
输入：n = 1000
输出：262

提示：
1 <= n <= 10⁹

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/numbers-with-repeated-digits

2.思路

（1）暴力穷举法
使用 for 循环对 [1, n] 内的每个整数 i 进行判断，如果 i 具有至少 1 位重复数字，则 res++（初始值为 0），遍历结束时返回 res 即可。但是显然该方法的时间复杂度较高，在 LeetCode 中提交时会出现“超出时间限制”的提示！

（2）动态规划 & 数位 dp
思路参考本题官方题解。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {public int numDupDigitsAtMostN(int n) {int res = 0;for (int i = 1; i <= n; i++) {if (isRepetitive(i)) {res++;}}return res;}//判断整数 num 是否具有至少 1 位重复数字public boolean isRepetitive(int num) {String str = String.valueOf(num);Set set = new HashSet<>();for (int i = 0; i < str.length(); i++) {char c = str.charAt(i);if (!set.contains(c)) {set.add(c);} else {return true;}}return false;}
}

//思路2————动态规划
class Solution {int[][] dp;public int numDupDigitsAtMostN(int n) {String sn = String.valueOf(n);dp = new int[sn.length()][1 << 10];for (int i = 0; i < sn.length(); i++) {Arrays.fill(dp[i], -1);}return n + 1 - f(0, sn, 0, true);}//返回 [1, n] 内没有重复数字的正整数个数public int f(int mask, String sn, int i, boolean same) {if (i == sn.length()) {return 1;}if (!same && dp[i][mask] >= 0) {return dp[i][mask];}int res = 0, t = same ? (sn.charAt(i) - '0') : 9;for (int k = 0; k <= t; k++) {if ((mask & (1 << k)) != 0) {continue;}res += f(mask == 0 && k == 0 ? mask : mask | (1 << k), sn, i + 1, same && k == t);}if (!same) {dp[i][mask] = res;}return res;}
}