searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

2024-05-15:用go语言,考虑一个整数 k 和一个整数 x

2024-05-15 07:56:17
1
0
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完整代码如下:
 
```go
package main
 
import (
"fmt"
"math/bits"
)
 
func findMaximumNumber(K int64, x int) int64 {
k := int(K)
num, pre1 := 0, 0
for i := bits.Len(uint((k+1)<<x)) - 1; i >= 0; i-- {
cnt := pre1<<i + i/x<<i>>1
if cnt > k {
continue
}
k -= cnt
num |= 1 << i
if (i+1)%x == 0 {
pre1++
}
}
return int64(num - 1)
}
 
func main() {
k := int64(9)
x := 1
result := findMaximumNumber(k, x)
fmt.Println(result)
}
```
 

 

0条评论
0 / 1000
3****m
116文章数
2粉丝数
3****m
116 文章 | 2 粉丝
原创

2024-05-15:用go语言,考虑一个整数 k 和一个整数 x

2024-05-15 07:56:17
1
0
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完整代码如下:
 
```go
package main
 
import (
"fmt"
"math/bits"
)
 
func findMaximumNumber(K int64, x int) int64 {
k := int(K)
num, pre1 := 0, 0
for i := bits.Len(uint((k+1)<<x)) - 1; i >= 0; i-- {
cnt := pre1<<i + i/x<<i>>1
if cnt > k {
continue
}
k -= cnt
num |= 1 << i
if (i+1)%x == 0 {
pre1++
}
}
return int64(num - 1)
}
 
func main() {
k := int64(9)
x := 1
result := findMaximumNumber(k, x)
fmt.Println(result)
}
```
 

 

文章来自个人专栏
福大大架构师每日一题
116 文章 | 1 订阅
0条评论
0 / 1000
请输入你的评论
0
0