【Leetcode】Count Numbers with Unique Digits

题目链接:https://leetcode.com/problems/count-numbers-with-unique-digits/

题目:
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])

Hint:

A direct way is to use the backtracking approach.
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.
This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
Let f(k) = count of numbers with unique digits with length equals k.
f(1) = 10, …, f(k) = 9 * 9 * 8 * … (9 – k + 2) [The first factor is 9 because a number cannot start with 0].

思路:
递推方程都给了,傻子采取回溯。。= =。。而且回溯看起来好难的模样。。

算法:

public int countNumbersWithUniqueDigits(int n) {
if (n == 0)
return 1;
int count = 0;
for (int i = 1; i <= n; i++) {// 求每位有多少unique digits
count += cal(i);
}
return count;
}

public int cal(int k) {
int sum = 9;
if (k == 0)
return 0;
if (k == 1)
return 10;
for (int i = 11 - k; i <= 9; i++) {
sum *= i;
}
return sum;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【Leetcode】Count Numbers with Unique Digits

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡