未分類

Count Numbers with Unique Digits

Backtracking, DynamicProgramming, Go, LeetCode, Math

Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

For example:

1
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])
提示 解題應用
Math 規律觀查

Default:

1
2
3
func countNumbersWithUniqueDigits(n int) int {
}

解答思路:

一開始的想法是先找出所有數字出現相同的情況再用總數減去就好，不過這樣一來反而會變的更複雜，其實就只要直接用排列組合的方式去找出各長度數字皆不同的組合就好，當k(當作出現的數字長度)為1時有10種組合，為2時有9*9種組合(開頭不得為0，結尾不得與開頭重覆故[10-1]*[10-1])，為3時則是9*9*8(結尾不得與前面重覆再減1)，為4時是9*9*8*7其它以此類推，而當數字的位數超過10位數，到第十一位數時必定出現重覆只會有0種組合(因為0~9只有10個)，最後只要將各長度數字不同的組合數量做加總就會是我們要的結果。

程式碼解說:

在理解了整個規律之後便能很容易的將程式碼完成，先篩選掉n大於10(0種組合)與等於0(1種組合: 1)及等於1(10種組合: 0~9)的情況，最後就是加總9*9+9*9*8+9*9*8*7+…至結果之中(n介於2~10之間)，要注意到的是不要忘了加上n為1的情況(10種組合)，所以一開始才將結果的初始值設為10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if n > 10 {
	return 0
} else if n == 0 {
	return 1
} else if n == 1 {
	return 10
}
tmp := 9
num := 9
result := 10
for n >= 2 {
	num *= tmp
	result += num
	tmp--
	n--
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func countNumbersWithUniqueDigits(n int) int {
	if n > 10 {
		return 0
	} else if n == 0 {
		return 1
	} else if n == 1 {
		return 10
	}
	tmp := 9
	num := 9
	result := 10
	for n >= 2 {
		num *= tmp
		result += num
		tmp--
		n--
	}
	return result
}

總結:

要找出0到10^n之間有多少個值不會出現重覆的數字，其實就只要直接用排列組合的方式去找出各長度數字皆不同的組合就好，當k(當作出現的數字長度)為1時有10種組合，為2時有9*9種組合(開頭不得為0，結尾不得與開頭重覆故[10-1]*[10-1])，為3時則是9*9*8(結尾不得與前面重覆再減1)，為4時是9*9*8*7其它以此類推，而當數字的位數超過10位數，到第十一位數時必定出現重覆只會有0種組合(因為0~9只有10個)，最後只要將各長度數字不同的組合數量做加總就會是我們要的結果。

分享到