长沙建设品牌网站,网上长期挣钱的方法,网站外链建设工作总结,wordpress 两栏 主题作者推荐
【动态规划】【字符串】扰乱字符串
本文涉及的基础知识点
二分查找算法合集 位运算
LeetCode100160. 价值和小于等于 K 的最大数字
给你一个整数 k 和一个整数 x 。 令 s 为整数 num 的下标从1 开始的二进制表示。我们说一个整数 num 的 价值 是满足 i % x 0 且…作者推荐
【动态规划】【字符串】扰乱字符串
本文涉及的基础知识点
二分查找算法合集 位运算
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的价值和。
i00 1 …周期长度2i100 01 10 11…周期长度4i2000 001 010 011 100 101 110 111…周期长度8…
周期长度 1i 。前半个周期全部是0后半个周期全部是1。
[0,num]共num1个数。
完整周期数(num1)/(1 i ) 每个周期有半数1不足一个周期的数有iCnt2 (num1)%(1i) 1的数量为iCnt2-- (i i )/2 iCnt如果小于0取0.
代码
核心代码
这周的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;}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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);}
}扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
