周口建设网站的,豆瓣 wordpress 插件,机关网站建设存在的问题,惠州网站策划建设前言 感谢皇家笨阿宝的指导 题目
给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x#xff0c;2x#xff0c;3x 等位置处设置位的数目#xff08;从最低有效位开始#xff09;。下面的表格包含了如何计算价值的例子。
XnumBinary RepresentationPri…前言 感谢皇家笨阿宝的指导 题目
给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x2x3x 等位置处设置位的数目从最低有效位开始。下面的表格包含了如何计算价值的例子。
XnumBinary RepresentationPrice1130000011013213000001101122330111010013313000001101133621011010102
num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价的。
请你返回 最大 的廉价数字。
示例 1 输入k 9, x 1 输出6 解释由下表所示6 是最大的廉价数字。 XnumBinary RepresentationPriceAccumulated Price11001111201012130112414100151510127161102917111312
示例 2 输入k 7, x 2 输出9 解释由下表所示9 是最大的廉价数字。 XnumBinary RepresentationPriceAccumulated Price210001002200101123001112240100022501010226011013270111142810001529100116210101028
提示
1 k 1015 1 x 8
解题思路
见代码内
代码
class Solution {
public:long long findMaximumNumber(long long k, int x) {//二分查找的过程long long left1,right(k1)x;while(leftright){long long mid(leftright1)/2;if(Sum(x,mid)k){//如果比 k 大 说明答案在mid左边rightmid-1;}else{//如果比 k 小 说明在mid右边leftmid;}}return left;}
//求解从 1 到 num 所有整数在二进制表示下在 i 位置处设置位的数字之和
/*
规律1 2 3 4 5 6
0 0 0 0 0 0 0
1 0 0 0 0 0 1
2 0 0 0 0 1 0
3 0 0 0 0 1 1
4 0 0 0 1 0 0
5 0 0 0 1 0 1
6 0 0 0 1 1 0
7 0 0 0 1 1 1
8 0 0 1 0 0 0
9 0 0 1 0 0 1此处从 0 开始列举由于 0 的贡献值为 0 因此对本题无影响
数学规律第 i 位的 0 1 存在周期性变化对于 i 位置 先是 2^(i-1) 个 0 后是 2^(i-1) 个 1得出周期为 2^(i-1)2^(i-1) 即 2^i*/
//先得到二进制有几位per1LLx
//对于在一个完整周期 T 内的贡献值是 T/2
//对于在一个不完整周期 T 内的贡献值是
// -不超过 T/2 贡献值为 0
// -超过 T/2 则是超过部分个 1 即最后一个不完整周期到 T/2 的距离 long long Sum_per(int x,long long num){long long per1LLx;long long ansper/2*(num/per);if(num%perper/2){ansnum%per-(per/2-1);}return ans;}
//是 num 的累加价值long long Sum(int x,long long num){long long ans0;int l64-__builtin_clzll(num);//求出数的二进制的位数除去前导 0 //位数不可能超过num的最高位//假设位数为x 2x 3x 4x ...nx//则 nx lfor(int ix;il;ix){//搜索在第 i 位的累加之和ansSum_per(i,num);}return ans;}
};
