357. Count Numbers with Unique Digits

liukai90 發布于2019-08-14 17:25 / 1811人閱讀

摘要：題目鏈接和安卓解鎖那道題很想，那道題步數是到，這道題是到，表示數字的位數。，每次要記錄走到的位數作為，從開始。注意最后的情況，只有一位的時候算上，一位以上，首位都不可以是。滾動數組優化空間到

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;
    }
}

云服務器 GPU云服務器 Numbers Digits h19 357服務器 unique

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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