Skip to content

Latest commit

 

History

History
156 lines (109 loc) · 3.04 KB

File metadata and controls

156 lines (109 loc) · 3.04 KB
comments difficulty edit_url rating source tags
true
简单
1198
第 426 场周赛 Q1
位运算
数学

English Version

题目描述

给你一个正整数 n

返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。

置位 位指的是二进制表示中值为 1 的位。

 

示例 1:

输入: n = 5

输出: 7

解释:

7 的二进制表示是 "111"

示例 2:

输入: n = 10

输出: 15

解释:

15 的二进制表示是 "1111"

示例 3:

输入: n = 3

输出: 3

解释:

3 的二进制表示是 "11"

 

提示:

  • 1 <= n <= 1000

解法

方法一:位运算

我们从 $x = 1$ 开始,不断将 $x$ 左移,直到 $x - 1 \geq n$,此时 $x - 1$ 就是我们要找的答案。

时间复杂度 $O(\log n)$,空间复杂度 $O(1)$

Python3

class Solution:
    def smallestNumber(self, n: int) -> int:
        x = 1
        while x - 1 < n:
            x <<= 1
        return x - 1

Java

class Solution {
    public int smallestNumber(int n) {
        int x = 1;
        while (x - 1 < n) {
            x <<= 1;
        }
        return x - 1;
    }
}

C++

class Solution {
public:
    int smallestNumber(int n) {
        int x = 1;
        while (x - 1 < n) {
            x <<= 1;
        }
        return x - 1;
    }
};

Go

func smallestNumber(n int) int {
	x := 1
	for x-1 < n {
		x <<= 1
	}
	return x - 1
}

TypeScript

function smallestNumber(n: number): number {
    let x = 1;
    while (x - 1 < n) {
        x <<= 1;
    }
    return x - 1;
}