(200分)- 找数字（Java JS Python C）

(200分)- 找数字（Java & JS & Python & C）

题目描述

小扇和小船今天又玩起来了数字游戏，

小船给小扇一个正整数 n（1 ≤ n ≤ 1e9），小扇需要找到一个比 n 大的数字 m，使得 m 和 n 对应的二进制中 1 的个数要相同，如：

4对应二进制100

8对应二进制1000

其中1的个数都为1个

现在求 m 的最小值。

输入描述

输入一个正整数 n（1 ≤ n ≤ 1e9）

输出描述

输出一个正整数 m

用例

题目解析

我们可以通过以下例子来说明解题方法：

示例1： n：10010100 → m：10011000

示例2： n：11101001 → m：11101010

示例3： n：11100010 → m：11100100

从这些例子可以看出，要找到满足条件的m，只需将n的二进制串中从右往左找到的第一个"01"子串替换为"10"即可。这种方法能在不增加'1'数量的前提下，找到比n大的最小m。

特殊情况处理： 当n的二进制形式为全1或类似111111、10000时，直接在最高位前补0： n = 0111111 → m = 1011111 n = 010000 → m = 100000

需要注意的优化点： 直接替换"01"为"10"可能会影响后续位的值。例如： n = 10000111100 → 简单替换后： m = 10001011100 此时m并非最优解，因为进位会影响后续位。更优的解法应该是： m = 10001000111 即在完成替换后，将进位影响位后面的所有'1'移至最低位。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; // 输入输出处理 void (async function () { // 将整数n转为二进制字符串 const nBinStr = "0" + Number(await readline()).toString(2); const mBinCharArr = [...nBinStr]; let countOne = 0; for (let i = mBinCharArr.length - 2; i >= 0; i--) { if (mBinCharArr[i] == "0" && mBinCharArr[i + 1] == "1") { // 从右向左找到了第一组"01"子串，则替换为"10" mBinCharArr[i] = "1"; mBinCharArr[i + 1] = "0"; // 如果第一组"01"子串右边存在1 if (countOne > 0) { // 则将第一组"01"子串的右边部分的'1'要全部集中到尾部 for (let j = i + 2; j < mBinCharArr.length; j++) { if (j < mBinCharArr.length - countOne) { mBinCharArr[j] = "0"; } else { mBinCharArr[j] = "1"; } } } break; } if (mBinCharArr[i + 1] == "1") countOne++; // 记录第一组"01"子串右边1的个数 } console.log(parseInt(mBinCharArr.join(""), 2)); })();

Java算法源码

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 将整数n转为二进制字符串 String nBinStr = "0" + Integer.toBinaryString(n); char[] mBinCharArr = nBinStr.toCharArray(); int countOne = 0; for (int i = mBinCharArr.length - 2; i >= 0; i--) { if (mBinCharArr[i] == '0' && mBinCharArr[i + 1] == '1') { // 从右向左找到了第一组"01"子串，则替换为"10" mBinCharArr[i] = '1'; mBinCharArr[i + 1] = '0'; // 如果第一组"01"子串右边存在1 if (countOne > 0) { // 则将第一组"01"子串的右边部分的'1'要全部集中到尾部 for (int j = i + 2; j < mBinCharArr.length; j++) { if (j < mBinCharArr.length - countOne) { mBinCharArr[j] = '0'; } else { mBinCharArr[j] = '1'; } } } break; } if (mBinCharArr[i + 1] == '1') countOne++; // 记录第一组"01"子串右边1的个数 } int m = Integer.parseInt(new String(mBinCharArr), 2); System.out.println(m); } }

Python算法源码

# 输入获取 nBinStr = bin(int(input())) mBinCharArr = list("0" + nBinStr[2:]) countOne = 0 for i in range(len(mBinCharArr) - 2, -1, -1): # 从右向左找到了第一组"01"子串，则替换为"10" if mBinCharArr[i] == '0' and mBinCharArr[i+1] == '1': mBinCharArr[i] = '1' mBinCharArr[i+1] = '0' # 如果第一组"01"子串右边存在1 if countOne > 0: # 则将第一组"01"子串的右边部分的'1'要全部集中到尾部 for j in range(i+2, len(mBinCharArr)): if j < len(mBinCharArr) - countOne: mBinCharArr[j] = '0' else: mBinCharArr[j] = '1' break # 记录第一组"01"子串右边1的个数 if mBinCharArr[i+1] == '1': countOne += 1 m = int("".join(mBinCharArr), 2) print(m)

C算法源码

#include <stdio.h> #include <string.h> #include <stdlib.h> void dec2bin(int num, char *s) { int i = 0; while (num > 0) { s[i++] = (char) (num % 2 + '0'); num /= 2; } // strrev(s); // 该函数只能在windows系统使用，OJ一般搭建在Linux系统上，因此无法使用该函数 int l = 0; int r = i - 1; while (l < r) { char tmp = s[l]; s[l] = s[r]; s[r] = tmp; l++; r--; } } int main() { int n; scanf("%d", &n); char nBinStr[1000] = {'\0'}; nBinStr[0] = '0'; dec2bin(n, nBinStr + 1); int len = (int) strlen(nBinStr); int countOne = 0; for (int i = len - 2; i >= 0; i--) { if (nBinStr[i] == '0' && nBinStr[i + 1] == '1') { // 从右向左找到了第一组"01"子串，则替换为"10" nBinStr[i] = '1'; nBinStr[i + 1] = '0'; // 如果第一组"01"子串右边存在1 if (countOne > 0) { // 则将第一组"01"子串的右边部分的'1'要全部集中到尾部 for (int j = i + 2; j < len; j++) { if (j < len - countOne) { nBinStr[j] = '0'; } else { nBinStr[j] = '1'; } } } break; } // 记录第一组"01"子串右边1的个数 if (nBinStr[i + 1] == '1') { countOne++; } } char *endptr; int m = strtol(nBinStr, &endptr, 2); printf("%d\n", m); return 0; }