LeetCode_动态规划_数位 dp_困难_1012.至少有 1 位重复的数字

妖狐艹你老母 2023-10-08 20:53 92阅读 0赞

#### 目录 ####

*  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 <= 109

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

## 2.思路 ##

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

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

## 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<Character> 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/numbers-with-repeated-digits/solution/zhi-shao-you-1-wei-zhong-fu-de-shu-zi-by-0mvu/