博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
统计0~10^n范围没有重复的个数 Count Numbers with Unique Digits
阅读量:6626 次
发布时间:2019-06-25

本文共 1851 字,大约阅读时间需要 6 分钟。

hot3.png

问题:

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

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])

解决:

【题意】计算有n位数的数字在0~10^n范围内,各个位数字不同的个数。

① 直接计算。

n = 1 ----> 10 <--- 没有重复

n = 2 ----> 91 <--- 排除11,22,33,44,55,66,77,88,99

n = 3 ----> 739 <--- 排除类似111、121、112、211的数字

当n = 1时因为只有一个数字,所以0 - 9都是答案.当n >= 2时,最高位可以为1 - 9任意一个数字,之后从i = 2开始可以选择的数字个数依次为9, 8, 7, 6...,(9 - i + 2)上一位选一个下一位就少了一种选择。

class Solution {//0ms

    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        int res = 10;
        int tmp = 9;
        for (int i = 2;i <= n;i ++){
            tmp *= (9 - i + 2);
            res += tmp;
        }
        return res;
    }
}

② 动态规划。

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)

class Solution {

    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int res = 10;//n = 1时
        int availableNumber = 9;
        int uniqueDigit = 9;
        while(n -- > 1 && availableNumber >= 1){
            uniqueDigit *= availableNumber;
            res += uniqueDigit;
            availableNumber --;
        }
        return res;
    }
}

转载于:https://my.oschina.net/liyurong/blog/1595444

你可能感兴趣的文章
【IOS-COCOS2D-X 游戏开发之二】【必看篇】总结阐述COCOS2D-X与COCOS2D-IPHONE区别;
查看>>
eoLinker-API_Shop_通讯服务类API调用的代码示例合集:短信服务、手机号归属地查询、电信基站查询等...
查看>>
前端面试回忆录 - 滴滴篇 - 凉面
查看>>
jxl导入Excel 切割List 并使用MyBatis批量插入数据库
查看>>
小程序开发总结
查看>>
Tomcat监听器设计思路
查看>>
管理ORACLE实例
查看>>
Confluence 6 MySQL 数据库设置准备
查看>>
Ruby 中 0/0.0 = NaN
查看>>
JEESNS数据库表设计结构
查看>>
JavaScript学习笔记:判断变量是否为undefined,判断变量和函数是否声明
查看>>
局域网访问Apache服务器
查看>>
JavaScript 闭包
查看>>
Spark算子:RDD行动Action操作(3)–aggregate、fold、lookup
查看>>
UILabel总结
查看>>
java获取当前时间前一周、前一月、前一年的时间
查看>>
话说WEB开发之页面重绘和回流
查看>>
using标识使用
查看>>
解决linux下不能上网
查看>>
nginx rewrite伪静态配置参数说明
查看>>