2024-05-15:用 go 语言,考虑一个整数 k 和一个整数 x。 对于一个数字 num, 在其二进制表示中, 从最低有效位开始, 我们计算在 x,2x,3x 等位置处设定位的数量来确定其价值。
2024-05-15:用 go 语言,考虑一个整数 k 和一个整数 x。
对于一个数字 num,
在其二进制表示中,
从最低有效位开始,
我们计算在 x,2x,3x 等位置处设定位的数量来确定其价值。
举例说明,
若对于 x=1,num=13,则二进制表示为 000001101,对应的价值为 3。
又如,当 x=2,num=13,二进制表示依然为 000001101,但对应的价值是 1。
另一个例子是当 x=3,num=362,二进制表示为 101101010,价值为 2。
一个数字的累加价值是从 1 到该数字的所有数字的总价值。
如果一个数字的累加价值小于或等于 k,则我们认为它是廉价的。
现在,我们需要找到最大的廉价数字。
输入:k = 9, x = 1。
输出:6。
答案 2024-05-15:
题目来自 leetcode3007。
大体步骤如下:
1.将输入的整数 k 转换为 int 类型,并初始化变量 num 和 pre1 为 0。
2.使用 bits.Len() 函数来计算 (k+1) << x 的二进制表示的位数,将结果减去 1,得到最高有效位的索引 i。
3.从 i 开始遍历到 0,每次循环减少 i 的值。
4.在每次循环中,计算 cnt 的值,cnt = pre1 << i + (i / x) << i >> 1。
5.如果 cnt 大于 k,则跳过当前循环。
6.否则,将 k 减去 cnt,并且通过位运算将 num 的第 i 位设置为 1。
7.如果 (i+1) 是 x 的倍数,则将 pre1 的值加 1。
8.循环结束后,返回 num - 1。
总的时间复杂度:O(log(k+1) * log((k+1)<<x)),其中 log(k+1) 是计算 (k+1) 的二进制表示的位数,log((k+1)<<x) 是计算 (k+1)<<x 的二进制表示的位数。
总的额外空间复杂度:O(1),只使用了常数级别的额外空间。
Go 完整代码如下:
![](https://static001.geekbang.org/infoq/f4/f4e19c22ed95e5de768e5d70e81f48b2.png)
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/873f9c05cef676f97101b81fc】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论