Medium

题目描述

给你一个整数 k 和一个整数 x。数字 num 的价格是通过计算其二进制表示中位置为 x、2x、3x 等位置上的置位位数来计算的，从最低有效位开始计算。下表包含了如何计算价格的示例：

xnum二进制表示价格
1130000011013
2130000011011
22330111010013
3130000011011
33621011010102

数字 num 的累积价格是从 1 到 num 所有数字的价格总和。如果数字的累积价格小于或等于 k，则认为该数字是便宜的。

返回最大的便宜数字。

示例 1:

输入: k = 9, x = 1
输出: 6
解释: 如下表所示，6 是最大的便宜数字。

| x | num | 二进制表示 | 价格 | 累积价格 |
|---|-----|-----------|------|----------|
| 1 | 1   | 001       | 1    | 1        |
| 1 | 2   | 010       | 1    | 2        |
| 1 | 3   | 011       | 2    | 4        |
| 1 | 4   | 100       | 1    | 5        |
| 1 | 5   | 101       | 2    | 7        |
| 1 | 6   | 110       | 2    | 9        |
| 1 | 7   | 111       | 3    | 12       |

示例 2:

输入: k = 7, x = 2
输出: 9
解释: 如下表所示，9 是最大的便宜数字。

| x | num | 二进制表示 | 价格 | 累积价格 |
|---|-----|-----------|------|----------|
| 2 | 1   | 0001      | 0    | 0        |
| 2 | 2   | 0010      | 1    | 1        |
| 2 | 3   | 0011      | 1    | 2        |
| 2 | 4   | 0100      | 0    | 2        |
| 2 | 5   | 0101      | 0    | 2        |
| 2 | 6   | 0110      | 1    | 3        |
| 2 | 7   | 0111      | 1    | 4        |
| 2 | 8   | 1000      | 1    | 5        |
| 2 | 9   | 1001      | 1    | 6        |
| 2 | 10  | 1010      | 2    | 8        |

约束条件:

  • 1 <= k <= 10^15
  • 1 <= x <= 8

提示:

  • 二分搜索答案
  • 在二分搜索的每一步中，应该计算第 i 个位置上的置位位数，然后计算它们的总和

解题思路

这是一道数位动态规划结合二分搜索的题目。

首先分析问题的本质：我们需要找到最大的数字 num，使得从 1 到 num 的所有数字的累积价格不超过 k。由于累积价格随着 num 单调递增，我们可以使用二分搜索来找到答案。

关键在于如何高效计算累积价格。对于给定的上界 num，我们需要计算所有小于等于 num 的数字在指定位置（x, 2x, 3x, ...）上的置位位数总和。

这可以通过数位 DP 来解决：

  1. 我们按位构造数字，对于每一位，可以选择填入 0 或 1
  2. 维护状态：当前位置、是否受到上界限制、当前价格贡献
  3. 对于位置是 x 的倍数的位，如果填入 1，则价格加 1

数位 DP 的状态转移：

  • 如果当前位不是 x 的倍数：无论填 0 还是 1，价格都不变
  • 如果当前位是 x 的倍数且填 1：价格加 1

通过记忆化搜索，我们可以高效地计算出累积价格，然后结合二分搜索找到最大的满足条件的数字。

时间复杂度主要由二分搜索的层数（约 60 层）和每次数位 DP 的计算复杂度决定。

代码实现

class Solution {
public:
    long long findMaximumNumber(long long k, int x) {
        long long left = 1, right = (k + 1) << x;
        
        auto calculatePrice = [&](long long num) -> long long {
            string s = "";
            for (long long temp = num; temp > 0; temp >>= 1) {
                s = char('0' + (temp & 1)) + s;
            }
            
            int n = s.length();
            vector<vector<long long>> memo(n, vector<long long>(2, -1));
            
            function<long long(int, bool)> dfs = [&](int pos, bool limit) -> long long {
                if (pos == n) return 0;
                
                if (!limit && memo[pos][limit] != -1) {
                    return memo[pos][limit];
                }
                
                int maxDigit = limit ? (s[pos] - '0') : 1;
                long long result = 0;
                
                for (int digit = 0; digit <= maxDigit; digit++) {
                    bool newLimit = limit && (digit == maxDigit);
                    long long contribution = 0;
                    
                    if (digit == 1 && (n - pos) % x == 0) {
                        contribution = 1;
                    }
                    
                    result += dfs(pos + 1, newLimit) + contribution * (1LL << (n - pos - 1));
                }
                
                if (!limit) {
                    memo[pos][limit] = result;
                }
                
                return result;
            };
            
            return dfs(0, true);
        };
        
        while (left < right) {
            long long mid = left + (right - left + 1) / 2;
            if (calculatePrice(mid) <= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        def calculatePrice(num):
            s = bin(num)[2:]
            n = len(s)
            
            from functools import lru_cache
            
            @lru_cache(None)
            def dfs(pos, limit):
                if pos == n:
                    return 0
                
                max_digit = int(s[pos]) if limit else 1
                result = 0
                
                for digit in range(max_digit + 1):
                    new_limit = limit and (digit == max_digit)
                    contribution = 0
                    
                    if digit == 1 and (n - pos) % x == 0:
                        contribution = 1
                    
                    result += dfs(pos + 1, new_limit) + contribution * (1 << (n - pos - 1))
                
                return result
            
            return dfs(0, True)
        
        left, right = 1, (k + 1) << x
        
        while left < right:
            mid = (left + right + 1) // 2
            if calculatePrice(mid) <= k:
                left = mid
            else:
                right = mid - 1
        
        return left

public class Solution {
    public long FindMaximumNumber(long k, int x) {
        long left = 1, right = (k + 1) << x;
        
        Func<long, long> calculatePrice = (num) => {
            string s = Convert.ToString(num, 2);
            int n = s.Length;
            var memo = new Dictionary<(int, bool), long>();
            
            Func<int, bool, long> dfs = null;
            dfs = (pos, limit) => {
                if (pos == n) return 0;
                
                var key = (pos, limit);
                if (!limit && memo.ContainsKey(key)) {
                    return memo[key];
                }
                
                int maxDigit = limit ? (s[pos] - '0') : 1;
                long result = 0;
                
                for (int digit = 0; digit <= maxDigit; digit++) {
                    bool newLimit = limit && (digit == maxDigit);
                    long contribution = 0;
                    
                    if (digit == 1 && (n - pos) % x == 0) {
                        contribution = 1;
                    }
                    
                    result += dfs(pos + 1, newLimit) + contribution * (1L << (n - pos - 1));
                }
                
                if (!limit) {
                    memo[key] = result;
                }
                
                return result;
            };
            
            return dfs(0, true);
        };
        
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (calculatePrice(mid) <= k) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

var findMaximumNumber = function(k, x) {
    function countBits(num, x) {
        if (num <= 0) return 0;
        
        let total = 0;
        let bit = x;
        
        while (bit <= 64) {
            let cycle = 1n << BigInt(bit);
            let completeGroups = (BigInt(num) + 1n) / cycle;
            let remainder = (BigInt(num) + 1n) % cycle;
            
            total += Number(completeGroups * (cycle / 2n));
            
            if (remainder > cycle / 2n) {
                total += Number(remainder - cycle / 2n);
            }
            
            bit += x;
        }
        
        return total;
    }
    
    let left = 1;
    let right = 10n ** 15n;
    let result = 0;
    
    while (left <= right) {
        let mid = (left + right) / 2n;
        let accumulated = countBits(Number(mid), x);
        
        if (accumulated <= k) {
            result = Number(mid);
            left = mid + 1n;
        } else {
            right = mid - 1n;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log²k × x)二分搜索 O(log k) 层，每次数位 DP 需要 O(log k × x) 时间
空间复杂度O(log k × x)记忆化搜索的存储空间