1012._Numbers_With_1_Repeated_Digit.md

1012. Numbers With 1 Repeated Digit

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/numbers-with-1-repeated-digit/

内容描述

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

解题方案

思路 1 - 时间复杂度: O(lgN)- 空间复杂度: O(lgN)******

算有重复的，我们可以先算出没有重复的，然后返回(总数-没有重复)即可

比赛中我想到了可以这样做，但是实现的时候TLE了，赛后看了[Java/Python] Count the Number Without Repeated Digit

那么没有重复怎么算呢？

对于一个N位digit的数字，小于等于它的没有重复的有以下两种：

1. digit数小于N的，对于这部分，直接算即可
2. digit数小于N的，对于这部分，我们必须要让构造出的数字小于等于N

class Solution:
    def numDupDigitsAtMostN(self, N):
        L = list(map(int, str(N + 1)))
        res, n = 0, len(L)

        def A(m, n):
            return 1 if n == 0 else A(m, n - 1) * (m - n + 1)

        for i in range(1, n): 
            res += 9 * A(9, i - 1)
        s = set()
        for i, x in enumerate(L):
            for y in range(0 if i else 1, x):
                if y not in s:
                    res += A(9 - i, n - i - 1)
            if x in s: 
                break
            s.add(x)
        return N - res

For anyone who doesn't understand the function def A(), you can see the iterative version of it below.

        def A(m, n):
            res = 1
            for i in range(n):
                res *= m
                m -= 1
            return res

It means the permutation of m * (m-1) * ... * (m-(n-1)).

And for why use 9*A(9,i-1) instead of A(9,i), that's because there should be no leading 0, but the following digit can be 0.

将函数A重命名为permu

class Solution:
    def numDupDigitsAtMostN(self, N):
        L = list(map(int, str(N + 1)))
        res, n = 0, len(L)

        def permu(m, n):
            res = 1
            for i in range(n):
                res *= m
                m -= 1
            return res

        for i in range(1, n): 
            res += 9 * permu(9, i - 1)
            
        s = set()
        for i, x in enumerate(L):
            for y in range(0 if i else 1, x):
                if y not in s:
                    res += permu(9 - i, n - i - 1)
            if x in s: 
                break
            s.add(x)
        return N - res