范围中美丽整数的数目

难度: Hard

给你正整数 low ，high 和 k 。

如果一个数满足以下两个条件，那么它是 美丽的 ：

偶数数位的数目与奇数数位的数目相同。
这个整数可以被 k 整除。

请你返回范围 [low, high] 中美丽整数的数目。

示例 1：

输入：low = 10, high = 20, k = 3
输出：2
解释：给定范围中有 2 个美丽数字：[12,18]
- 12 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
- 18 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 3 整除。
以下是一些不是美丽整数的例子：
- 16 不是美丽整数，因为它不能被 k = 3 整除。
- 15 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。
给定范围内总共有 2 个美丽整数。

示例 2：

输入：low = 1, high = 10, k = 1
输出：1
解释：给定范围中有 1 个美丽数字：[10]
- 10 是美丽整数，因为它有 1 个奇数数位和 1 个偶数数位，而且可以被 k = 1 整除。
给定范围内总共有 1 个美丽整数。

示例 3：

输入：low = 5, high = 5, k = 2
输出：0
解释：给定范围中有 0 个美丽数字。
- 5 不是美丽整数，因为它的奇数数位和偶数数位的数目不相等。

提示：

0 < low <= high <= 10⁹
0 < k <= 20

Submission

运行时间: 44 ms

内存: 16.5 MB

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        s2 = str(high)
        n = len(s2)
        s1 = str(low).zfill(n)
        @cache
        def dfs(i:int,cnt1:int,cnt2:int,cnt3:int,is_limit1:bool,is_limit2:bool,is_num:bool)->int:
            if i==n:
                if is_num:
                    if cnt1==cnt2 and cnt3==0:
                        return 1
                    else:
                        return 0
                else:
                    return 0
            res = 0
            if not is_num:
                if int(s1[i])==0:
                    res += dfs(i+1,cnt1,cnt2,cnt3,True,False,False)
            if not is_num:
                if (n-i)%2!=0:
                    return res
            low = int(s1[i]) if is_limit1 else 0
            if not is_num:
                if low<1:
                    low = 1
                    if is_limit1:
                        is_limit1 = False
            up = int(s2[i]) if is_limit2 else 9
            for d in range(low,up+1):
                res += dfs(i+1,cnt1+(d%2!=0),cnt2+(d%2==0),(cnt3*10+d)%k,is_limit1 and d==low,is_limit2 and d==up,True)
            return res
        return dfs(0,0,0,0,True,True,False)

Explain

题解采用了深度优先搜索（DFS）和记忆化搜索来解决问题。首先，将low和high转换为字符串，并在low前补0使其长度与high一致。这样可以确保在比较时位数相等。通过递归函数dfs来探索每个可能的数字，该函数通过六个参数来控制状态：当前处理的数字位置i，当前奇数位的数量cnt1，偶数位的数量cnt2，当前数字模k的余数cnt3，以及两个布尔值is_limit1和is_limit2分别表示当前是否受到low和high的限制。递归的基本思路是，对于每一位，根据是否受限制选择可能的数字范围进行遍历，并递归处理下一位。最终，当处理完所有位时，检查奇数位和偶数位数量是否相等以及是否能被k整除，来确定该数字是否美丽。

时间复杂度: O(n^2 * k)

空间复杂度: O(n^2 * k)

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        s2 = str(high)
        n = len(s2)
        s1 = str(low).zfill(n)
        @cache
        def dfs(i:int,cnt1:int,cnt2:int,cnt3:int,is_limit1:bool,is_limit2:bool,is_num:bool)->int:
            if i==n:
                return 1 if is_num and cnt1==cnt2 and cnt3==0 else 0
            res = 0
            low = int(s1[i]) if is_limit1 else 0
            up = int(s2[i]) if is_limit2 else 9
            for d in range(low, up+1):
                res += dfs(i+1, cnt1+(d%2!=0), cnt2+(d%2==0), (cnt3*10+d)%k, is_limit1 and d==low, is_limit2 and d==up, True)
            return res
        return dfs(0, 0, 0, 0, True, True, False)

Explore

使用DFS而不是迭代法的原因在于，问题的复杂性和约束条件。DFS允许我们在搜索过程中有效地应用剪枝，避免无效的枚举。例如，通过逐步构建数字并在不满足条件时立即停止进一步搜索，可以显著减少需要检查的数字总数。此外，迭代枚举每个数字在数字范围很大时将非常低效，特别是当涉及到多个约束（如位数的奇偶性和模k余数）时，DFS通过递归控制和状态传递可以更灵活地处理这些复杂的条件。

在DFS实现中，处理数字0，特别是在数字开头的情况，通过确保数字长度与high相同来进行。这是通过将low数字前补0实现的，确保在递归过程中每一位都能被考虑到，即使它是0。在递归函数中，通过参数is_limit1和is_limit2控制数字是否可以取0，尤其是在首位。如果is_limit1为true且当前位是最低位，则可以从0开始；否则，如果不是首位或没有限制，则可以自由选择0到9之间的任何数字。

在递归函数中使用is_limit1和is_limit2这两个布尔值是为了确保生成的数字在指定的low和high范围内。is_limit1控制生成数字不低于low，is_limit2确保不超过high。具体实现方式是，当递归到某一位时，如果是受限状态（即is_limit1或is_limit2为true），则这一位数字的选取会受到low或high对应位的限制：只能从low的当前位或到high的当前位之间选择。如果不受限，则可以自由选择0到9任意数字。这种方法可以精确控制数字的生成，避免无效的搜索。

记忆化搜索的关键是避免重复计算已经求解过的状态，从而提高算法效率。在本题中，记忆化的状态和参数包括当前位的位置i，奇数位的数量cnt1，偶数位的数量cnt2，以及当前数字模k的余数cnt3，还有两个布尔值is_limit1和is_limit2表示是否受到low和high的限制。通过缓存这些状态的结果，当递归调用遇到相同的状态时，可以直接返回之前计算的结果，避免了重复的计算工作。这种方法特别适用于本题，因为数字的每一位选择都可能引起状态的变化，且状态空间大，容易产生重复。