0357. Count Numbers With Unique Digits

357. Count Numbers with Unique Digits #

题目 #

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

Example:

Input: 2
Output: 91 
Explanation: 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,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10^n 。

解题思路 #

  • 输出 n 位数中不出现重复数字的数字的个数
  • 这道题摸清楚规律以后,可以直接写出最终所有答案,答案只有 11 个。
  • 考虑不重复数字是如生成的。如果只是一位数,不存在重复的数字,结果是 10 。如果是二位数,第一位一定不能取 0,那么第一位有 1-9,9种取法,第二位为了和第一位不重复,只能有 0-9,10种取法中减去第一位取的数字,那么也是 9 种取法。以此类推,如果是三位数,第三位是 8 种取法;四位数,第四位是 7 种取法;五位数,第五位是 6 种取法;六位数,第六位是 5 种取法;七位数,第七位是 4 种取法;八位数,第八位是 3 种取法;九位数,第九位是 2 种取法;十位数,第十位是 1 种取法;十一位数,第十一位是 0 种取法;十二位数,第十二位是 0 种取法;那么第 11 位数以后,每个数都是重复数字的数字。知道这个规律以后,可以累积上面的结果,把结果直接存在数组里面,暴力打表即可。O(1) 的时间复杂度。

代码 #


package leetcode

// 暴力打表法
func countNumbersWithUniqueDigits1(n int) int {
	res := []int{1, 10, 91, 739, 5275, 32491, 168571, 712891, 2345851, 5611771, 8877691}
	if n >= 10 {
		return res[10]
	}
	return res[n]
}

// 打表方法
func countNumbersWithUniqueDigits(n int) int {
	if n == 0 {
		return 1
	}
	res, uniqueDigits, availableNumber := 10, 9, 9
	for n > 1 && availableNumber > 0 {
		uniqueDigits = uniqueDigits * availableNumber
		res += uniqueDigits
		availableNumber--
		n--
	}
	return res
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者