LC9-20

2376. 统计特殊整数

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。

示例 2：

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。

示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。

提示：

• 1 <= n <= 2 * 109

数位DP模板提，用mask来记录当前已经访问过的数字，通过二进制来表示1到9。灵神模板

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        s = str(n)
        m = len(s)

        @cache
        def f(i: int, is_limit: int, is_num: int, mask: int) -> int:
            if i == m:
                return 1 if is_num else 0
            ret = 0
            if not is_num:
                ret = f(i + 1, False, is_num, mask)
            do, up = -1, -1
            do = 0 if is_num else 1
            up = int(s[i]) if is_limit else 9
            for k in range(do, up + 1):
                if not mask >> (k + 1) & 1:
                    ret += f(i + 1, is_limit and k == up, True, mask | (1 << k + 1))
            return ret
        return f(0, True, False, 0)

func countSpecialNumbers(n int) int {
	s := strconv.Itoa(n)
	m := len(s)
	type pair struct {
		idx  int
		mask int
	}
	cache := make(map[pair]int)

	var f func(i int, isLimit bool, isNum bool, mask int) int

	f = func(i int, isLimit bool, isNum bool, mask int) (ret int) {
		if i == m {
			if isNum {
				return 1
			} else {
				return 0
			}
		}
		if p, ok := cache[pair{i, mask}]; ok && isNum && !isLimit {
			return p
		}
		var do, up int
		if !isNum {
			ret = f(i+1, false, isNum, mask)
		}
		if !isNum {
			do = 1
		} else {
			do = 0
		}
		if isLimit {
			v, _ := strconv.Atoi(string(s[i]))
			up = v
		} else {
			up = 9
		}
		for k := do; k <= up; k++ {
			if (mask>>(k+1))&1 == 0 {
				ret += f(i+1, isLimit && k == up, true, mask|(1<<(k+1)))
			}
		}
		if isNum && !isLimit {
			cache[pair{i, mask}] = ret
		}
		return
	}

	return f(0, true, false, 0)
}

• $时间复杂度: O(mk2k),k等于10$
• $空间复杂度: O(m2k)$