1012. 至少有 1 位重复的数字

Difficulty: 困难

给定正整数 N，返回小于等于 N 且具有至少 1 位重复数字的正整数的个数。

示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

1
2

输入：1000
输出：262

提示：

  1. 1 <= N <= 10^9

Solution

Language: ****

解题思路

将问题转化为 至少有重复元素的序列 = N - 没有出现重复元素的序列

我的解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

int dp[15][10];
class Solution {
public:
string s;
    int numDupDigitsAtMostN(int n) {
        s = to_string(n);
        memset(dp,-1,sizeof dp);
       
        return n- dfs(0,   1,0) +1;
    }
    unordered_map<int,int> mp;
    int dfs(int pos,int limit,int len) {
        if(pos == s.size()) return 1;
        if(!limit && dp[pos][len] != -1) return dp[pos][len];
        // len 表示生成的序列的长度
        int res = 0;
        //len = 0 ，就可以表示 有前导0
        int h = limit? s[pos] -'0' : 9;
        int b = s[pos] -'0';
        for(int i=0;i<=h;++i) {
            if(len ==0  &&  i == 0) {
                //还是前导0‘’
                res += dfs(pos+1,limit && b==i  ,len);
            }else if(mp[i]==0) {
                mp[i] = 1;
                res += dfs(pos+1,limit && b == i, len+1);
                mp[i] = 0;
            }
        }
        if(!limit) dp[pos][len ] = res;
        return res;
    }




};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int dp[11][1050][2][2][2];
class Solution {
public:
    string s;
    int dfs(int i, int mask, int lim, int lz, bool ok) {
        if(i == s.size()) return ok;
        int &v = dp[i][mask][lim][lz][ok];
        if(~v) return v;
        v = 0;

        int up = lim ? s[i] - '0' : 9;
        for(int j = 0; j <= up; j += 1) {
            if(lz) {
                v += dfs(i + 1, j ? (mask | 1 << j) : 0, lim && j == up, lz && j == 0, ok);
            } else {
                v += dfs(i + 1, mask | 1 << j, lim && j == up, lz, ok || (mask >> j & 1));
            }
        }
        return v;
    }
    int numDupDigitsAtMostN(int n) {
        s = to_string(n);
        memset(dp, -1, sizeof dp);
        return dfs(0, 0, 1, 1, 0);
    }
};