[LeetCode]Numbers With Repeated Digits

题目描述:

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.

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: 262

Note:

  1. 1 <= N <= 10^9

题目大意:

给定正整数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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论