小红的好数

[题目链接](https://www.nowcoder.com/practice/2d051851420c40baa5a3b7cefcaa78d5)

思路

定义"好数"为：数位中奇数个数等于偶数个数的正整数。例如 1124 有两个奇数位（1, 1）和两个偶数位（2, 4），是好数。注意 0 是偶数。

要求统计区间 $[l, r]$ 内好数的个数。由于 $l, r$ 可达 $10^{18}$ ，不可能逐个枚举，需要使用数位 DP。

数位 DP 框架

利用前缀和思想，将问题转化为：

$ $\text{answer} = f(r) - f(l-1)$ $

其中 $f(n)$ 表示 $[1, n]$ 中好数的个数。

对于 $f(n)$ ，将 $n$ 按十进制拆成数位数组，然后从高位到低位递归，维护以下状态：

状态	含义
`pos`	当前处理到第几位
`diff`	已填数位中，奇数个数 $-$ 偶数个数
`tight`	当前是否受上界约束（即前面的位是否都取到了 $n$ 对应位的值）
`started`	是否已经开始填非零数字（用于跳过前导零）

当 started = 0 且当前填 0 时，不更新 diff（前导零不算数位）。当所有位填完后，若 started = 1 且 diff = 0，说明奇数位个数等于偶数位个数，计数 $+1$ 。

样例演示

输入 l = 8, r = 12：

$f(12)$ ： $[1, 12]$ 中的好数有 10（奇数位 1、偶数位 0）和 12（奇数位 1、偶数位 2），共 $2$ 个。
$f(7)$ ： $[1, 7]$ 中所有数都是一位数，奇数位或偶数位只有一个，不可能相等，共 $0$ 个。
答案 $= 2 - 0 = 2$ 。

代码

C++
Java

#include <cstring>

class Solution {
public:
    long long getNums(long long l, long long r) {
        return count(r) - count(l - 1);
    }

private:
    int digits[20];
    int len;
    long long memo[20][41][2][2];

    long long count(long long n) {
        if (n <= 0) return 0;
        len = 0;
        long long tmp = n;
        while (tmp > 0) {
            digits[len++] = tmp % 10;
            tmp /= 10;
        }
        for (int i = 0; i < len / 2; i++) {
            int t = digits[i];
            digits[i] = digits[len - 1 - i];
            digits[len - 1 - i] = t;
        }
        memset(memo, -1, sizeof(memo));
        return dp(0, 0, 1, 0);
    }

    long long dp(int pos, int diff, int tight, int started) {
        if (pos == len) {
            if (!started) return 0;
            return diff == 0 ? 1 : 0;
        }
        int di = diff + 20;
        if (memo[pos][di][tight][started] != -1) {
            return memo[pos][di][tight][started];
        }
        int limit = tight ? digits[pos] : 9;
        long long res = 0;
        for (int d = 0; d <= limit; d++) {
            int newTight = tight && (d == limit);
            if (!started && d == 0) {
                res += dp(pos + 1, 0, newTight, 0);
            } else {
                int newDiff = diff;
                if (d % 2 == 1) newDiff++;
                else newDiff--;
                res += dp(pos + 1, newDiff, newTight, 1);
            }
        }
        return memo[pos][di][tight][started] = res;
    }
};

import java.util.*;

public class Solution {
    int[] digits = new int[20];
    int len;
    long[][][][] memo;

    public long getNums(long l, long r) {
        return count(r) - count(l - 1);
    }

    private long count(long n) {
        if (n <= 0) return 0;
        len = 0;
        long tmp = n;
        while (tmp > 0) {
            digits[len++] = (int)(tmp % 10);
            tmp /= 10;
        }
        for (int i = 0; i < len / 2; i++) {
            int t = digits[i];
            digits[i] = digits[len - 1 - i];
            digits[len - 1 - i] = t;
        }
        memo = new long[20][41][2][2];
        for (long[][][] a : memo)
            for (long[][] b : a)
                for (long[] c : b)
                    Arrays.fill(c, -1);
        return dp(0, 0, 1, 0);
    }

    private long dp(int pos, int diff, int tight, int started) {
        if (pos == len) {
            if (started == 0) return 0;
            return diff == 0 ? 1 : 0;
        }
        int di = diff + 20;
        if (memo[pos][di][tight][started] != -1) {
            return memo[pos][di][tight][started];
        }
        int limit = tight == 1 ? digits[pos] : 9;
        long res = 0;
        for (int d = 0; d <= limit; d++) {
            int newTight = (tight == 1 && d == limit) ? 1 : 0;
            if (started == 0 && d == 0) {
                res += dp(pos + 1, 0, newTight, 0);
            } else {
                int newDiff = diff;
                if (d % 2 == 1) newDiff++;
                else newDiff--;
                res += dp(pos + 1, newDiff, newTight, 1);
            }
        }
        return memo[pos][di][tight][started] = res;
    }
}

复杂度分析

时间复杂度： $O(D \times (2D+1) \times 2 \times 2 \times 10)$ ，其中 $D$ 为数字的位数（最多 $19$ 位）。每个状态最多计算一次，每次枚举 $0 \sim 9$ 共 $10$ 个数字。总状态数约 $20 \times 41 \times 2 \times 2 = 3280$ ，乘以 $10$ 后约 $3 \times 10^4$ ，非常高效。
空间复杂度： $O(D \times (2D+1) \times 2 \times 2)$ ，即记忆化数组的大小。