2026-07-07：统计区间内奇妙数的数目。用go语言，给定两个整数 l 和 r。对于任意整数，把它写成十进制各位数字的序列：如果这些数字从左

福大大架构师每日一题

发布于 2026-07-07 18:38:36

2026-07-07：统计区间内奇妙数的数目。用go语言，给定两个整数 l 和 r。对于任意整数，把它写成十进制各位数字的序列：如果这些数字从左到右要么严格递增、要么严格递减（相邻两位必须分别满足更大或更小），则该整数称为好数。任意一位的整数都算好数。若某个整数是好数，或它的各位数字之和本身是好数，则该整数称为奇妙数。需要计算区间 [l, r]（包含端点）中奇妙数的个数，并返回这个数量。

1 <= l <= r <= 1000000000000000。

输入： l = 8, r = 10。

输出： 3。

解释：

8 和 9 是一位数，所以它们是好数，因此也是奇妙数。

10 的数位为 [1, 0]，形成了一个严格递减的序列，所以 10 是好数，因此也是奇妙数。

因此，答案是 3。

题目来自力扣3869。

一、代码整体两大模块分步流程

整体分为两大独立计算模块，结果相加得到最终奇妙数总数：模块A：预处理所有“本身是好数、且数位和不是好数”的数字，二分统计区间数量ans；模块B：数位DP统计区间内所有数位和为好数的数字数量dfs结果；最终答案 = A结果 + B结果。

模块A：预处理全部纯好数（本身是好数），快速区间计数

步骤1：初始化全局数组goodNums（init函数预生成，程序启动仅执行一次）

目标：枚举、生成所有十进制严格递增/严格递减的数字（全部好数），过滤掉其中数位和为好数的数字，只保留「本身是好数、数位和不是好数」的数字存入数组。

子步骤1：二进制掩码枚举0~9数字子集

用掩码mask遍历 1 ~ (1<<10)-1，每一位mask代表数字0-9是否被选用：

• mask第i位=1：代表数字i参与构造数字；
• 每个非空mask对应唯一一组不重复数字，能构造一个严格递减数、一个严格递增数。

子步骤2：构造严格递减好数

从9到0遍历数字，mask选中则拼接在数字末尾：示例mask含1、0：拼接顺序9→1→0，得到10，严格递减；拼接同时累加所有选中数字得到数位和sum；拼接完成后判断：若sum不是好数（!isGood(sum)），把这个递减数字存入goodNums。

子步骤3：构造严格递增好数，做前置合法性校验

严格递增数字不能以0开头：若mask包含数字0（mask最低位为1），直接跳过本轮递增数构造；从1到9从小到大遍历选中数字，依次拼接，生成严格递增数字，同步计算数位和sum；若sum不是好数，存入goodNums数组。

子步骤4：全局数组排序

全部mask遍历完成后，对goodNums升序排序。排序目的是使用二分查找快速统计区间数字个数。

步骤2：二分查找统计区间[l,r]内模块A数字数量

sort.SearchInts二分查找：

1. 查找第一个 ≥ l 的下标leftIdx；
2. 查找第一个 ≥ r+1 的下标rightIdx；
3. 区间内数量 = rightIdx - leftIdx，记为ans。模块A统计的是：区间内「本身是好数，且数位和不是好数」的数字。后续模块B会统计所有「数位和是好数」的数字（包含那些本身是好数的重叠数字），两者相加刚好覆盖全部奇妙数。

模块B：数位DP，统计区间[l,r]内所有数位和为好数的数字总数

输入范围极大（最高1e15，15位数字），无法暴力枚举，使用数字数位DP求解，统计满足「数位和s是好数」的所有数字，不限制数字本身是否为好数。

前置预处理步骤

1. 将左右边界l、r转为字符串lowS、highS，获取高位数长度n（取r的位数，统一补前导空位对齐两个数字长度）；
2. 计算长度差值diffLH = r的位数 - l的位数，用于处理l位数更少时的前导空白位；
3. 初始化DP记忆数组memo：memo[i][sum]，i为当前处理到第几位，sum为当前累计数位和；
- • 最大位数15，每位最大9，数位和上限15*9=135；
- • 记忆数组存储无上下界约束时，后续合法数字总数；采用标记res+1区分未访问状态，无需初始化为-1。

DFS递归函数四层逻辑（i=当前处理位，digitSum=累计数位和，limitLow=下界紧约束，limitHigh=上界紧约束）

1. 递归终止条件（i == n，所有位处理完毕）

当前数字构造完成，判断累计数位和digitSum是否为好数：

• 是好数：返回1（该数字合法，计入统计）；
• 不是好数：返回0。

2. 记忆化剪枝判断

若当前数字不受下界、上界任何约束（limitLow=false && limitHigh=false）：

• 检查memo[i][digitSum]是否存在缓存结果；
• 存在则直接读取缓存值减1返回；
• 不存在则递归计算结果，执行defer延迟存入缓存（存res+1区分未访问）。

3. 确定当前位数字可选范围[lo, hi]

• lo：下界约束，若当前位落在l有效数字区间内，lo取lowS对应位数字，否则lo=0；
• hi：上界约束，若开启上界紧约束，hi取highS对应位数字，否则hi=9。

4. 前导空白位特殊处理（对齐长短数字）

当l位数小于r位数（i < diffLH）且开启下界约束：

• 当前位可以不填数字（前导空白，不计入数位和），递归下一位，limitLow保持true、limitHigh改为false；
• 后续填充数字从d=1开始（数字不能前导0）。

5. 遍历当前位所有合法数字，累加合法数量

从d初始值循环到hi，每选一个数字：

• 新数位和 = digitSum + d；
• 更新新约束：仅当当前d等于边界值时，对应约束保持true，否则释放约束；
• 递归下一位，返回值累加至总结果res。

6. 返回当前分支总合法数量res

模块B最终结果

调用dfs(0,0,true,true)，得到[l,r]内所有数位和为好数的数字总数。

二、总结果合并逻辑

奇妙数 = A类数字（本身是好数、数位和非好数） + B类数字（数位和是好数，不限是否好数）两类相加无重复漏算：

• 数字本身是好数且数位和是好数：仅在B类统计一次；
• 数字本身是好数、数位和不是好数：仅在A类统计一次；
• 数字本身不是好数、数位和是好数：仅在B类统计一次；全部三类合并刚好覆盖所有奇妙数。

示例输入 l=8，r=10 完整演算

1. 模块A：goodNums存储「本身是好数、数位和不是好数」，8、9、10都是好数，分别计算数位和：
- • 8：和=8，是个位数，两位不等判定为好数 → 不存入goodNums；
- • 9：和=9，是好数 → 不存入goodNums；
- • 10：和=1，是好数 → 不存入goodNums；二分查找区间[8,10]，A结果ans=0。
2. 模块B：统计数位和为好数的数字：
- • 8：和8是好数，计数+1；
- • 9：和9是好数，计数+1；
- • 10：和1是好数，计数+1； DFS返回3。
3. 总和0+3=3，与题目输出一致。

三、时间复杂度、额外空间复杂度分析

1. 预处理阶段（init函数，仅程序启动运行1次，不计入单次查询耗时）

时间

掩码循环：2^10=1024次循环，每次循环构造两个数字，最多遍历10位数字，总固定常数1024210=20480次运算，O(1) 常数复杂度。

空间

goodNums数组固定仅139个元素，常数空间O(1)。

2. 单次查询 countFancy(l,r) 时间复杂度

（1）二分统计模块A

二分查找长度139的数组，二分次数log₂139≈8次，O(1)常数。

（2）数位DP核心耗时

设最大位数 len=15（1e15最多15位），数位和最大sum_max=15*9=135；状态总数 = 位数 × 数位和 × limitLow(2种) × limitHigh(2种) = 15 × 135 × 2 × 2 = 8100 个状态；每个状态仅遍历0~9共10个数字分支，总运算量固定为常数级。单次查询整体时间复杂度：O(1)（常数，与l、r数值无关）。

3. 单次查询额外空间复杂度

1. DP记忆数组memo：15 × 136 = 2040 个int64，固定常数；
2. DFS递归栈深度最大15层；
3. 存储数字字符串lowS、highS长度最多15；单次查询额外空间：O(1) 常数空间。

全局总复杂度总结

1. 整体时间复杂度（单次查询）：O(1)，所有循环、状态、预处理均为固定常数，不受输入l、r大小影响；
2. 整体额外空间复杂度：O(1)，全局数组与单次DP内存均为固定常量，无随输入扩张的存储空间。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
    "sort"
    "strconv"
)

// 数位和不是好数的好数（只有 139 个）
var goodNums []int

func init() {
    // 枚举 {0,1,2,...,9} 的非空子集
    for mask := 1; mask < 1<<10; mask++ {
        // 构造严格递减好数
        x := 0
        sum := 0
        for i := 9; i >= 0; i-- { // 从大到小遍历子集中的元素
            if mask>>i&1 > 0 {
                x = x*10 + i
                sum += i
            }
        }
        if !isGood(sum) {
            goodNums = append(goodNums, x)
        }

        // 构造严格递增好数
        if mask&1 > 0 { // 不能包含 0
            continue
        }
        x = 0
        sum = 0
        for i := 1; i < 10; i++ { // 从小到大遍历子集中的元素
            if mask>>i&1 > 0 {
                x = x*10 + i
                sum += i
            }
        }
        if !isGood(sum) {
            goodNums = append(goodNums, x)
        }
    }

    slices.Sort(goodNums) // 方便二分求个数
}

// 判断数位和 s 是否为好数
func isGood(s int)bool {
    if s < 100 { // s 是个位数或者两位数
        return s/10 != s%10// 十位和个位不相等即为好数
    }
    // s 是三位数，其百位一定是 1
    return1 < s/10%10 && s/10%10 < s%10// 只能严格递增
}

func countFancy(l, r int64)int64 {
    // 计算 [l, r] 内的数位和不是好数的好数的个数
    ans := int64(sort.SearchInts(goodNums, int(r+1)) - sort.SearchInts(goodNums, int(l)))

    // 计算 [l, r] 内的数位和是好数的数的个数（这个数是不是好数都可以）
    lowS := strconv.FormatInt(l, 10)
    highS := strconv.FormatInt(r, 10)
    n := len(highS)
    diffLH := n - len(lowS)
    memo := make([][]int64, n)
    for i := range memo {
        memo[i] = make([]int64, n*9+1) // 数位和最大 9n
    }

    var dfs func(int, int, bool, bool)int64
    dfs = func(i, digitSum int, limitLow, limitHigh bool) (res int64) {
        if i == n {
            if isGood(digitSum) {
                return1// 合法
            }
            return0// 不合法
        }
        if !limitLow && !limitHigh {
            dv := &memo[i][digitSum]
            if *dv > 0 {
                return *dv - 1
            }
            deferfunc() { *dv = res + 1 }() // 这样写无需初始化 memo 为 -1
        }

        lo := 0
        if limitLow && i >= diffLH {
            lo = int(lowS[i-diffLH] - '0')
        }
        hi := 9
        if limitHigh {
            hi = int(highS[i] - '0')
        }

        d := lo
        // 通过 limitLow 和 i 可以判断能否不填数字，无需 isNum 参数
        if limitLow && i < diffLH {
            // 不填数字，上界不受约束
            res = dfs(i+1, 0, true, false)
            d = 1// 下面填数字，从 1 开始填
        }

        for ; d <= hi; d++ {
            res += dfs(i+1, digitSum+d, limitLow && d == lo, limitHigh && d == hi)
        }
        return
    }

    return ans + dfs(0, 0, true, true)
}

func main() {
    l := 8
    r := 10
    result := countFancy(int64(l), int64(r))
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import bisect

def is_good(s: int) -> bool:
    """判断数位和 s 是否为好数"""
    if s < 100:
        # 个位数或两位数：十位和个位不相等
        return (s // 10) != (s % 10)
    # s 是三位数（实际不会发生，但保留逻辑）
    return1 < (s // 10 % 10) < (s % 10)


# 预处理所有“数位和不是好数”的好数（仅有 139 个）
good_nums = []

for mask in range(1, 1 << 10):
    # 构造严格递减好数（从高到低取数字）
    x = 0
    digit_sum = 0
    for i in range(9, -1, -1):
        if mask & (1 << i):
            x = x * 10 + i
            digit_sum += i
    if not is_good(digit_sum):
        good_nums.append(x)

    # 构造严格递增好数（从低到高取数字，不含 0）
    if mask & 1:          # 子集包含 0，则跳过
        continue
    x = 0
    digit_sum = 0
    for i in range(1, 10):
        if mask & (1 << i):
            x = x * 10 + i
            digit_sum += i
    if not is_good(digit_sum):
        good_nums.append(x)

good_nums.sort()


def count_fancy(l: int, r: int) -> int:
    """
    计算 [l, r] 内满足条件的数的个数：
      1) 本身是好数（数位严格递增或递减）且数位和不是好数
      2) 或者数位和是好数（不要求本身是好数）
    """
    # 区间内 good_nums 的个数
    ans = bisect.bisect_left(good_nums, r + 1) - bisect.bisect_left(good_nums, l)

    low_s = str(l)
    high_s = str(r)
    n = len(high_s)
    diff = n - len(low_s)

    max_sum = 9 * n
    memo = [[-1] * (max_sum + 1) for _ in range(n)]

    def dfs(i: int, digit_sum: int, limit_low: bool, limit_high: bool) -> int:
        if i == n:
            return1if is_good(digit_sum) else0

        if not limit_low and not limit_high:
            if memo[i][digit_sum] != -1:
                return memo[i][digit_sum]

        lo = 0
        if limit_low and i >= diff:
            lo = int(low_s[i - diff])

        hi = 9
        if limit_high:
            hi = int(high_s[i])

        res = 0
        d = lo

        # 处理低边界位数不足的情况：允许跳过当前位（相当于填 0）
        if limit_low and i < diff:
            res = dfs(i + 1, 0, True, False)   # 不填数字，上界约束解除
            d = 1                              # 若填数字，不能填 0（避免重复）

        while d <= hi:
            res += dfs(
                i + 1,
                digit_sum + d,
                limit_low and d == lo,
                limit_high and d == hi
            )
            d += 1

        if not limit_low and not limit_high:
            memo[i][digit_sum] = res

        return res

    return ans + dfs(0, 0, True, True)


if __name__ == "__main__":
    l, r = 8, 10
    print(count_fancy(l, r))

C++完整代码如下：

#include <bits/stdc++.h>
using namespace std;

// 判断数位和 s 是否为好数
bool isGood(int s) {
    if (s < 100) {
        // 个位数或两位数：十位和个位不相等
        return (s / 10) != (s % 10);
    }
    // s 是三位数，其百位一定是1
    return1 < (s / 10 % 10) && (s / 10 % 10) < (s % 10);
}

// 预处理所有"数位和不是好数"的好数（仅有139个）
vector<int> goodNums;

void init() {
    // 枚举 {0,1,2,...,9} 的非空子集
    for (int mask = 1; mask < (1 << 10); mask++) {
        // 构造严格递减好数
        int x = 0;
        int sum = 0;
        for (int i = 9; i >= 0; i--) {
            if (mask & (1 << i)) {
                x = x * 10 + i;
                sum += i;
            }
        }
        if (!isGood(sum)) {
            goodNums.push_back(x);
        }

        // 构造严格递增好数
        if (mask & 1) {  // 不能包含0
            continue;
        }
        x = 0;
        sum = 0;
        for (int i = 1; i < 10; i++) {
            if (mask & (1 << i)) {
                x = x * 10 + i;
                sum += i;
            }
        }
        if (!isGood(sum)) {
            goodNums.push_back(x);
        }
    }

    sort(goodNums.begin(), goodNums.end());
}

long long countFancy(long long l, long long r) {
    // 计算 [l, r] 内的数位和不是好数的好数的个数
    long long ans = upper_bound(goodNums.begin(), goodNums.end(), r) -
                    lower_bound(goodNums.begin(), goodNums.end(), l);

    // 计算 [l, r] 内的数位和是好数的数的个数（这个数是不是好数都可以）
    string lowS = to_string(l);
    string highS = to_string(r);
    int n = highS.length();
    int diffLH = n - lowS.length();

    // memo[i][digitSum] 表示从第i位开始，当前数位和为digitSum时的方案数
    // 使用 -1 表示未计算
    vector<vector<long long>> memo(n, vector<long long>(n * 9 + 1, -1));

    function<long long(int, int, bool, bool)> dfs = [&](int i, int digitSum, bool limitLow, bool limitHigh) -> long long {
        if (i == n) {
            return isGood(digitSum) ? 1 : 0;
        }

        if (!limitLow && !limitHigh) {
            if (memo[i][digitSum] != -1) {
                return memo[i][digitSum];
            }
        }

        int lo = 0;
        if (limitLow && i >= diffLH) {
            lo = lowS[i - diffLH] - '0';
        }
        int hi = 9;
        if (limitHigh) {
            hi = highS[i] - '0';
        }

        long long res = 0;
        int d = lo;

        // 通过 limitLow 和 i 可以判断能否不填数字
        if (limitLow && i < diffLH) {
            // 不填数字，上界不受约束
            res = dfs(i + 1, 0, true, false);
            d = 1;  // 下面填数字，从1开始填
        }

        for (; d <= hi; d++) {
            res += dfs(i + 1, digitSum + d,
                       limitLow && (d == lo),
                       limitHigh && (d == hi));
        }

        if (!limitLow && !limitHigh) {
            memo[i][digitSum] = res;
        }

        return res;
    };

    return ans + dfs(0, 0, true, true);
}

int main() {
    init();

    long long l = 8, r = 10;
    long long result = countFancy(l, r);
    cout << result << endl;

    return0;
}