357. Count Numbers with Unique Digits

liukai90 发布于2019-08-14 17:25 / 1730人阅读

摘要：题目链接和安卓解锁那道题很想，那道题步数是到，这道题是到，表示数字的位数。，每次要记录走到的位数作为，从开始。注意最后的情况，只有一位的时候算上，一位以上，首位都不可以是。滚动数组优化空间到

357. Count Numbers with Unique Digits

题目链接：https://leetcode.com/problems...

和安卓解锁那道题很想，那道题步数是m到n，
https://segmentfault.com/a/11...
这道题是1到n，表示数字的位数。backtracking，每次要记录走到的位数作为depth，从msb开始。dp[i]: # of numbers with (i+1) unique digits, dp[0] = 9, dp[i] = (n - i) * dp[i-1]，最后结果是sum(dp[i])，i = [0, n-1], 也可以dfs来做, bottom up。注意最后0的情况，只有一位的时候算上0，一位以上，首位都不可以是0。

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n == 0)  return 1;
        
        int[] dp = new int[Math.min(n, 10)];
        dp[0] = 9;
        // count 0
        int result = 1 + dp[0];
        for(int i = 1; i < Math.min(n, 10); i++) {
            dp[i] = (10 - i) * dp[i-1];
            result += dp[i];
        }
        
        return result;
    }
}

滚动数组优化空间到O(1)

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n == 0)  return 1;
        
        int dp = 9;
        // count 0
        int result = 1 + dp;
        for(int i = 1; i < Math.min(n, 10); i++) {
            dp = (10 - i) * dp;
            result += dp;
        }
        
        return result;
    }
}

服务器托管私有云 Numbers Digits h19 357服务器 unique

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66627.html

leetcode-357-Count Numbers with Unique Digits

摘要：此模型的特殊性相邻的三个值可以得到一个爆破值，相邻的两个值相当于没有值，赋予类比二分法求极值。通过二分确定具体的位置。此处二分法到极值是三个连续的数，从相邻三个数的固定值，逐次放宽范围，确定越来越宽的爆破值。此题的总结：求解最大爆破值，是一个倒序二分法问题，最终的原子结构是连续的三个数。连续的三个数，可以往上递推间隔一个数的三个数，间隔n个数的三个数特点在于：每一...

lansheng228 2019-07-30 17:36 评论0 收藏0
Sequelize Model

摘要：定义默认值和是否为空默认时间为创建时间设置为将会在数据表中添加列如果查询时该列为数据库会抛出错误如果你想在查询前检查该值是否为，看一下下面的验证部分可以是或如果多个列是相同就会变成会创建索引也可以这么创建索引主键自动增量在可以有可以通过属性定义Model import sequelize from sequelize var Foo = sequelize.define(foo, ...

andong777 2019-08-21 14:34 评论0 收藏0
30s js代码片段翻译

摘要：可否被整除使用模运算符来检查余数是否等于。数值增加序号后缀使用模运算符来查找单位数和十位数的值。这是对 github 上30s代码片段的翻译整理，由于作者的文档是通过脚本生成的，也就懒得去提pull了，整理了放到博客上供大家学习参考，后续会持续跟进翻译。 Array Array concatenation (合并参数) 使用 Array.concat() 来连接参数中的任何数组或值。...

sevi_stuo 2019-08-22 13:46 评论0 收藏0
Laravel：使用Migrations

摘要：首先利用创建一个可迁移的数据表模板，该命令运行后会在目录下生成一个文件生成的文件包含和两个方法，其中中是包含了添加表，添加列，添加索引等等一切的描述，比较简单，就是删除表，当然里面还可以有一些其他逻辑中支持的数据表列类型，做个备注，暂时 1、首先利用artisan创建一个可迁移的数据表模板，该命令运行后会在database/migrations目录下生成一个文件 php artisan...

waltr 2019-06-27 13:44 评论0 收藏0