首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >2025-06-18:仅含置位位的最小整数。用go语言,给定一个正整数 n,求一个不小于 n 的最小整数 x,且该整数的二进制表

2025-06-18:仅含置位位的最小整数。用go语言,给定一个正整数 n,求一个不小于 n 的最小整数 x,且该整数的二进制表

作者头像
福大大架构师每日一题
发布于 2025-06-19 01:38:17
发布于 2025-06-19 01:38:17
7700
代码可运行
举报
运行总次数:0
代码可运行

2025-06-18:仅含置位位的最小整数。用go语言,给定一个正整数 n,求一个不小于 n 的最小整数 x,且该整数的二进制表示中,1 的个数与给定的“置位”数量相同。换句话说,x 的二进制中有指定数量的位是 1,且 x ≥ n,找到满足条件的最小的这样的 x。

1 <= n <= 1000。

输入: n = 5。

输出: 7。

解释:

7 的二进制表示是 "111"。

题目来自力扣3370。

解决步骤(假设题目是求最小的全 1≥ n

  1. 1. 计算 n 的二进制位数:
    • • 使用 bits.Len(uint(n)) 得到 n 的二进制表示的长度(即最高有效位的位数)。
    • • 例如,n = 5101),bits.Len(5) 返回 3
  2. 2. 构造全 1 的数:
    • • 全 1 的数的二进制表示是 k1,其值为 2^k - 1
    • • 例如,k = 32^3 - 1 = 7111)。
  3. 3. 检查是否满足 ≥ n
    • • 如果 2^k - 1 ≥ n,则直接返回 2^k - 1
    • • 否则,需要增加位数 k 并重新构造全 1 的数。
    • • 例如,n = 8
      • bits.Len(8) 返回 481000)。
      • 2^4 - 1 = 151111),15 ≥ 8,返回 15
    • • 例如,n = 5
      • bits.Len(5) 返回 3
      • 2^3 - 1 = 77 ≥ 5,返回 7

时间复杂度和空间复杂度

  • • 时间复杂度:
    • bits.Len(uint(n)) 的时间复杂度是 O(1)(通常是通过硬件指令或快速位操作实现)。
    • • 构造 1 << k - 1 也是 O(1)
    • • 因此,总时间复杂度是 O(1)
  • • 空间复杂度:
    • • 只使用了常数级别的额外空间(几个变量)。
    • • 因此,总空间复杂度是 O(1)

总结

  • • 题目可能是求“不小于 n 的最小全 1 数”。
  • • 代码通过 bits.Len 找到 n 的二进制位数 k,然后返回 (1 << k) - 1
  • • 时间复杂度和空间复杂度均为 O(1)

Go完整代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
package main

import (
    "fmt"
    "math/bits"
)

func smallestNumber(n int)int {
    return1<<bits.Len(uint(n)) - 1
}

func main() {
    n := 5
    fmt.Println(smallestNumber(n))
}

Python完整代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
# -*-coding:utf-8-*-

def smallest_number(n: int) -> int:
    # bits_len = n的二进制长度
    bits_len = n.bit_length()
    return (1 << bits_len) - 1

if __name__ == "__main__":
    n = 5
    print(smallest_number(n))

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2025-06-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
LeetCode 图解 | 191.位 1 的个数
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
五分钟学算法
2020/02/20
5520
2025-06-05:统计小于 N 的 K 可约简整数。用go语言,给定一个二进制字符串 s,它表示一个整数 n 的二进制形式。
2025-06-05:统计小于 N 的 K 可约简整数。用go语言,给定一个二进制字符串 s,它表示一个整数 n 的二进制形式。
福大大架构师每日一题
2025/06/06
500
2025-06-05:统计小于 N 的 K 可约简整数。用go语言,给定一个二进制字符串 s,它表示一个整数 n 的二进制形式。
2025-05-05:连接二进制表示可形成的最大数值。用go语言,给定一个包含三个整数的数组 nums。 将数组中所有元素的二进
2025-05-05:连接二进制表示可形成的最大数值。用go语言,给定一个包含三个整数的数组 nums。
福大大架构师每日一题
2025/05/05
900
2025-05-05:连接二进制表示可形成的最大数值。用go语言,给定一个包含三个整数的数组 nums。 将数组中所有元素的二进
2024-05-15:用go语言,考虑一个整数 k 和一个整数 x。 对于一个数字 num, 在其二进制表示中, 从最低有效位开
又如,当x=2,num=13,二进制表示依然为000001101,但对应的价值是1。
福大大架构师每日一题
2024/05/17
1370
2024-05-15:用go语言,考虑一个整数 k 和一个整数 x。 对于一个数字 num, 在其二进制表示中, 从最低有效位开
2025-05-02:找出第 K 个字符Ⅰ。用go语言,Alice 和 Bob 玩一个游戏。起初,Alice 有一个字符串,内容
2025-05-02:找出第 K 个字符Ⅰ。用go语言,Alice 和 Bob 玩一个游戏。起初,Alice 有一个字符串,内容是 "a"。
福大大架构师每日一题
2025/05/02
690
2025-05-02:找出第 K 个字符Ⅰ。用go语言,Alice 和 Bob 玩一个游戏。起初,Alice 有一个字符串,内容
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整数 k。
福大大架构师每日一题
2025/07/08
560
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整
2025-03-08:使两个整数相等的位更改次数。用go语言,给定两个正整数 n 和 k。 你可以从 n 的二进制表示中选择任意
2025-03-08:使两个整数相等的位更改次数。用go语言,给定两个正整数 n 和 k。
福大大架构师每日一题
2025/03/10
910
2025-03-08:使两个整数相等的位更改次数。用go语言,给定两个正整数 n 和 k。 你可以从 n 的二进制表示中选择任意
2025-05-31:最小可整除数位乘积Ⅰ。用go语言,给定两个整数 n 和 t,要求找出不小于 n 的最小整数,使得这个整数各
2025-05-31:最小可整除数位乘积Ⅰ。用go语言,给定两个整数 n 和 t,要求找出不小于 n 的最小整数,使得这个整数各位数字的乘积能够被 t 整除。
福大大架构师每日一题
2025/06/06
740
2025-05-31:最小可整除数位乘积Ⅰ。用go语言,给定两个整数 n 和 t,要求找出不小于 n 的最小整数,使得这个整数各
2022-01-30:最小好进制。
对于给定的整数 n, 如果n的k(k>=2)进制数的所有数位全为1,则称 k(k>=2)是 n 的一个好进制。
福大大架构师每日一题
2022/03/04
3360
2022-01-30:最小好进制。
LeetCode 762. 二进制表示中质数个计算置位
给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个数。
Michael阿明
2020/07/13
4540
LeetCode 762. 二进制表示中质数个计算置位
☆打卡算法☆LeetCode 191. 位1的个数 算法解析
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为汉明重量)。
恬静的小魔龙
2022/09/21
2400
☆打卡算法☆LeetCode 191. 位1的个数 算法解析
Leetcode No.190 颠倒二进制位
示例 1: 输入: 00000010100101000001111010011100 输出: 00111001011110000010100101000000 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596, 因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。
week
2021/05/06
3500
LeetCode-191.位1的个数(java)
        刚刷到这道题的时候,我在想,这一看又是一道二进制题,该不会也跟上一期190.颠倒二进制法一道题型吧?我抱着怀疑的慢慢读题看示例,果不其然,还真是,只不过这道题是要你进行 为'1' 的进行个数统计。很简单吧?
bug菌
2023/05/27
2020
LeetCode-191.位1的个数(java)
(Leetcode 2021 刷题计划) 190. 颠倒二进制位
解题思路: 针对该题, 第一个思路是将其转化为字符串(to_string), 然后直接反转(reverse), 一顿操作结果发现思路不对, 直接采用这种模拟的方法通关。
windism
2021/03/29
4710
2024-12-01:单面值组合的第 K 小金额。用go语言,给定一个整数数组 coins,表示不同面值的硬币,同时给出一个整数
2024-12-01:单面值组合的第 K 小金额。用go语言,给定一个整数数组 coins,表示不同面值的硬币,同时给出一个整数 k。你可以使用任意数量的这些硬币,但不能将不同面值的硬币组合在一起。请返回可以用这些硬币构成的第 k 个最小金额。
福大大架构师每日一题
2024/12/03
1440
2024-12-01:单面值组合的第 K 小金额。用go语言,给定一个整数数组 coins,表示不同面值的硬币,同时给出一个整数
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。 定义:如果一个整数
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。
福大大架构师每日一题
2025/06/06
550
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。 定义:如果一个整数
LeetCode 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
题目地址 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数) https://leetcode-cn.com/problems/w3tCBm/ 题目描述 给定一个非负整数 n ,请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组。   示例 1: 输入: n = 2 输出: [0,1,1] 解释: 0 --> 0 1 --> 1 2 --> 10 示例 2: 输入: n = 5 输出: [0,1,1,2,1,2]
freesan44
2021/09/18
3500
LeetCode 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
☆打卡算法☆LeetCode 190. 颠倒二进制位 算法解析
可以将这个二进制位看成一个二进制串,然后从低位到高位进行遍历枚举,然后将其倒序的插入到int数据对象中。
恬静的小魔龙
2022/09/21
2260
☆打卡算法☆LeetCode 190. 颠倒二进制位 算法解析
2022-01-30:最小好进制。 对于给定的整数 n, 如果n的k(k
对于给定的整数 n, 如果n的k(k>=2)进制数的所有数位全为1,则称 k(k>=2)是 n 的一个好进制。
福大大架构师每日一题
2022/01/30
2150
2025-03-27:统计满足 K 约束的子字符串数量Ⅰ。用go语言,给定一个二进制字符串 s 和一个整数 k,定义满足 k 约
2025-03-27:统计满足 K 约束的子字符串数量Ⅰ。用go语言,给定一个二进制字符串 s 和一个整数 k,定义满足 k 约束的条件为:
福大大架构师每日一题
2025/03/27
630
2025-03-27:统计满足 K 约束的子字符串数量Ⅰ。用go语言,给定一个二进制字符串 s 和一个整数 k,定义满足 k 约
推荐阅读
LeetCode 图解 | 191.位 1 的个数
5520
2025-06-05:统计小于 N 的 K 可约简整数。用go语言,给定一个二进制字符串 s,它表示一个整数 n 的二进制形式。
500
2025-05-05:连接二进制表示可形成的最大数值。用go语言,给定一个包含三个整数的数组 nums。 将数组中所有元素的二进
900
2024-05-15:用go语言,考虑一个整数 k 和一个整数 x。 对于一个数字 num, 在其二进制表示中, 从最低有效位开
1370
2025-05-02:找出第 K 个字符Ⅰ。用go语言,Alice 和 Bob 玩一个游戏。起初,Alice 有一个字符串,内容
690
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整
560
2025-03-08:使两个整数相等的位更改次数。用go语言,给定两个正整数 n 和 k。 你可以从 n 的二进制表示中选择任意
910
2025-05-31:最小可整除数位乘积Ⅰ。用go语言,给定两个整数 n 和 t,要求找出不小于 n 的最小整数,使得这个整数各
740
2022-01-30:最小好进制。
3360
LeetCode 762. 二进制表示中质数个计算置位
4540
☆打卡算法☆LeetCode 191. 位1的个数 算法解析
2400
Leetcode No.190 颠倒二进制位
3500
LeetCode-191.位1的个数(java)
2020
(Leetcode 2021 刷题计划) 190. 颠倒二进制位
4710
2024-12-01:单面值组合的第 K 小金额。用go语言,给定一个整数数组 coins,表示不同面值的硬币,同时给出一个整数
1440
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。 定义:如果一个整数
550
LeetCode 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
3500
☆打卡算法☆LeetCode 190. 颠倒二进制位 算法解析
2260
2022-01-30:最小好进制。 对于给定的整数 n, 如果n的k(k
2150
2025-03-27:统计满足 K 约束的子字符串数量Ⅰ。用go语言,给定一个二进制字符串 s 和一个整数 k,定义满足 k 约
630
相关推荐
LeetCode 图解 | 191.位 1 的个数
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档