至少有1位重复的数字

Leetcode Link: 1012. 至少有 1 位重复的数字 - 力扣（LeetCode）

题目

解法一

思路： 可以找其对偶问题，即找全不重复的数字，然后用所有的数字个数减去不重复的数字的个数即得到了结果。

题解：

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n)
        @cache
        def process(i, mask, is_bound, is_zero):
            if i == len(s):
                return not is_zero
            
            maxi = int(s[i]) if is_bound else 9
            
            res = 0
            for val in range(maxi+1):
                if is_zero and val == 0:
                    res += process(i+1, mask, False, True)
                else:
                    if mask >> val & 1 == 0:
                        res += process(i+1, mask | (1 << val), is_bound and val==maxi, is_zero and val == 0)
            return res
        
        return n - process(0, 0, True, True)

启发和联系