题目如下:
Given a positive integer
N
, return the number of positive integers less than or equal toN
that have at least 1 repeated digit.Example 1:
Input: 20 Output: 1 Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.Example 2:
Input: 100 Output: 10 Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.Example 3:
Input: 1000 Output: 262Note:
1 <= N <= 10^9
解题思路:题目要求出至少有一个重复元素的数字的总数,我们可以先求没有重复元素的数字的总数,再用N减去这个总数即可。怎么求出没有重复元素的数字的个数呢?假设Input = 53254,首先求出位数小于Input时满足条件的数字总数
位数为1:一共有9种 (1,2,3.... 9)
位数为2:最高位不能为0,只能在1~9种任选一个,第二位在1~9中只有8种选择,但是也可以为0,所以也是9选1,总数为9*9,
位数为3:一共有 9 * 9 * 8
位数为4:很明显可以看出规律了,总数为9 * A(9, 4-1)
位数等于Input时的情况会麻烦一些。我的方法是首先求以5XXXX这种格式的总数,然后再求出53XXX这种格式的总数,直到最后求出总数。
代码如下:
class Solution(object): def numDupDigitsAtMostN(self, N): """ :type N: int :rtype: int """ def calcPerm(v1,v2): v = 1 while v1 > 0: v *= v2 v2 -= 1 v1 -= 1 return v ln = list(str(N)) res = 1 if len(list(str(N))) == len(set(list(str(N)))) else 0 #判断N是否包含重复元素 dic_used = [int(ln[0])] for i in range(1,len(ln)): count = 0 for j in range(0,int(ln[i])): if j not in dic_used: count += 1 res += count * calcPerm(len(ln) - i - 1, 10 - i - 1) if int(ln[i]) in dic_used: break dic_used.append(int(ln[i])) # for i in range(1,len(ln)+1): if i != len(ln): res += (9 * calcPerm(i-1,9)) else: count = int(ln[0]) - 1 res += (count * calcPerm(i - 1, 9)) # return N - res