题目描述：

LeetCode 1015. Numbers With Repeated Digits

Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

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.

Input: 1000
Output: 262

题目大意：

给定正整数N，返回不大于N的包含重复数的正整数个数。

解题思路：

排列 + 计数原理

题目可转化为求解不重复数字的个数

Python代码：

class Solution(object):
    def numDupDigitsAtMostN(self, N):
        """
        :type N: int
        :rtype: int
        """
        self.S = str(N)
        ans = self.solve(self.S, 0) + self.calc9(len(self.S) - 2)
        return N - ans
    def solve(self, S, D):
        pcnt = collections.Counter(self.S[:D] or [-1])
        if len(S) == 1:
            return sum(1 for x in range(not D, int(S) + 1) if not pcnt[str(x)])
        ans = 0
        for x in range(not D, int(S[0])):
            if pcnt[str(x)] == 0:
                ans += self.arrange(9 - D, len(S) - 1)
        if pcnt[S[0]] == 0:
            ans += self.solve(S[1:], D + 1)
        return ans
    def calc9(self, M):
        return 9 * sum(self.arrange(9, i) for i in range(M + 1))
    def arrange(self, a, b):
        if a < b or a < 0 or b < 0: return 0
        return self.factorial(a) / self.factorial(a - b)
    def factorial(self, n):
        if not n: return 1
        return reduce(operator.mul, range(1, n + 1))

本文链接：http://bookshadow.com/weblog/2019/03/18/leetcode-numbers-with-repeated-digits/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

×

捐赠书影博客

Close