作者推荐
本文涉及的基础知识点
二分查找算法合集
位运算
LeetCode100160. 价值和小于等于 K 的最大数字
给你一个整数 k 和一个整数 x 。
令 s 为整数 num 的下标从1 开始的二进制表示。我们说一个整数 num 的 价值 是满足 i % x == 0 且 s[i] 是 设置位 的 i 的数目。
请你返回 最大 整数 num ，满足从 1 到 num 的所有整数的 价值 和小于等于 k 。
注意：
一个整数二进制表示下 设置位 是值为 1 的数位。
一个整数的二进制表示下标从右到左编号，比方说如果 s == 11100 ，那么 s[4] == 1 且 s[2] == 0 。
示例 1：
输入：k = 9, x = 1
输出：6
解释：数字 1 ，2 ，3 ，4 ，5 和 6 二进制表示分别为 “1” ，“10” ，“11” ，“100” ，“101” 和 “110” 。
由于 x 等于 1 ，每个数字的价值分别为所有设置位的数目。
这些数字的所有设置位数目总数是 9 ，所以前 6 个数字的价值和为 9 。
所以答案为 6 。
示例 2：
输入：k = 7, x = 2
输出：9
解释：由于 x 等于 2 ，我们检查每个数字的偶数位。
2 和 3 在二进制表示下的第二个数位为设置位，所以它们的价值和为 2 。
6 和 7 在二进制表示下的第二个数位为设置位，所以它们的价值和为 2 。
8 和 9 在二进制表示下的第四个数位为设置位但第二个数位不是设置位，所以它们的价值和为 2 。
数字 1 ，4 和 5 在二进制下偶数位都不是设置位，所以它们的价值和为 0 。
10 在二进制表示下的第二个数位和第四个数位都是设置位，所以它的价值为 2 。
前 9 个数字的价值和为 6 。
前 10 个数字的价值和为 8，超过了 k = 7 ，所以答案为 9 。
提示：
1 <= k <= 1015
1 <= x <= 8
二分查找
随着num的增加，价值和单调增加。这是二分查找的基础。寻找最后一个符合条件的nums，用左闭右开空间。
如何求1到num第i位的价值和。 由于0不包括1，所以本问题等效与0到num的价值和。
| i==0 | 0 1 … | 周期长度2 |
| i==1 | 00 01 10 11… | 周期长度4 |
| i==2 | 000 001 010 011 100 101 110 111… | 周期长度8 |
| … |
周期长度 1<
[0,num]共num+1个数。
- 完整周期数：(num+1)/(1 << i ) 每个周期有半数1
- 不足一个周期的数有iCnt2= (num+1)%(1<
代码
核心代码
这周的LeetCode C++可能有问题，总溢出，所以加了不少判断。
class Solution {
public:
long long findMaximumNumber(long long k, int x) {
long long left = 0, r = 5e17;
while (r - left > 1)
{
const auto mid = left + (r - left) / 2;
if (Cnt(mid, k,x) <= k)
{
left = mid;
}
else
{
r = mid;
}
}
return left;
}
long long Cnt(long long mid,int k,int x )
{
long long llCnt = 0;
for (int ii = x; ii <= 60; ii += x)
{
const long long tmp = 1LL << ii;//周期
const long long cur1 = (mid + 1) / tmp * (tmp / 2);
const long long cur2 = max(0LL, (mid + 1) % tmp - tmp / 2);
if (LLONG_MAX - llCnt < cur1)
{
return k + 1;
}
llCnt += cur1;
if (LLONG_MAX - llCnt < cur2)
{
return k + 1;
}
llCnt += cur2;
}
return llCnt;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
long long k;
int x;
{
Solution sln;
k = 19, x = 6;
auto res = sln.findMaximumNumber(k, x);
Assert(50LL, res);
}
{
Solution sln;
k = 9, x = 1;
auto res = sln.findMaximumNumber(k, x);
Assert(6LL, res);
}
{
Solution sln;
k = 7, x = 2;
auto res = sln.findMaximumNumber(k, x);
Assert(9LL, res);
}
{
Solution sln;
k = 343883588590415, x = 1;
auto res = sln.findMaximumNumber(k, x);
//Assert(9LL, res);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
QQ群名片
评论记录：
回复评论：