Leetcode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Leetcode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K
- 1. 解题思路
- 2. 代码实现

题目链接：3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K

1. 解题思路

这一题我的思路上就是一个二分的思路，先确定一个上下界，然后不断通过二分来找到最大的price不超过k的值。

因此，剩下的问题就在于对于任何一个给定的 $n$ ，如果确定 $\sum\limits_{i=1}^{n}p(i)$ 的结果。

这里，我们使用的是一个迭代的结果，我们将所有数用二进制进行表示，考察 $n$ 的最大一位（不妨设为第 $k$ 位），如果这个位刚好是 $x$ 的整数倍且为 $1$ ，那么考察 $2^{k-1}$ 到 $n$ 的这段区间，其贡献的price就是 $n-2^{k-1}+1$ 联合上 $\sum\limits_{i=2^{k-1}}^{n} p(i - 2^{2^{k-1}})$ 的部分，以及剩下的 $1$ 到 $2^{k-1}-1$ 的部分。

同样的，如果最高位不为 $x$ 的整倍数，那么直接忽略掉最高位，结果就是 $\sum\limits_{i=2^{k-1}}^{n} p(i - 2^{2^{k-1}})$ 的部分与剩下的 $1$ 到 $2^{k-1}-1$ 的部分之和。

我们将其翻译为代码语言即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        
        @lru_cache(None)
        def dp(num):
            s = bin(num)[2:]
            n = len(s)
            if n < x or num == 0:
                return 0
            a, b = num ^ (1 << (n-1)), 1<<(n-1)
            if n % x == 0:
                return a+1 + dp(num-b) + dp(b-1)
            else:
                return dp(num-b) + dp(b-1)
            
        i, j = 0, 10**16
        while j - i > 1:
            m = (i+j) // 2
            if dp(m) > k:
                j = m
            else:
                i = m
        return i

提交代码评测得到：耗时412ms，占用内存26MB。文章来源地址https://www.toymoban.com/news/detail-807071.html

到了这里，关于Leetcode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！