網易首頁 > 網易號 > 正文申請入駐

2026-05-07：給定范圍內平衡整數的數目。用go語言，給定兩個整數 low 和 high，統計在閉區間 [low, high] 內滿足“平衡”條件...

2026-05-07 00:11:19　來源: moonfdd

北京舉報

分享至

2026-05-07：給定范圍內平衡整數的數目。用go語言，給定兩個整數 low 和 high，統計在閉區間 [low, high] 內滿足“平衡”條件的整數個數。

對某個整數，先要求它至少是兩位數。接著把它的每一位數字按位置從左到右編號，最左邊是第 1 位。將所有在奇數位上的數字相加，得到奇數位數字和；再把所有在偶數位上的數字相加，得到偶數位數字和。如果這兩個和相等，則該整數被稱為“平衡整數”。

最終，你需要返回區間 [low, high] 中所有平衡整數的數量。

1 <= low <= high <= 1000000000000000。

輸入： low = 1, high = 100。

輸出： 9。

解釋：

1 到 100 之間共有 9 個平衡數，分別是 11、22、33、44、55、66、77、88 和 99。

題目來自力扣3791。

平衡整數計數代碼執行過程分步詳解一、代碼整體執行步驟（分階段）階段1：基礎邊界過濾

1. 函數接收low和high兩個超大整數（int64類型）；
2. 首先判斷：如果high < 11，直接返回0（因為最小的平衡數是11，沒有符合條件的數）；
3. 把low修正為max(low, 11)，排除1-10這些無效數字，縮小計算范圍。

階段2：數字格式化與預處理

1. 將修正后的low和high轉換成字符串：

? 目的：方便逐位處理每一位數字（數位DP的核心操作）；

2. 計算high的字符串長度n（最大數字的位數）：

? 示例中high=100，字符串是"100"，長度n=3；

3. 計算diffLH：high的位數 -low的位數，用于后續限制低位數字的枚舉范圍；

4.初始化記憶化數組（memo）：

? 二維數組：第一維是當前處理到第幾位（0~n-1），第二維是奇偶位差值的存儲位；
? 作用：緩存已經計算過的狀態，避免重復遞歸，大幅提升效率。

階段3：核心邏輯 —— 數位DFS遞歸（深度優先搜索）

定義遞歸函數dfs，這是數位DP的核心，參數含義：

?i：當前正在處理第i位數字（從0開始，對應數字的最高位）；
?diff：奇數位和 - 偶數位和的差值（最終diff=0就是平衡數）；
?limitLow：布爾值，當前位是否受low的下限約束；
?limitHigh：布爾值，當前位是否受high的上限約束。

遞歸執行流程：

子步驟1：遞歸終止條件

當i == n（所有位數處理完畢）：

? 判斷diff是否等于0：
- ? 等于0 → 是平衡數，返回1（計數+1）；
- ? 不等于0 → 不是平衡數，返回0。

子步驟2：記憶化緩存讀取

如果當前不受low和high的數字限制（可以自由枚舉0-9）：

1. 計算記憶數組的下標（將差值偏移為非負數，防止數組越界）；
2. 如果該狀態已經計算過 → 直接返回緩存的結果，不重復計算；
3. 如果沒計算過 → defer延遲存儲結果，計算完成后寫入緩存。

子步驟3：確定當前位的枚舉范圍

根據limitLow和limitHigh，限制當前位能選的數字：

? 下限lo：受約束時=low對應位的數字，不受約束時=0；
? 上限hi：受約束時=high對應位的數字，不受約束時=9；
? 示例：處理100的百位時，hi只能是1，不能超過high的數字。

子步驟4：枚舉當前位的所有合法數字

循環遍歷從lo到hi的每一個數字d：

1.更新差值diff：

? 第i位是奇數位（i%2=0）：diff = diff + d；
? 第i位是偶數位（i%2=1）：diff = diff - d；

2.更新約束條件：

? 下一位的limitLow= 當前約束且當前選的數字=下限；
? 下一位的limitHigh= 當前約束且當前選的數字=上限；

3. 遞歸調用下一位，累加所有合法結果。

子步驟5：返回累計結果

將當前位所有枚舉情況的結果求和，返回給上一層遞歸。

階段4：返回最終答案

啟動遞歸dfs(0, 0, true, true)（從第0位開始，初始差值為0，同時受low和high約束），函數返回的就是[low, high]內平衡整數的總數量。

二、針對示例輸入的執行驗證

輸入：low=1，high=100

1. 過濾：high=100≥11，low修正為11；
2. 格式化：low="11"（2位），high="100"（3位），n=3；
3. 遞歸枚舉所有11~100的兩位數、三位數：

? 兩位數（11~99）：奇數位=十位，偶數位=個位，十位=個位 → 11、22…99，共9個；
? 三位數（100）：奇數位（百位+個位）=1+0=1，偶數位（十位）=0，1≠0 → 不合法；

4. 最終結果=9，與題目輸出一致。

三、時間復雜度 & 額外空間復雜度 1. 時間復雜度

O(位數 × 最大差值 × 10)

? 核心變量：

1. 數字最大位數n：101?對應15位；
2. 奇偶位最大差值：每位最大9，總差值≤15×9=135；
3. 每位枚舉數字：0~9共10種選擇；

? 總計算量：15 × 135 × 10 =20250（常數級極小計算量）；

? 本質：O(1) 常數時間復雜度（因為位數固定最大15，無變量級增長）。

2. 額外空間復雜度

O(位數 × 最大差值)

? 核心占用：記憶化數組memo；
? 大小：15（位數） × 135（最大差值）=2025個int64元素；
? 遞歸棧空間：最大深度=數字位數=15，可忽略；
? 本質：O(1) 常數空間復雜度。

總結

1. 代碼核心是數位DP+記憶化遞歸，專門解決超大范圍數字的數位統計問題；
2. 執行流程：邊界過濾→數字格式化→記憶化DFS逐位枚舉→統計合法平衡數；
3. 時間復雜度：O(1)（常數級）；
4. 額外空間復雜度：O(1)（常數級）。

Go完整代碼如下：

package main

 import (
    "fmt"
    "strconv"
)

 func countBalanced(low, high int64)int64 {
    // 最小的滿足要求的數是 11
    if high < 11 {
        return0
    }

     low = max(low, 11)
    lowS := strconv.FormatInt(low, 10)
    highS := strconv.FormatInt(high, 10)
    n := len(highS)
    diffLH := n - len(lowS)
    memo := make([][]int64, n)
    for i := range memo {
        // diff 至少 floor(n/2) * 9，至多 ceil(n/2) * 9，值域大小 n * 9
        memo[i] = make([]int64, n*9+1)
    }

     var dfs func(int, int, bool, bool)int64
    dfs = func(i, diff int, limitLow, limitHigh bool) (res int64) {
        if i == n {
            if diff != 0 { // 不合法
                return0
            }
            return1
        }
        if !limitLow && !limitHigh {
            p := &memo[i][diff+n/2*9] // 保證下標非負
            if *p > 0 {
                return *p - 1
            }
            deferfunc() { *p = res + 1 }() // 記憶化的時候加一，這樣 memo 可以初始化成 0
        }

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

         for d := lo; d <= hi; d++ {
            // 下一個位置奇偶性翻轉
            res += dfs(i+1, diff+(1-i%2*2)*d,
                limitLow && d == lo, limitHigh && d == hi)
        }
        return
    }
    return dfs(0, 0, true, true)
}

 func main() {
    low := int64(1)
    high := int64(100)
    result := countBalanced(low, high)
    fmt.Println(result)
}

Python完整代碼如下：

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

 def count_balanced(low: int, high: int) -> int:
    if high < 11:
        return0

     low = max(low, 11)
    low_str = str(low)
    high_str = str(high)
    n = len(high_str)
    diff_lh = n - len(low_str)

     # 記憶化數組：memo[i][diff_offset]
    # diff 的取值范圍：[-max_diff, max_diff]，max_diff = (n // 2 + (n % 2)) * 9
    max_possible_diff = ((n + 1) // 2) * 9
    memo = [[-1] * (2 * max_possible_diff + 1) for _ in range(n)]

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

         # 記憶化：只有當不受 low 和 high 限制時才能復用
        if not limit_low and not limit_high:
            idx = diff + max_possible_diff
            if memo[i][idx] != -1:
                return memo[i][idx]

         lo = 0
        if limit_low and i >= diff_lh:
            lo = int(low_str[i - diff_lh])

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

         total = 0
        for d in range(lo, hi + 1):
            # 根據位置 i 的奇偶性決定 diff 的增減
            # i=0 是最高位（視為偶數位，與 Go 版本一致）
            sign = 1if i % 2 == 0else-1
            total += dfs(i + 1, diff + sign * d,
                         limit_low and d == lo,
                         limit_high and d == hi)

         if not limit_low and not limit_high:
            memo[i][diff + max_possible_diff] = total
        return total

     return dfs(0, 0, True, True)

 if __name__ == "__main__":
    low_val = 1
    high_val = 100
    result = count_balanced(low_val, high_val)
    print(result)

C++完整代碼如下：

  

  

  

   


 using namespace std;

 long long countBalanced(long long low, long long high) {
    // 最小的滿足要求的數是 11
    if (high < 11) {
        return0;
    }

     low = max(low, 11LL);
    string lowS = to_string(low);
    string highS = to_string(high);
    int n = highS.length();
    int diffLH = n - lowS.length();

     // 初始化記憶化數組，使用 -1 表示未計算
    vector 
 
 > memo(n, vector 
 
 (n *  
 
 9 + 1, -1));

     // 使用函數對象實現遞歸
    function 
 
 int 
 ,  
 int 
 ,  
 bool 
 ,  
 bool 
 )> dfs = [&]( 
 int 
  i,  
 int 
  diff,  
 bool 
  limitLow,  
 bool 
  limitHigh) -> long long { 
 
 
          
 if 
  (i == n) { 
 
 
              
 return 
  diff ==  
 0 
  ?  
 1 
  :  
 0 
 ; 
 
 
         } 
 
 
 
 
          
 if 
  (!limitLow && !limitHigh) { 
 
 
              
 int 
  idx = diff + n /  
 2 
  *  
 9 
 ; 
 
 
              
 if 
  (idx >=  
 0 
  && idx < n *  
 9 
  +  
 1 
  && memo[i][idx] !=  
 -1 
 ) { 
 
 
                  
 return 
  memo[i][idx]; 
 
 
             } 
 
 
         } 
 
 
 
 
          
 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 
 ; 
 
 
          
 for 
  ( 
 int 
  d = lo; d <= hi; d++) { 
 
 
              
 // 下一個位置奇偶性翻轉 
 
 
             res += dfs(i +  
 1 
 , diff + ( 
 1 
  - i %  
 2 
  *  
 2 
 ) * d, 
 
 
                        limitLow && d == lo, limitHigh && d == hi); 
 
 
         } 
 
 
 
 
          
 if 
  (!limitLow && !limitHigh) { 
 
 
              
 int 
  idx = diff + n /  
 2 
  *  
 9 
 ; 
 
 
              
 if 
  (idx >=  
 0 
  && idx < n *  
 9 
  +  
 1 
 ) { 
 
 
                 memo[i][idx] = res; 
 
 
             } 
 
 
         } 
 
 
 
 
          
 return 
  res; 
 
 
     }; 
 
 
 
 
      
 return 
  dfs( 
 0 
 ,  
 0 
 ,  
 true 
 ,  
 true 
 ); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     long long low =  
 1 
 ; 
 
 
     long long high =  
 100 
 ; 
 
 
     long long result = countBalanced(low, high); 
 
 
     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.