范围中美丽整数的数目

You are given positive integers low, high, and k.

A number is beautiful if it meets both of the following conditions:

• The count of even digits in the number is equal to the count of odd digits.
• The number is divisible by k.

Return the number of beautiful integers in the range [low, high].

 

Example 1:

Input: low = 10, high = 20, k = 3
Output: 2
Explanation: There are 2 beautiful integers in the given range: [12,18]. 
- 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
- 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
Additionally we can see that:
- 16 is not beautiful because it is not divisible by k = 3.
- 15 is not beautiful because it does not contain equal counts even and odd digits.
It can be shown that there are only 2 beautiful integers in the given range.

Example 2:

Input: low = 1, high = 10, k = 1
Output: 1
Explanation: There is 1 beautiful integer in the given range: [10].
- 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1.
It can be shown that there is only 1 beautiful integer in the given range.

Example 3:

Input: low = 5, high = 5, k = 2
Output: 0
Explanation: There are 0 beautiful integers in the given range.
- 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.

 

Constraints:

• 0 < low <= high <= 109
• 0 < k <= 20

/*
 * 使用Java Stream的思路：
 * 1. 使用IntStream遍历从low到high之间的每个整数。
 * 2. 通过filter筛选出满足条件的美丽整数。
 * 3. 使用count()方法计算美丽整数的数量。
 */
import java.util.stream.IntStream;

public class BeautifulNumbersStream {
    public static int countBeautifulNumbers(int low, int high, int k) {
        return (int) IntStream.rangeClosed(low, high)
                .filter(num -> {
                    int oddCount = 0;
                    int evenCount = 0;
                    int original = num;

                    while (num > 0) {
                        int digit = num % 10;
                        if (digit % 2 == 0) {
                            evenCount++;
                        } else {
                            oddCount++;
                        }
                        num /= 10;
                    }

                    // 检查是否奇数位和偶数位数量相等并且可以被k整除
                    return oddCount == evenCount && original % k == 0;
                })
                .count();
    }

    public static void main(String[] args) {
        int low = 10, high = 20, k = 3;
        System.out.println(countBeautifulNumbers(low, high, k)); // 输出: 2
    }
}

题解采用了深度优先搜索（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)