2026-08-03：统计网格路径中好整数的数目。用go语言，给定一个整数区间 [l, r]，以及一个方向字符串 directions，这个字符串中恰好包含 3|下标|spiderlinebreak

分享至

2026-08-03：统计网格路径中好整数的数目。用go语言，给定一个整数区间 [l, r]，以及一个方向字符串 directions，这个字符串中恰好包含 3 个字母 'D' 和 3 个字母 'R'。

对于区间里的每个整数 x，先将它补成 16 位数字：如果位数不足 16 位，就在左侧补 0。然后把这 16 个数字按行从左到右依次填入一个 4 × 4 的方格中，也就是前 4 个数字填第一行，接下来 4 个数字填第二行，依此类推。

接着，从方格左上角出发，按照 directions 中的顺序依次移动：遇到 'D' 就向下走一格，遇到 'R' 就向右走一格。过程中把经过的格子里的数字记录下来，起点也算在内，因此一共会得到 7 个数字。

如果这 7 个数字组成的序列是非递减的，就称 x 是一个好整数。最终需要统计并返回 [l, r] 内好整数的个数。

1 <= l <= r <= 9000000000000000。

directions.length == 6。

directions 由恰好三个 'D' 字符和三个 'R' 字符组成。

输入： l = 8, r = 10, directions = "DDDRRR"。

输出： 2。

解释：

x = 8 的网格：

路径：(0,0) → (1,0) → (2,0) → (3,0) → (3,1) → (3,2) → (3,3)

访问的数字序列为 [0, 0, 0, 0, 0, 0, 8]。

由于访问的数字序列是非递减的，因此 8 是一个好整数。

x = 9 的网格：

访问的数字序列为 [0, 0, 0, 0, 0, 0, 9]。

由于访问的数字序列是非递减的，因此 9 是一个好整数。

x = 10 的网格：

访问的数字序列为 [0, 0, 0, 0, 0, 1, 0]。

由于访问的数字序列不是非递减的，因此 10 不是一个好整数。

因此，只有 8 和 9 是好整数，在该范围内总共有 2 个好整数。

题目来自力扣3906。

步骤一：问题建模与前缀和转化

题目要求在区间[l, r]内统计“好整数”的个数。
一个好整数x的定义包含三个要素：

• 将x补足到16 位（不足左侧补0）。
• 按行优先填入4×4 网格，格子编号0到15（左上角0，右下角15）。
• 按照给定的方向字符串directions（恰好 3 个'D'、3 个'R'）从左上角出发，收集途经 7 个格子内的数字，若这个长度为 7 的数字序列非递减，则x为好整数。

为便于计数，算法转化为求前缀个数：
设F(N)表示[0, N]中好整数的个数，则答案 =F(r) - F(l-1)。
代码中实际实现了函数solve(s)，它返回小于数字串s的好整数个数。
因此F(r) = solve(str(r+1))，F(l-1) = solve(str(l))（这里l已经被当作下界传入，相当于l是原l，减法由solve(highS) - solve(lowS)直接完成，其中highS = r+1,lowS = l）。
这样做的好处是：可以用统一的上界比较逻辑处理所有情况，并且自然地包含前导零。

步骤二：确定数字的位数与路径映射

• 取highS = str(r+1)，令n = len(highS)。
因为r最大为9×10^15（16 位），r+1可能为10^16（17 位），故n为 16 或 17。
• 将lowS = str(l)左补'0'至长度n，使两个字符串长度一致，方便数位 DP 对齐处理。
• 原网格有 16 个格子，映射到线性下标0…15。在n位数字串中，真正的 16 个格子位于最低的 16 位，即下标n-16到n-1。高位（如果有第 17 位）只能是0。
• 根据directions的 6 步移动，模拟出在 4×4 网格中的路径：
- • 起点为左上角（线性下标0）。
- • 每步'R'表示向右，下标+1；'D'表示向下，下标+4。
- • 由于路径长度为 7（含起点），且只关心网格中的格子，路径下标只会落在0…15内。
• 将这些路径下标映射到n位数字串的对应位上：
网格下标g对应数字串下标pos = (n - 16) + g。
用一个布尔数组inPath标记这 7 个位置，表示这些位上的数字必须构成非递减序列。

步骤三：预处理组合数与后缀信息

为了快速计算非递减序列的方案数，首先预处理组合数comb[i][j]（i最大约n+10，这里maxM=7，实际只需到 17 左右）。组合数用于计算“从若干数字中可重复地选取若干项且保持非递减”的组合数（即插板法）。

接着计算后缀数组suf：

•suf[i]表示在数字串下标[i, n-1]范围内，有多少位位于路径上（即inPath为真的位数）。
• 这个值在后面会被用来快速知道“剩余未处理位中还有m = suf[i+1]个路径位”。

步骤四：实现数位 DP 函数solve(s)

函数solve(s)统计所有n位数字串（含前导零）中字典序严格小于s且满足路径非递减约束的个数。
遍历i从0到n-1（高位到低位），维护变量pre：表示路径上前一个已确定位的数字值（初始pre = 0，因为序列非递减且数字为 0–9）。

对于当前位i，设上限数字hi = s[i] - '0'，剩余路径位个数m = suf[i+1]。

情况 1：当前位i不在路径上

• 这一位的数字没有任何单调性约束，可以独立选取。
• 为了确保构成的数严格小于s，我们让这一位取0到hi-1中的任意值（共hi种），对于每种取值，后续位的填法分为两部分：

1.剩余m个路径位：它们必须形成一个以pre为下限的非递减序列。从数字pre到9共10 - pre种数字，可重复地取m个并保持非递减。根据组合数学，方案数为C(m + 9 - pre, m)。
2.剩余的非路径位：共(n-1-i) - m位，每位可任意填0–9，方案数为10^{(n-1-i) - m}。

• 两者相乘再乘以hi，累加到结果中。

• 随后，隐式地将当前位固定为hi（即等于上限），不做额外操作，直接进入下一位循环（通过continue实现），因为此时仍需继续匹配上界。

情况 2：当前位i在路径上

• 路径序列要求非递减，因此当前位可选的数字d必须满足pre ≤ d < hi。
• 若hi < pre，则连最小的合法值pre都超过了上限，无法填任何合法数字，直接终止循环。
• 否则hi ≥ pre，对每一个合法的d(pre到hi-1)，剩余位的方案数为：
- • 路径位：从d到9中可重复取m个非递减，方案数为C(m + 9 - d, m)。
- • 非路径位：仍然为10^{(n-1-i) - m}。
• 将d从pre到hi-1的方案数求和。利用组合恒等式，该和可化简为：
(C(m + 10 - pre, m + 1) - C(m + 10 - hi, m + 1))。
• 将求和结果乘以10^{(n-1-i) - m}并累加。
• 处理完所有小于hi的分支后，将pre更新为hi，表示当前位取hi以继续匹配上界，进入下一位。

遍历结束后，函数返回累加的结果res，这就是严格小于s的好整数个数。

步骤五：计算最终答案

• 调用solve(highS)得到[0, r]的好整数个数（因为highS = r+1，统计小于r+1即是≤ r）。
• 调用solve(lowS)得到[0, l-1]的好整数个数（lowS = l，统计小于l即是≤ l-1）。
• 两者相减即为区间[l, r]内的好整数个数。

复杂度分析

•时间复杂度：
组合数预处理为常数时间（规模与maxM相关，不超过18×8）。
countGoodIntegersOnPath中，字符串转换、路径标记、后缀数组计算均是O(n)，其中n为r+1的十进制位数，最大为 17。
solve函数遍历n位，每次迭代仅进行常数次组合数查表、幂运算和算术操作，因此solve也是O(n)。
总体时间复杂度为O(n)，由于n ≤ 17，实际上可以视为O(1)，与区间大小无关。
•额外空间复杂度：
组合数表格占用常数空间。
字符串、inPath、suf等数组长度均为O(n)，常数上界很小。
递归或栈空间为O(1)。
因此总额外空间复杂度为O(n)，实际也是O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
    "strconv"
    "strings"
)

 const maxM = 7

 var comb [maxM + 10][maxM + 1]int

 func init() {
    // 预处理组合数
    for i := range comb {
        comb[i][0] = 1
        for j := 1; j < min(i+1, len(comb[i])); j++ {
            comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
        }
    }
}

 func countGoodIntegersOnPath(l, r int64, directions string) int64 {
    highS := strconv.FormatInt(r+1, 10) // 注意这里加一了
    n := len(highS)
    lowS := strconv.FormatInt(l, 10)
    lowS = strings.Repeat("0", n-len(lowS)) + lowS

     inPath := make([]bool, n)
    pos := n - 16 // 右下角是下标 n-1，那么左上角是下标 n-16
    for _, d := range directions {
        if pos >= 0 { // 只需要对网格图中的后 n 个格子做标记
            inPath[pos] = true // 标记在路径中的格子
        }
        if d == 'R' { // 往右
            pos++
        } else { // 往下
            pos += 4 // 相当于往右数 4 个位置
        }
    }
    inPath[n-1] = true // 终点一定在路径中

     // suf[i] 表示后缀 [i, n-1] 在路径中的下标个数
    suf := make([]int, n+1)
    for i := n - 1; i >= 0; i-- {
        suf[i] = suf[i+1]
        if inPath[i] {
            suf[i]++
        }
    }

     // 计算小于 r 的合法整数个数
    solve := func(r string) (res int) {
        pre := 0
        for i, ch := range r {
            hi := int(ch - '0')
            m := suf[i+1]
            if !inPath[i] {
                res += hi * comb[m+9-pre][m] * int(math.Pow10(n-1-i-m))
                continue
            }
            if hi < pre {
                break
            }
            res += (comb[m+10-pre][m+1] - comb[m+10-hi][m+1]) * int(math.Pow10(n-1-i-m))
            pre = hi // 这一位填 hi，继续计算剩余数位的方案数
        }
        return res
    }

     return int64(solve(highS) - solve(lowS))
}

 func main() {
    l := 8
    r := 10
    directions := "DDDRRR"
    result := countGoodIntegersOnPath(int64(l), int64(r), directions)
    fmt.Println(result)
}

Python完整代码如下：

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

 import math

 def count_good_integers_on_path(l: int, r: int, directions: str) -> int:
    # 将上界加一，方便计算小于等于r的个数
    high_s = str(r + 1)
    n = len(high_s)
    # 将下界补零到相同长度（用于数位DP）
    low_s = str(l).zfill(n)

     # 标记路径上的格子（对应16位数字的最后16位）
    in_path = [False] * n
    pos = n - 16          # 起始位置（对应16位网格的左上角）
    for d in directions:
        if pos >= 0:
            in_path[pos] = True
        if d == 'R':
            pos += 1
        else:             # 'D'
            pos += 4
    in_path[n - 1] = True   # 终点一定在路径上

     # suf[i] 表示后缀 [i, n-1] 中路径格子的个数
    suf = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suf[i] = suf[i + 1] + (1 if in_path[i] else 0)

     # 计算严格小于 s 的合法数字个数
    def solve(s: str) -> int:
        res = 0
        pre = 0  # 上一个路径格子的数字
        for i, ch in enumerate(s):
            hi = int(ch)
            m = suf[i + 1]   # 当前位置之后（不包括i）路径格子数
            if not in_path[i]:
                # 当前位置不在路径上，可以自由选择0..hi-1
                if hi > 0:
                    ways = math.comb(m + 9 - pre, m)
                    res += hi * ways * (10 ** (n - 1 - i - m))
                # pre 保持不变，因为该位置不影响路径序列
                continue
            else:
                # 当前位置在路径上，必须保证 >= pre
                if hi < pre:
                    break
                # 当前位可取 pre .. hi-1 的所有情况
                total = math.comb(m + 10 - pre, m + 1)
                ge = math.comb(m + 10 - hi, m + 1)   # 当前位 >= hi 的方案数
                res += (total - ge) * (10 ** (n - 1 - i - m))
                pre = hi   # 更新上一个路径数字为当前选择
        return res

     # 区间计数 = (小于 r+1 的个数) - (小于 l 的个数)
    return solve(high_s) - solve(low_s)

 if __name__ == "__main__":
    l, r = 8, 10
    directions = "DDDRRR"
    result = count_good_integers_on_path(l, r, directions)
    print(result)

C++完整代码如下：

  

  

    


 using namespace std;

 const int MAX_M = 7;
long long comb[MAX_M + 10][MAX_M + 1];

 // 预处理组合数
void initComb() {
    for (int i = 0; i < MAX_M + 10; i++) {
        comb[i][0] = 1;
        for (int j = 1; j < min(i + 1, MAX_M + 1); j++) {
            comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
        }
    }
}

 // 计算小于 r 的合法整数个数（这里的r是字符串形式）
int solve(const string& r, const vector& inPath, const vector& suf, int n) {
    int res = 0;
    int pre = 0;  // 上一个路径格子的数字

     for (int i = 0; i < n; i++) {
        int hi = r[i] - '0';
        int m = suf[i + 1];  // 当前位置之后路径格子的个数

         if (!inPath[i]) {
            // 当前位置不在路径上，可以自由选择
            res += hi * comb[m + 9 - pre][m] * (int)pow(10, n - 1 - i - m);
            continue;
        }

         // 当前位置在路径上
        if (hi < pre) {
            break;  // 无法满足非递减条件
        }

         // 当前位可取 pre..hi-1 的所有情况
        res += (comb[m + 10 - pre][m + 1] - comb[m + 10 - hi][m + 1]) * (int)pow(10, n - 1 - i - m);
        pre = hi;  // 更新上一个路径数字为当前选择
    }

     return res;
}

 long long countGoodIntegersOnPath(long long l, long long r, string directions) {
    // 将上界加一，方便计算小于等于r的个数
    string highS = to_string(r + 1);
    int n = highS.length();

     // 将下界补零到相同长度
    string lowS = to_string(l);
    lowS = string(n - lowS.length(), '0') + lowS;

     // 标记路径上的格子（对应16位数字的最后16位）
    vector inPath(n, false);
    int pos = n - 16;  // 起始位置（对应16位网格的左上角）

     for (char d : directions) {
        if (pos >= 0) {
            inPath[pos] = true;  // 标记在路径中的格子
        }
        if (d == 'R') {
            pos++;  // 向右
        } else {  // 'D'
            pos += 4;  // 向下，相当于向右移动4个位置
        }
    }
    inPath[n - 1] = true;  // 终点一定在路径中

     // suf[i] 表示后缀 [i, n-1] 中路径格子的个数
    vector suf(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = suf[i + 1];
        if (inPath[i]) {
            suf[i]++;
        }
    }

     // 区间计数 = (小于 r+1 的个数) - (小于 l 的个数)
    int result = solve(highS, inPath, suf, n) - solve(lowS, inPath, suf, n);
    return (long long)result;
}

 int main() {
    // 预处理组合数
    initComb();

     // 测试用例
    long long l = 8;
    long long r = 10;
    string directions = "DDDRRR";
    long long result = countGoodIntegersOnPath(l, r, directions);
    cout << result << endl;

     return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。

特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.