【LeetCode】每日一题 2024_9_20 统计特殊整数（数位 DP）

前言

每天和你一起刷 LeetCode 每日一题~

LeetCode 启动！

题目：统计特殊整数

代码与解题思路

func countSpecialNumbers(n int) int { // 今天的题目是数位 DP，我不会做，所以现场学习了一下灵神的数位 DP 模版s := strconv.Itoa(n)m := len(s)memo := make([][1<<10]int, m) // 记忆化，每个数位 0~9，二维的二进制开 10 个数位for i := range memo {for j := range memo[i] {memo[i][j] = -1}}// mask 代表的是当前的整数使用 0~9 这几个数位的集合// isLimit 代表的数字是否对应，需不需要约束，true 代表需要约束// isNum true 代表前面填了数字，false 代表没填，防止前导零的情况var dfs func(int, int, bool, bool) int  dfs = func(i, mask int, isLimit, isNum bool) (res int) {if i == m { // 遍历完所有数位了if isNum { // 如果最后一位数也填了，是个正常的数字return 1 // 证明有一个特殊整数}return 0 // 不算特殊整数，返回 0}// 记忆化：只记忆合法数字的情况（约束情况只出现一次，所以也不记忆）if !isLimit && isNum {p := &memo[i][mask]if *p != -1 {return *p}defer func() {*p = res}()}if !isNum { // 前面一个数字没填，那这个数字也可以不填（不填的情况）res += dfs(i+1, mask, false, false) // 前面没有约束}// 填数字的情况d := 0if !isNum { // 如果前面那个数字没填，那就不能填 0 d = 1}up := 9 // 没有约束默认上限是 9if isLimit { // 如果有约束，就设置 up 为约束的上限up = int(s[i]-'0')}for d <= up { // 枚举符合条件的每一个数字if mask >> d & 1 == 0 { // 没用过这个数字// mask|1<<d 标记这个数字在 mask 二进制的数位// isLimit&&d == up 如果上一个数字是约束，这个数字又是上限，那就存在约束res += dfs(i+1, mask|1<<d, isLimit&&d == up, true) // 填了数字}d++}return res}return dfs(0, 0, true, false) // 第一个数字自然需要约束
}