LeetCode每日一题(1012. Numbers With Repeated Digits)

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

Example 1:

Input: n = 20
Output: 1

Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

Example 2:

Input: n = 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: n = 1000
Output: 262

Constraints:

• 1 <= n <= 109

---

整体上我们反过来想， 至少重复 2 位的数字的数量=总数-没有重复数字的数量， 那我们只要算出所有没有重复数字的数量就可以了。这部分我们又可以分为两部分。 一部分是位数小于 n 的， 这部分直接计算就可以，每一位可选的数字数量相乘即可，但是要注意减去开头是 0 的情况。另一部分是位数等于 n 的， 这里我们整体上还是按每一位可选数字数量来算， 但是要注意，如果前 m 位都跟 n[…m]的数字相等， 那当前位数字的可选范围就是从 0 到 n[m+1], 因为如果我们选择比 n[m+1]大的数字，那整体是肯定要>n 的，也就是超出范围了。同时我们还需要维护当前剩余的可选数字， 因为每个数字只能使用一次， 前面的位使用了，那当前位就不能再使用， 这一点我们通过 bit mask 来实现， 因为最多一共就 10 个可选的数字， 从 0 到 9

---

use std::collections::HashMap;

impl Solution {
   
    fn rc(
        digits: &[i32],
        pos: usize,
        is_equal: bool,
        choices: i32,
        cache: &mut HashMap<(usize, bool, i32), i32>,
    ) -> i32 {
   
        if pos == digits.len() {
   
            return 1;
        }
        let mut ans = 0;
        // 第一位的情况， 可选数字不能包括0
        if pos == 0 {
   
            for d in 1..=digits[pos] {
   
                if choices &
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23