CountNumbersWithUniqueDigits [source code]
public class CountNumbersWithUniqueDigits {
static
/******************************************************************************/
class Solution {
public int countNumbersWithUniqueDigits(int n) {
int[] counts = new int[11];
if (n == 0)
return 1; //tricky corner case
counts[1] = 10;
for (int i = 2; i < 11; i++)
counts[i] = 9 * permute(9, i - 1);
int res = 0;
for (int i = 1; i <= n; i++)
res += counts[i];
return res;
}
public int permute(int n, int k) {
int res = 1;
for (int i = 0; i < k; i++)
res *= n--;
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
CountNumbersWithUniqueDigits.Solution tester = new CountNumbersWithUniqueDigits.Solution();
int[] inputs = {
2, 91,
0, 1,
};
for (int i = 0; i < inputs.length / 2; i++) {
int n = inputs[2 * i];
int ans = inputs[1 + 2 * i];
System.out.println(Printer.separator());
int output = tester.countNumbersWithUniqueDigits(n);
System.out.println(
Printer.wrapColor(n, "magenta") +
" -> " + output +
Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
);
}
}
}
总体来说是一个很简单的题目, 数学上理解就行了. 对应于每一个digit位数, 直接计算对应的count数量, 这个数量就是排列组合计算一下就行了, 很基础的题目; 最后的速度是0ms (10%);
注意这里, OJ认为input是0的时候结果应该是1, 这个我还真的不怎么理解为什么, 不过不管了, 一个Corner Case, 他说啥是啥吧.
这题目标签里面还有些什么DP和backtracking什么的, 这些我也没有去往这个方向去想. 还有hint, 也没来得及看;
看了一下hint上面关于backtracking做法的解释, 好像这题用backtracking应该也是可以做的; 虽然不是这一题本身的最佳解法, 不过还是值得了解一下的;
discussion最优解, 思路是差不多的:
@stupidbird911 said in JAVA DP O(1) solution.:
Following the hint. Let f(n) = count of number with unique digits of length n.
f(1) = 10. (0, 1, 2, 3, ...., 9)
f(2) = 9 * 9. Because for each number i from 1, ..., 9, we can pick j to form a 2-digit number ij and there are 9 numbers that are different from i for j to choose from.
f(3) = f(2) 8 = 9 9 * 8. Because for each number with unique digits of length 2, say ij, we can pick k to form a 3 digit number ijk and there are 8 numbers that are different from i and j for k to choose from.
Similarly f(4) = f(3) 7 = 9 9 8 7....
...
f(10) = 9 9 8 7 6 ... 1
f(11) = 0 = f(12) = f(13)....
any number with length > 10 couldn't be unique digits number.
The problem is asking for numbers from 0 to 10^n. Hence return f(1) + f(2) + .. + f(n)
As @4acreg suggests, There are only 11 different ans. You can create a lookup table for it. This problem is O(1) in essence.
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
int res = 10;
int uniqueDigits = 9;
int availableNumber = 9;
while (n-- > 1 && availableNumber > 0) {
uniqueDigits = uniqueDigits * availableNumber;
res += uniqueDigits;
availableNumber--;
}
return res;
}
不过他的这个计算稍微麻烦了一点; 我的就是他后面说的lookup的做法; 他这个其实就是用一个类似计算DP的方法, 每一个iteration(Bottom-Up的方式)计算DP的一个entry, 然后同时完成一个collect的过程; 代码写的还是很简练的;
backtracking做法:
public class Solution {
public static int countNumbersWithUniqueDigits(int n) {
if (n > 10) {
return countNumbersWithUniqueDigits(10);
}
int count = 1; // x == 0
long max = (long) Math.pow(10, n);
boolean[] used = new boolean[10];
for (int i = 1; i < 10; i++) {
used[i] = true;
count += search(i, max, used);
used[i] = false;
}
return count;
}
private static int search(long prev, long max, boolean[] used) {
int count = 0;
if (prev < max) {
count += 1;
} else {
return count;
}
for (int i = 0; i < 10; i++) {
if (!used[i]) {
used[i] = true;
long cur = 10 * prev + i;
count += search(cur, max, used);
used[i] = false;
}
}
return count;
}
}
注意他对n > 10情况的处理: 一个recursion来处理掉, 还是很简练的; 在主函数里面的for循环里面, 对于used的undo操作非常明显的是backtracking的标志: undo the decisions (for this node's subtree).
他这里为什么要有这个prev参数刚开始没有看懂. 一个参数看不懂, 直接的思路当然就是代码里面去找它是怎样被update和use的; 这里我们可以看到, prev唯一被use的地方其实就是base case里面和max进行对比来决定termination; 这个做法就很奇怪了, 有必要这么麻烦吗? 这个recursion的深度限制其实就是, no more distinct digits available to use就可以了; 下面有人就给出了一个改进的做法;
public class Solution {
public int countNumbersWithUniqueDigits(int n) {
int count = 0;
if (n == 0) return 1;
boolean[] flags = new boolean[10];
count += countNumbersWithUniqueDigits(n-1);
for (int i = 1; i < 10; i++) {
flags[i] = true;
count += search(n-1, flags);
flags[i] = false;
}
return count;
}
public int search(int n, boolean[] flags) {
if (n == 0) {
return 1;
}
int count = 0;
for (int i = 0; i < 10; i++) {
if (flags[i] == false) {
flags[i] = true;
count += search(n-1, flags);
flags[i] = false;
}
}
return count;
}
}
另外还是注意这里recursion返回值的设定, 使用count这个int作为返回值在这里是合理的;
另外这个算法好像除了一个recursion深度的控制技巧, 其他的基本就没有什么太大的难度了;
另外一个backtracking的写法:
public class Solution {
public static int countNumbersWithUniqueDigits(int n) {
HashSet<Integer> alreadyHave = new HashSet<>();
return countNoneRepeat(n,alreadyHave);
}
public static int countNoneRepeat(int n, HashSet<Integer> alreadyHave) {
if (n < 1) {
return 1;
}
int result = 0;
for (int i = 0; i < 10; i++) {
if (!alreadyHave.contains(i)) {
alreadyHave.add(i);
result += countNoneRepeat(n-1,alreadyHave);
alreadyHave.remove(i);
} else {
if (i == 0 && alreadyHave.size() == 1) {
alreadyHave.remove(0);
result += countNoneRepeat(n-1,alreadyHave);
}
}
}
return result;
}
}
这几个backtracking的其实都是判断leaf: 只有leaf可以return 1, 其他的internal node做的只是直接将下面返回上来的结果上浮;
这个是另外一个版本的改写, 跟前面的基本差不多, 只不过这个flag用bit而非array来实现了;
public class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n > 10) return countNumbersWithUniqueDigits(10);
long max = (long)Math.pow(10, n);
int used = 0;
int count = 1; // 0
for (int i = 1; i < 10; i++) {
used ^= (1 << i);
count += helper(i, max, used);
used ^= (1 << i);
}
return count;
}
private int helper(long pre, long max, int used) {
int count = 0;
if (pre < max) {
count++;
} else {
return count;
}
for (int i = 0; i < 10; i++) {
if ((used >>> i & 1) == 1) continue;
used ^= (1 << i);
long cur = 10 * pre + i;
count += helper(cur, max, used);
used ^= (1 << i);
}
return count;
}
}
另外这个题目的discussion里面居然看到好多人不太理解backtracking(并不是古老的帖子, 很多都是一个月内的), 看来这个东西还是, 不好说; 反正我自己掌握了就好; 这个backtracking算法我自己写应该还是能写出来的, 未必能非常快, 但是应该还是写的出来的;
Problem Description
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.
Difficulty:Medium
Total Accepted:36.6K
Total Submissions:79.7K
Contributor: LeetCode
Companies
google
Related Topics
dynamic programming backtracking math
Hide Hint 1
A direct way is to use the backtracking approach.
Hide Hint 2
Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
Hide Hint 3
This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
Hide Hint 4
Let f(k) = count of numbers with unique digits with length equals k.
Hide Hint 5
f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2) [The first factor is 9 because a number cannot start with 0].