## 题目描述：

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`

## 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))
``````

Pingbacks已关闭。