【leetcode】1012. 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 <= 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(4-1，9) (A为数学中排列)

位数等于Input时的情况会麻烦一些。我的方法是首先求以5XXXX这种格式的总数，然后再求出53XXX这种格式的总数，直到最后求出总数。

5XXXX: 第二位只能为0，1或者2，剩余的位数中，只能在除了第一位和第二位之外的8个数字中挑选，总数为 3 * A(3，8)

53XXX: 第三位只能为0或者1，剩余的位数中，只能在除了第一，二，三位之外的7个数字中挑选，总数为 2 * A(2，7)

532XX之后的情况类似

代码如下：

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

巴特西

【leetcode】1012. Numbers With Repeated Digits

最新文章

热门文章