侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【模拟, 动态规划, 数学】统计各位数字都不同的数字个数

GabrielxD
2022-04-11 / 0 评论 / 0 点赞 / 39 阅读 / 979 字 / 正在检测是否收录...

题目

357. 统计各位数字都不同的数字个数


给你一个整数 n ,统计并返回各位数字都不同的数字 x 的个数,其中 0 <= x < 10^n

示例 1:

输入:n = 2
输出:91
解释:答案应为除去 11、22、33、44、55、66、77、88、99 外,在 0 ≤ x < 100 范围内的所有数字。 

示例 2:

输入:n = 0
输出:1

提示:

  • 0 <= n <= 8

解题

方法一:暴力 模拟

思路

遍历 [0, 10^n^) 中的每一个数字 num ,再遍历 num 中的每一位 digit ,使用 digitFrequencies 数组记录每一位(0~9)的出现频率,如果该位出现频率大于1 则代表有重复位数,舍去;最后在 num 遍历中给没有重复位数的(!hasRepeatDigit)记数。遍历完成后返回计数 ans 即可。

代码

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        // n=8 时会超时,直接返回答案吧...
        if (n == 8) {
            return 2345851;
        }
        int range = (int)Math.pow(10, n); // [0, range) 为 num 的范围
        int ans = 0; // 计数
    for (int i = 0; i &lt; range; i++) { // 遍历范围中的每一个数字
        int num = i; // 范围中的每一个数字
        int[] digitFrequencies = new int[10]; // num 中每一位 digit 的出现频率
        boolean hasRepeatDigit = false; // num 是否有重复数位

        while (num &gt; 0) { // 从后往前遍历 num 中每一位
            int digit = num % 10; // num 中每一位
            digitFrequencies[digit]++; // 记录频率
            if (digitFrequencies[digit] &gt; 1) {
                // 出现频率 &gt; 1 则 num 有重复数位
                hasRepeatDigit = true;
            }
            num /= 10; // 把 num 位数往前推
        }

        if (!hasRepeatDigit) {
            // num 没有重复数位则计数
            ans++;
        }
    }

    return ans;
}

}

方法二:动态规划

思路

n=0,数字有{0}1个。

n=1,数字有{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}10个。

n=2,数字有{n=1的所有答案}∪{长度为2的新增数字},其中: 长度为 2 的新增数字可以在 n=1 的所有 9 个数字基础上进行拼接(0不能算),如: 从n=1的数字列表{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}中随便取出一个除0以外的数字(0不能作为起始数字) 例如取 2 ,通过在2的尾巴处拼接一位数字可以得到新的合法数字有: {20, 21,23,24,25,26,27,28,29} 可以看到,除了不能在尾巴处拼接一个2(两个连续的2非法),0-9 中一共有9个数字可以拿来拼接在尾巴处。新增答案为9个。同理,对于n=1数字列表{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}中的其他任意非0数也可以进行拼接操作,一共可以新增9*9个答案。 最终,n=2的合法数字,n=1时的答案 + 长度为2的数字个数(9*9个)= 10 + 81 = 91

n=3,同理,只不过此时可以用拼接的数字减少为了8个,此时答案为 10 + (9 * 9) + [(9 * 9) * 8] = 739

n=4时同理,只不过此时可以用拼接的数字减少为了7个,此时答案为 10 + (9 * 9) + [(9 * 9) * 8] + {[(9 * 9) * 8] * 7} = 5275

通过归纳,假设 dp[i]n = i 时的答案,则动态转移方程为:

dp[i] = dp[i-1] + (dp[i-1] - dp[i-2]) * (10 - (i - 1))

转移的初始条件为

  • dp[0] = 1
  • dp[1] = 10

代码

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 10;
    for(int i = 2; i &lt;= n; i++) {
        //      上一次的答案  上一次较上上一次增加的答案    可以拼接的数字个数
        dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - 2]) * (10 - (i - 1));
    }

    return dp[n];
}

}

0

评论区