javascript 解法, 执行用时: 72 ms, 内存消耗: 41.9 MB, 提交时间: 2023-03-20 09:15:30

/**
 * @param {number} n
 * @return {number}
 */
var numDupDigitsAtMostN = function(n) {
    const sn = '' + n;
    const f = (mask, sn, i, same) => {
        if (i === sn.length) {
            return 1;
        }
        let t = same ? sn[i].charCodeAt() - '0'.charCodeAt() : 9, res = 0, c = bitCount(mask) + 1;
        for (let k = 0; k <= t; k++) {
            if ((mask & (1 << k)) !== 0) {
                continue;
            }
            if (same && k === t) {
                res += f(mask | (1 << t), sn, i + 1, true);
            } else if (mask === 0 && k === 0) {
                res += f(0, sn, i + 1, false);
            } else {
                res += A(sn.length - 1 - i, 10 - c);
            }
        }
        return res;
    }
    return n + 1 - f(0, sn, 0, true);
}

const A = (x, y) => {
    let res = 1;
    for (let i = 0; i < x; i++) {
        res *= y--;
    }
    return res;
}

const bitCount = (n) => {
    return n.toString(2).split('0').join('').length;
}

java 解法, 执行用时: 0 ms, 内存消耗: 38.5 MB, 提交时间: 2023-03-20 09:15:14

class Solution {
    public int numDupDigitsAtMostN(int n) {
        String sn = String.valueOf(n);
        return n + 1 - f(0, sn, 0, true);
    }

    public int f(int mask, String sn, int i, boolean same) {
        if (i == sn.length()) {
            return 1;
        }
        int t = same ? sn.charAt(i) - '0' : 9, res = 0, c = Integer.bitCount(mask) + 1;
        for (int k = 0; k <= t; k++) {
            if ((mask & (1 << k)) != 0) {
                continue;
            }
            if (same && k == t) {
                res += f(mask | (1 << t), sn, i + 1, true);
            } else if (mask == 0 && k == 0) {
                res += f(0, sn, i + 1, false);
            } else {
                res += A(sn.length() - 1 - i, 10 - c);
            }
        }
        return res;
    }

    public int A(int x, int y) {
        int res = 1;
        for (int i = 0; i < x; i++) {
            res *= y--;
        }
        return res;
    }
}

python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2023-03-20 09:14:58

class Solution:
    def numDupDigitsAtMostN(self, N: int) -> int:
        limit, s = list(map(int, str(N + 1))), set()
        n, res = len(limit), sum(9 * perm(9, i) for i in range(len(limit) - 1))
        for i, x in enumerate(limit):
            for y in range(i == 0, x):
                if y not in s:
                    res += perm(9 - i, n - i - 1)
            if x in s: 
                break
            s.add(x)
        return N - res

java 解法, 执行用时: 9 ms, 内存消耗: 40.7 MB, 提交时间: 2023-03-20 09:14:03

class Solution {
    char s[];
    int dp[][];

    public int numDupDigitsAtMostN(int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        dp = new int[m][1 << 10];
        for (int i = 0; i < m; i++) 
            Arrays.fill(dp[i], -1); // -1 表示没有计算过
        return n - f(0, 0, true, false);
    }

    int f(int i, int mask, boolean isLimit, boolean isNum) {
        if (i == s.length)
            return isNum ? 1 : 0; // isNum 为 true 表示得到了一个合法数字
        if (!isLimit && isNum && dp[i][mask] != -1)
            return dp[i][mask];
        int res = 0;
        if (!isNum) // 可以跳过当前数位
            res = f(i + 1, mask, false, false);
        int up = isLimit ? s[i] - '0' : 9; // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
        for (int d = isNum ? 0 : 1; d <= up; ++d) // 枚举要填入的数字 d
            if ((mask >> d & 1) == 0) // d 不在 mask 中
                res += f(i + 1, mask | (1 << d), isLimit && d == up, true);
        if (!isLimit && isNum)
            dp[i][mask] = res;
        return res;
    }
}

golang 解法, 执行用时: 8 ms, 内存消耗: 6.2 MB, 提交时间: 2023-03-20 09:13:41

func numDupDigitsAtMostN(n int) (ans int) {
	s := strconv.Itoa(n)
	m := len(s)
	dp := make([][1 << 10]int, m)
	for i := range dp {
		for j := range dp[i] {
			dp[i][j] = -1 // -1 表示没有计算过
		}
	}
	var f func(int, int, bool, bool) int
	f = func(i, mask int, isLimit, isNum bool) (res int) {
		if i == m {
			if isNum {
				return 1 // 得到了一个合法数字
			}
			return
		}
		if !isLimit && isNum {
			dv := &dp[i][mask]
			if *dv >= 0 {
				return *dv
			}
			defer func() { *dv = res }()
		}
		if !isNum { // 可以跳过当前数位
			res += f(i+1, mask, false, false)
		}
		d := 0
		if !isNum {
			d = 1 // 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
		}
		up := 9
		if isLimit {
			up = int(s[i] - '0') // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
		}
		for ; d <= up; d++ { // 枚举要填入的数字 d
			if mask>>d&1 == 0 { // d 不在 mask 中
				res += f(i+1, mask|1<<d, isLimit && d == up, true)
			}
		}
		return
	}
	return n - f(0, 0, true, false)
}

python3 解法, 执行用时: 252 ms, 内存消耗: 19.6 MB, 提交时间: 2023-03-20 09:13:08

'''
正难则反，求出没有重复数字的个数
f(i, mask, is_limit, is_num) 表示构造从高到低第 i 位及其之后数位的合法方案数，
其余参数的含义为:
mask: 表示前面选过的数字集合，换句话说，第 i 位要选的数字不能在 mask 中。
is_limit: 表示当前是否受到了 n 的约束。若为真，则第 i 位填入的数字至多为 s[i]，否则可以是 9。
如果在受到约束的情况下填了 s[i]，那么后续填入的数字仍会受到 n 的约束。
is_num: 表示 i 前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1；
若为真，则要填入的数字可以从 0 开始。

'''
class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n)
        @cache  # 记忆化搜索
        def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:
            if i == len(s):
                return int(is_num)  # is_num 为 True 表示得到了一个合法数字
            res = 0
            if not is_num:  # 可以跳过当前数位
                res = f(i + 1, mask, False, False)
            low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
            up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）
            for d in range(low, up + 1):  # 枚举要填入的数字 d
                if (mask >> d & 1) == 0:  # d 不在 mask 中
                    res += f(i + 1, mask | (1 << d), is_limit and d == up, True)
            return res
        return n - f(0, 0, True, False)