LeetCode 解題紀錄 357. Count Numbers with Unique Digits

Count Numbers with Unique Digits - LeetCode

題目

給定一個數字 n，返回 1 ≤ x ≤ 10^n 中每個位數都不重複的 x 數目

限制

• 0 ≤ n ≤ 8

觀察

• 10⁰ 只有一個 (1)
• 10¹ 有 10 個 (1 2 3 4 5 6 7 8 9 10)
• 當到 2 位數以上時，就變成是個計算排列的數學問題，第一個位數不能選擇 0，所以有 9 個選擇(1~9)，而第二個位數也是有 9 個選擇(這時候 0 可以選了)，所以會有 9*9= 81，加上一位數的 10 個 81+10=91
• 依此類推 3 位數是 9*9*8，總數還要加上 9*9+10

思路

• special case 是 1
• 使用 loop 計算不同位數的排列數並加總
• 最後加上 base case 10

Trail 1

結果

時間複雜度為 O(n)，空間複雜度為 O(1)，屬於數學類型的問題，知道原理的話程式碼真的很精簡