Hard

题目描述

给你两个整数 low 和 high。

如果一个整数同时满足以下两个条件，我们称它为平衡整数：

  • 它至少包含两位数字。
  • 奇数位置上数字的和等于偶数位置上数字的和（最左边的数字位置为 1）。

返回区间 [low, high]（包含边界）内平衡整数的数目。

示例 1：

输入：low = 1, high = 100
输出：9
解释：1 到 100 之间的 9 个平衡数字是 11, 22, 33, 44, 55, 66, 77, 88, 和 99。

示例 2：

输入：low = 120, high = 129
输出：1
解释：只有 121 是平衡的，因为奇数位置和偶数位置上的数字和都是 2。

示例 3：

输入：low = 1234, high = 1234
输出：0
解释：1234 不是平衡的，因为奇数位置数字和 (1 + 3 = 4) 不等于偶数位置数字和 (2 + 4 = 6)。

约束条件：

  • 1 <= low <= high <= 10^15

解题思路

这是一道数位动态规划的经典题目。核心思路是计算 f(high) - f(low-1)，其中 f(x) 表示区间 [1, x] 内平衡整数的数目。

解题思路：

  1. 数位DP状态设计：我们需要维护以下状态：

    • pos：当前填写的位置
    • diff：奇数位数字和减去偶数位数字和的差值
    • tight：是否受到上界限制
    • started：是否已经开始填写非零数字（用于跳过前导零）

  2. 状态转移：对于每一位，我们可以选择填入 0-9 的数字，需要：

    • 更新差值：如果当前位置是奇数位，加上当前数字；如果是偶数位，减去当前数字
    • 更新 tight 状态：如果当前数字等于上界对应位，保持 tight；否则置为 false
    • 更新 started 状态：如果填入非零数字，置为 true

  3. 边界条件：

    • 当填完所有位时，检查差值是否为 0 且至少有两位数字（started 为 true 且原数不是一位数）
    • 处理前导零，只有在 started 为 true 时才开始计算位置的奇偶性

  4. 优化：使用记忆化搜索避免重复计算相同状态。

关键点：差值的范围是有限的（大约在 [-405, 405] 之间），可以通过偏移映射到数组索引。

代码实现

class Solution {
public:
    long long countBalanced(long long low, long long high) {
        return solve(high) - solve(low - 1);
    }
    
private:
    string num;
    int dp[20][900][2][2]; // pos, diff+450, tight, started
    
    long long solve(long long x) {
        if (x <= 0) return 0;
        num = to_string(x);
        memset(dp, -1, sizeof(dp));
        return dfs(0, 450, 1, 0); // diff offset by 450
    }
    
    int dfs(int pos, int diff, int tight, int started) {
        if (pos == num.length()) {
            return started && diff == 450; // diff should be 0
        }
        
        if (dp[pos][diff][tight][started] != -1) {
            return dp[pos][diff][tight][started];
        }
        
        int limit = tight ? (num[pos] - '0') : 9;
        int res = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newTight = tight && (digit == limit);
            int newStarted = started || (digit > 0);
            int newDiff = diff;
            
            if (newStarted) {
                // Position counting starts from 1, so pos+1 is the actual position
                if ((pos + 1) % 2 == 1) { // odd position
                    newDiff += digit;
                } else { // even position
                    newDiff -= digit;
                }
            }
            
            res += dfs(pos + 1, newDiff, newTight, newStarted);
        }
        
        return dp[pos][diff][tight][started] = res;
    }
};

class Solution:
    def countBalanced(self, low: int, high: int) -> int:
        def solve(x):
            if x <= 0:
                return 0
            
            s = str(x)
            n = len(s)
            memo = {}
            
            def dfs(pos, diff, tight, started):
                if pos == n:
                    return 1 if started and diff == 0 else 0
                
                if (pos, diff, tight, started) in memo:
                    return memo[(pos, diff, tight, started)]
                
                limit = int(s[pos]) if tight else 9
                res = 0
                
                for digit in range(limit + 1):
                    new_tight = tight and (digit == limit)
                    new_started = started or (digit > 0)
                    new_diff = diff
                    
                    if new_started:
                        # Position counting starts from 1
                        if (pos + 1) % 2 == 1:  # odd position
                            new_diff += digit
                        else:  # even position
                            new_diff -= digit
                    
                    res += dfs(pos + 1, new_diff, new_tight, new_started)
                
                memo[(pos, diff, tight, started)] = res
                return res
            
            return dfs(0, 0, True, False)
        
        return solve(high) - solve(low - 1)

public class Solution {
    private string num;
    private Dictionary<(int, int, bool, bool), long> memo;
    
    public long CountBalanced(long low, long high) {
        return Solve(high) - Solve(low - 1);
    }
    
    private long Solve(long x) {
        if (x <= 0) return 0;
        
        num = x.ToString();
        memo = new Dictionary<(int, int, bool, bool), long>();
        return Dfs(0, 0, true, false);
    }
    
    private long Dfs(int pos, int diff, bool tight, bool started) {
        if (pos == num.Length) {
            return (started && diff == 0) ? 1 : 0;
        }
        
        var key = (pos, diff, tight, started);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        
        int limit = tight ? (num[pos] - '0') : 9;
        long res = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            bool newTight = tight && (digit == limit);
            bool newStarted = started || (digit > 0);
            int newDiff = diff;
            
            if (newStarted) {
                // Position counting starts from 1
                if ((pos + 1) % 2 == 1) { // odd position
                    newDiff += digit;
                } else { // even position
                    newDiff -= digit;
                }
            }
            
            res += Dfs(pos + 1, newDiff, newTight, newStarted);
        }
        
        memo[key] = res;
        return res;
    }
}

var countBalanced = function(low, high) {
    function countBalancedUpTo(num) {
        const s = num.toString();
        const n = s.length;
        
        if (n < 2) return 0;
        
        const memo = new Map();
        
        function dp(pos, tight, evenSum, oddSum, started) {
            if (pos === n) {
                return started && evenSum === oddSum ? 1 : 0;
            }
            
            const key = `${pos},${tight},${evenSum},${oddSum},${started}`;
            if (memo.has(key)) return memo.get(key);
            
            const limit = tight ? parseInt(s[pos]) : 9;
            let result = 0;
            
            for (let digit = 0; digit <= limit; digit++) {
                const newStarted = started || digit > 0;
                const newTight = tight && (digit === limit);
                
                let newEvenSum = evenSum;
                let newOddSum = oddSum;
                
                if (newStarted) {
                    if (pos % 2 === 0) {
                        newOddSum += digit;
                    } else {
                        newEvenSum += digit;
                    }
                }
                
                result += dp(pos + 1, newTight, newEvenSum, newOddSum, newStarted);
            }
            
            memo.set(key, result);
            return result;
        }
        
        return dp(0, true, 0, 0, false);
    }
    
    return countBalancedUpTo(high) - countBalancedUpTo(low - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(log(high) × 900 × 2 × 2 × 10) = O(log(high))
空间复杂度O(log(high) × 900 × 2 × 2) = O(log(high))

其中 900 是差值的可能取值范围（约 [-450, 450]），10 是每位可能的数字选择。