小扇和小船的数字游戏 - 华为OD统一考试（C卷）
OD统一考试（C卷）
分值： 200分
题解： Java / Python / C++
题目描述
小扇和小船今天又玩起来了数字游戏，
小船给小扇一个正整数 n（1 ≤ n ≤ 1e9），小扇需要找到一个比 n 大的数字 m，使得 m 和 n 对应的二进制中 1 的个数要相同，如：
4对应二进制100
8对应二进制1000
其中1的个数都为1个
现在求 m 的最小值。
输入描述
输入一个正整数 n（1 ≤ n ≤ 1e9）
输出描述
输出一个正整数 m
示例1
输入：
2
输出：
4
说明：
2的二进制10，
4的二进制位100，
1的个数相同，且4是满足条件的最小数
示例2
输入：
7
输出：
11
说明：
7的二进制111，
11的二进制位1011，
1的个数相同，且11是满足条件的最小数
题解
题解分析
这道题目要求找到一个比给定的正整数 n 大的数字 m，使得它们的二进制表示中 1 的个数相同。本质上，题目要求在二进制表示中，找到一个比 n 大的具有相同数量的 1 的数。
给出的解法是使用贪心算法。首先，将 n 转换为二进制表示，然后通过贪心地找到可以将某个 0 变成 1 的位置，使得数字变大，同时保持 1 的个数不变。最后输出这个结果。
解题思路
- 将给定的十进制数 n 转换为二进制表示，并在末尾添加一个 0。
- 使用贪心算法找到可以将某个 0 变成 1 的位置的索引 idx。
- 调整 idx 位 0 变成 1，同时调整 idx 前的位，使得低位为 1，高位为 0，且二进制中 1 的个数不变。
- 输出调整后的结果。
Java
import java.util.Scanner;
import java.util.ArrayList;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(solve(n));
}
// 解决问题的函数
public static int solve(int n) {
ArrayList<Integer> bs = new ArrayList<>();
// 转换为二进制
while (n > 0) {
bs.add(n % 2);
n /= 2;
}
// 在列表末尾添加一个 0，以便处理
bs.add(0);
// 贪心的寻找可以将 0 变成 1 的地方的索引 idx（使得数字变大）
// idx 满足低位存在 1 且 bs.get(idx) == 0
int idx = 0, oneCnt = 0;
for (; idx < bs.size(); idx++) {
if (oneCnt > 0 && bs.get(idx) == 0) {
break;
}
oneCnt += bs.get(idx);
}
// 将 idx 位 0 变成 1，同时 idx 前的位也相应调整
// 调整规则：低位 1，高位 0，且二进制中 1 的个数不变
for (int i = 0; i < idx; i++) {
bs.set(i, (i < oneCnt - 1) ? 1 : 0);
}
// idx 位 0 变成 1，后面的位全部保持不变
bs.set(idx, 1);
// 计算最终结果
int result = 0, base = 1;
for (int i = 0; i < bs.size(); i++) {
result += bs.get(i) * base;
base *= 2;
}
return result;
}
}
Python
def solve(n):
bs = []
# 转换为二进制
while n > 0:
bs.append(n % 2)
n //= 2
# 在列表末尾添加一个 0，以便处理
bs.append(0)
# 贪心的寻找可以将 0 变成 1 的地方的索引 idx（使得数字变大）
# idx 满足低位存在 1 且 bs[idx] == 0
idx, one_cnt = 0, 0
while idx < len(bs):
if one_cnt > 0 and bs[idx] == 0:
break
one_cnt += bs[idx]
idx += 1
# 将 idx 位 0 变成 1，同时 idx 前的位也相应调整
# 调整规则：低位 1，高位 0，且二进制中 1 的个数不变
for i in range(idx):
bs[i] = 1 if i < one_cnt - 1 else 0
# idx 位 0 变成 1，后面的位全部保持不变
bs[idx] = 1
# 计算最终结果
result, base = 0, 1
for bit in bs:
result += bit * base
base *= 2
return result
if __name__ == "__main__":
n = int(input())
print(solve(n))
C++
#include <iostream>
#include <vector>
using namespace std;
int solve(int n) {
vector<int> bs;
// 转换为二进制
while (n > 0) {
bs.push_back(n % 2);
n /= 2;
}
// 在数组末尾添加一个 0，以便处理
bs.push_back(0);
// 贪心的寻找可以 0 变成 1 的地方 idx (使得数字变大)
// idx 满足低位存在 1 且 bs[idx] == 0
int idx = 0, oneCnt = 0;
for (; idx < bs.size(); idx++) {
if (oneCnt > 0 && bs[idx] == 0) break;
oneCnt += bs[idx];
}
// 将 idx 位 0 变成 1，同时 idx 前的位也相应调整
// 调整规则： 低位 1 ，高位 0， 且 二进制中 1 的个数不变
for (int i = 0; i < idx; i++) {
bs[i] = (i < oneCnt - 1) ? 1 : 0;
}
// idx 位 0 变成 1 ，后面的位全部保持不变
bs[idx] = 1;
int result = 0, base = 1;
for (int bit : bs) {
result += bit * base;
base *= 2;
}
return result;
}
int main() {
int n;
cin >> n;
cout << solve(n) << endl;
return 0;
}
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
#面经##校招##春招##华为##面试#
