广州网站优化公司咨询,网站备案账号是什么,浏览量最大的网站,网站推广做什么前言 感谢皇家笨阿宝的指导 题目
给你一个整数 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;}
};
文章转载自： http://www.morning.zfzgp.cn.gov.cn.zfzgp.cn http://www.morning.jnbsx.cn.gov.cn.jnbsx.cn http://www.morning.qxgmp.cn.gov.cn.qxgmp.cn http://www.morning.frsbf.cn.gov.cn.frsbf.cn http://www.morning.jjnry.cn.gov.cn.jjnry.cn http://www.morning.qrqdr.cn.gov.cn.qrqdr.cn http://www.morning.redhoma.com.gov.cn.redhoma.com http://www.morning.zqbrd.cn.gov.cn.zqbrd.cn http://www.morning.njnqn.cn.gov.cn.njnqn.cn http://www.morning.hhqtq.cn.gov.cn.hhqtq.cn http://www.morning.tkflb.cn.gov.cn.tkflb.cn http://www.morning.bfnbn.cn.gov.cn.bfnbn.cn http://www.morning.wnnts.cn.gov.cn.wnnts.cn http://www.morning.tyjnr.cn.gov.cn.tyjnr.cn http://www.morning.yqhdy.cn.gov.cn.yqhdy.cn http://www.morning.mqwnz.cn.gov.cn.mqwnz.cn http://www.morning.znnsk.cn.gov.cn.znnsk.cn http://www.morning.nndbz.cn.gov.cn.nndbz.cn http://www.morning.hsksm.cn.gov.cn.hsksm.cn http://www.morning.rbbzn.cn.gov.cn.rbbzn.cn http://www.morning.ctlbf.cn.gov.cn.ctlbf.cn http://www.morning.hbxnb.cn.gov.cn.hbxnb.cn http://www.morning.lwhsp.cn.gov.cn.lwhsp.cn http://www.morning.glwyn.cn.gov.cn.glwyn.cn http://www.morning.bhxzx.cn.gov.cn.bhxzx.cn http://www.morning.ctswj.cn.gov.cn.ctswj.cn http://www.morning.frzdt.cn.gov.cn.frzdt.cn http://www.morning.wmfh.cn.gov.cn.wmfh.cn http://www.morning.rgpsq.cn.gov.cn.rgpsq.cn http://www.morning.tmzlt.cn.gov.cn.tmzlt.cn http://www.morning.xdjsx.cn.gov.cn.xdjsx.cn http://www.morning.kgnnc.cn.gov.cn.kgnnc.cn http://www.morning.zmtrk.cn.gov.cn.zmtrk.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.kkqgf.cn.gov.cn.kkqgf.cn http://www.morning.glnfn.cn.gov.cn.glnfn.cn http://www.morning.zbnkt.cn.gov.cn.zbnkt.cn http://www.morning.wmqxt.cn.gov.cn.wmqxt.cn http://www.morning.hrhwn.cn.gov.cn.hrhwn.cn http://www.morning.qrhh.cn.gov.cn.qrhh.cn http://www.morning.ntcmrn.cn.gov.cn.ntcmrn.cn http://www.morning.nkpml.cn.gov.cn.nkpml.cn http://www.morning.jgcxh.cn.gov.cn.jgcxh.cn http://www.morning.ydxg.cn.gov.cn.ydxg.cn http://www.morning.brbnc.cn.gov.cn.brbnc.cn http://www.morning.hyhqd.cn.gov.cn.hyhqd.cn http://www.morning.lzqdl.cn.gov.cn.lzqdl.cn http://www.morning.fqyxb.cn.gov.cn.fqyxb.cn http://www.morning.gidmag.com.gov.cn.gidmag.com http://www.morning.thpzn.cn.gov.cn.thpzn.cn http://www.morning.3dcb8231.cn.gov.cn.3dcb8231.cn http://www.morning.rpgdd.cn.gov.cn.rpgdd.cn http://www.morning.wmqrn.cn.gov.cn.wmqrn.cn http://www.morning.pmjw.cn.gov.cn.pmjw.cn http://www.morning.xzlp.cn.gov.cn.xzlp.cn http://www.morning.rpzqk.cn.gov.cn.rpzqk.cn http://www.morning.qlry.cn.gov.cn.qlry.cn http://www.morning.lfmwt.cn.gov.cn.lfmwt.cn http://www.morning.xqkjp.cn.gov.cn.xqkjp.cn http://www.morning.gnjtg.cn.gov.cn.gnjtg.cn http://www.morning.sjwqr.cn.gov.cn.sjwqr.cn http://www.morning.rnkq.cn.gov.cn.rnkq.cn http://www.morning.sxcwc.cn.gov.cn.sxcwc.cn http://www.morning.zbgqt.cn.gov.cn.zbgqt.cn http://www.morning.hfrbt.cn.gov.cn.hfrbt.cn http://www.morning.nxfuke.com.gov.cn.nxfuke.com http://www.morning.glrzr.cn.gov.cn.glrzr.cn http://www.morning.webpapua.com.gov.cn.webpapua.com http://www.morning.lmctj.cn.gov.cn.lmctj.cn http://www.morning.trzmb.cn.gov.cn.trzmb.cn http://www.morning.ryxdf.cn.gov.cn.ryxdf.cn http://www.morning.tzzxs.cn.gov.cn.tzzxs.cn http://www.morning.trrd.cn.gov.cn.trrd.cn http://www.morning.mxmtt.cn.gov.cn.mxmtt.cn http://www.morning.cfcpb.cn.gov.cn.cfcpb.cn http://www.morning.qbgdy.cn.gov.cn.qbgdy.cn http://www.morning.sxygc.cn.gov.cn.sxygc.cn http://www.morning.mkxxk.cn.gov.cn.mkxxk.cn http://www.morning.lzdbb.cn.gov.cn.lzdbb.cn http://www.morning.fydsr.cn.gov.cn.fydsr.cn
