首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

2024-05-15:用go语言,考虑一个整数 k 和一个整数 x。 对于一个数字 num, 在其二进制表示中, 从最低有效位开

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:

chatgpt

题目来自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完整代码如下:

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)

}

在这里插入图片描述

  • 发表于:
  • 原文链接https://page.om.qq.com/page/ODaQU0MoN7MDqEjJj6VXw3VQ0
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

相关快讯

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券