leetcode_357

Golang:

思路：简单DP，这里可以注意到，当n>10，即这个数字的长度>10后，所有这个长度的数字都会有重复的现象发生，所以也可以直接穷举。

代码如下：

DP的放在这里，双百时空间复杂度

func countNumbersWithUniqueDigits(n int) int {
    if n<0{
        return 10
    }
    arr1:=make([]int,11)
    arr1[0],arr1[1]=1,10
    temp:=9
    flag:=9
    for i:=2;i<len(arr1);i++{
        temp*=flag
        flag--
        arr1[i]=temp+arr1[i-1]
    }
    if n>=10 {
        return arr1[10]
    }else{
        return arr1[n]
    }
}

穷举的放在这里：时间复杂度100%，空间89%，不太能理解。。。

func countNumbersWithUniqueDigits2(n int) int {
    if n<0 {
        return 10
    }
    arr:=[]int{1,10,91,739,5275,32491,168571,712891,2345851,5611771,8877691}
    if n>=10{
        return arr[10]
    }else{
        return arr[n]
    }
}

有疑问加站长微信联系（非本文作者）