357 计算每个数字不同的位数(递归、组合式)
1. 问题描述:
给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10 ^ n 。
示例:
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的所有数字。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-numbers-with-unique-digits
2. 思路分析:
① 分析题目可以知道这道题目类似于全排列,只是这个全排列有点特殊,对于当前的n位数字并不是使用到0-9的全部数字,只是使用到了0-9数字中的某些数字,但是本质上是一样的,所以处理方式也是差不多的,只是在细节的处理上有所差别。全排列中使用的数字也是不能够重复的,在生成全排列的过程中使用vis列表来标记哪些数字之前是已经被访问过的。对于这道题目来说也是一样的,为了生成的数字是没有重复的所以使用一个长度为10的vis列表来标记0-9中哪些数字是之前已经访问过的,只要是当前位置标记过了那么下一次就不能够使用这个数字了,这样就可以避免重复数字的问题。对于当前的位置i,尝试vis列表中没有被访问过的数字,所以可以尝试0-9中没有被访问过的数字,根据这个特点那么可以在for循环中结合vis列表的访问情况进行递归。
② 在递归的过程中需要注意的是数字的首位是不能够为0的,所以在递归的过程中如果发现首位是0的情况下需要跳过0这个数字,尝试其他的数字,递归的方法中需要传递变量n,表示当前生成的是几位数字的排列,标记列表vis用来标记当前使用过的数字情况,记录当前递归到n位数字的第几位的变量cur,这个变量可以作为递归的出口,当发现当前的数字已经有n位了那么就可以计数返回返回到上一层了。可能力扣的数据量并不是特别大,当n = 10的时候电脑已经计算不出结果了,但是上去还是通过了
③ 除了使用递归的方法求解之外,可以发现这道题目其实是一个排列组合问题,可以得到:
f(0)=1
f(1)=10
f(2)=9*9+f(1)
f(3)=9*9*8+f(2)
f(4)=9*9*8*7+f(3)
首位是不可以为0的所以有9种取法,第二位也是有9中取法,第三位有8种取法....每一位依次递减,按照这个规律依次计算结果进行累加即可解决
3. 代码如下:
from typing import List
class Solution:
res = 0
# rec变量是用来记录生成n位数字的结果, 可以作为辅助变量来输出看结果是否正确
def dfs(self, n: int, cur: int, vis: List[int], rec: str):
if cur == n:
self.res += 1
# print(rec)
return
# 尝试当前的数字i
for i in range(10):
# 首位是0那么需要跳过
if cur == 0 and i == 0: continue
# 之前没有使用过这个数字那么当前就可以使用这个数字, 这样就可以避免重复的问题
if vis[i] == 0:
vis[i] = 1
self.dfs(n, cur + 1, vis, rec + str(i))
# 回溯, 当前位置尝试其他未被使用过的数字
vis[i] = 0
# 利用vis列表来记录当前哪些数字是已经被访问过的
def countNumbersWithUniqueDigits(self, n: int) -> int:
vis = [0] * 10
# dfs方法是计算当前有i位数字的排列所以最终需要将位数为0~n的结果相加起来
for i in range(n + 1):
self.dfs(i, 0, vis, "")
return self.res
排列组合:
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
res = 1
for i in range(n):
t, cur = i, 9
for j in range(t):
cur *= (9 - j)
res += cur
return res