-
Leetcode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K
- 1. 解題思路
- 2. 代碼實(shí)現(xiàn)
- 題目鏈接：3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K
1. 解題思路
這一題我的思路上就是一個(gè)二分的思路，先確定一個(gè)上下界，然后不斷通過二分來找到最大的price不超過k的值。
因此，剩下的問題就在于對(duì)于任何一個(gè)給定的 n n n，如果確定 ∑ i = 1 n p ( i ) \sum\limits_{i=1}^{n}p(i) i=1∑n?p(i)的結(jié)果。
這里，我們使用的是一個(gè)迭代的結(jié)果，我們將所有數(shù)用二進(jìn)制進(jìn)行表示，考察 n n n的最大一位（不妨設(shè)為第 k k k位），如果這個(gè)位剛好是 x x x的整數(shù)倍且為 1 1 1，那么考察 2 k ? 1 2^{k-1} 2k?1到 n n n的這段區(qū)間，其貢獻(xiàn)的price就是 n ? 2 k ? 1 + 1 n-2^{k-1}+1 n?2k?1+1聯(lián)合上 ∑ i = 2 k ? 1 n p ( i ? 2 2 k ? 1 ) \sum\limits_{i=2^{k-1}}^{n} p(i - 2^{2^{k-1}}) i=2k?1∑n?p(i?22k?1)的部分，以及剩下的 1 1 1到 2 k ? 1 ? 1 2^{k-1}-1 2k?1?1的部分。
同樣的，如果最高位不為 x x x的整倍數(shù)，那么直接忽略掉最高位，結(jié)果就是 ∑ i = 2 k ? 1 n p ( i ? 2 2 k ? 1 ) \sum\limits_{i=2^{k-1}}^{n} p(i - 2^{2^{k-1}}) i=2k?1∑n?p(i?22k?1)的部分與剩下的 1 1 1到 2 k ? 1 ? 1 2^{k-1}-1 2k?1?1的部分之和。
我們將其翻譯為代碼語言即可。
2. 代碼實(shí)現(xiàn)
給出python代碼實(shí)現(xiàn)如下：文章來源：http://www.zghlxwxcb.cn/news/detail-807071.html
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
提交代碼評(píng)測得到：耗時(shí)412ms，占用內(nèi)存26MB。文章來源地址http://www.zghlxwxcb.cn/news/detail-807071.html
到了這里，關(guān)于Leetcode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![java.net.ConnectException: [NACOS HTTP-POST] The maximum number of tolerable server reconnection](https://imgs.yssmx.com/Uploads/2024/02/671925-1.png)
