LeetCode（357）计算各个位数不同的数字个数

本题来自LeetCode：357. 计算各个位数不同的数字个数

题目详情

给定一个非负整数 n，计算各位数字都不同的数字 x的个数，其中 0≤x10^n 。

示例:

输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

分析思路

由于只有`0123456789`这十个数字，当`n 10`时，无论如何都会产生重复数字，故`n 10`的个数和`n = 10`的个数相等；

计算`各位数字都不同的数字`，即从`10`个数字中取`n`个不同数字的所有排列数，即A(10, n);需要注意的是首位数字不能为`0`，否则就不满`n`位数了；

需要计算区间`[0, 10^n)`之间数字都不同的数字的个数，故需要将`[0, n]`位数的排列数累加起来。

定义`count[n]`为`[0, 10^n)`之间数字都不同的数字的个数。

综上可得以下表达式：

count[n] = count[n -1] + A(10, n) * 9 / 10,    0 = n = 10
count[n] = count[10],                10  n
其中A(10, n)是从10个不同元素中取出n个元素的排列数

题目解答

根据以上分析可以轻松写出以下解答：

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
         // count[n]记录区间[0, 10^n)的个数
         int[] count = new int[11];
         // n = 0时，区间为[0, 1)
         count[0] = 1;
         // n至多为10
         for(int i = 1; i = Math.min(n, 10); i ++) {
            // i位数的排列总数，即区间[10^(i - 1), 10 ^ i)
            int arrangeWithI = arrangeWithN(i);
            // i位数的累计排列数，即区间[0, 10 ^ i)
            count[i] = count[i - 1] + arrangeWithI;
         }
         return n  10 ? count[10] : count[n];

    }
    private int arrangeWithN(int n) {
        // 首位不能为0，故只剩123456789这九个数字
        int arrange = 9;
        int remainDigits = 9;
        while(--n  0) {
            arrange *= remainDigits;
            remainDigits --;
        }
        return arrange;
    }
}

进一步可以发现：

数组`count`，其实没有必要，采用累计和`sum`替换；

计算`i`位数的排列总数`arrangeWithN`这一步，存在重复计算，可以进行优化；整体优化后：

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
         int sum = 1;
         // 当前位数数字的排列数
         // 初始值：1位数时的排列数
         int currentArrange = 9;
         // 剩余可选数字数
         int remainDigits = 9;
         // n至多为10
         for(int i = 1; i = Math.min(n, 10); i ++) {
            // i位数的累计排列数，即区间[0, 10 ^ i)
            sum += currentArrange;
            // (i + 1)位数的排列数，即区间[10^i, 10 ^ (i + 1))
            currentArrange *= remainDigits;
            // 可用数字数减一
            remainDigits --;
         }
         return sum;
    }
}

原文始发于微信公众号（xiaogan的技术博客）：