LeetCode-357. Count Numbers with Unique Digits

[ninehills]

问题

https://leetcode.com/problems/count-numbers-with-unique-digits/description/

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

思路

动态规划的思路，可以看到从随着n的增加，是有规律的

n = 0, r(0) = 1
n = 1, r(1) = 10
n = 2, r(2) = 9 * 9 + r(1) // 当n=2时，首先是r(1)，然后加上两位数的解 - 首位有9种可能（不含0），次位也有9种可能（不含首位）
n = 3, r(3) = 9 * 9 * 8 + r(2) + r(1) // // 当n=2时，首先是r(1) + r(2)，然后加上三位数的解 - 首位有9种可能（不含0），次位也有9种可能（不含首位），再次位有8种可能（不含首位和次位）
n = 11, r(11) = 9 * 9 * 8 * ... * 2 * 1 * 0 + r(10) + ... + r(1)

解答

package main

import "fmt"

func countNumbersWithUniqueDigits(n int) int {
    if (n == 0) {
        return 1
    }
    var ret = 10
    var k = 9
    for i := 2; i <= n && i <= 10; i++ {
        k = k * (9 - i + 2)
        ret += k
    }
    return ret
}

// ----------------------

func main() {
    fmt.Println(countNumbersWithUniqueDigits(9))
}

[ninehills]

4