(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

用例

输入 2
输出 4
说明

2的二进制10,

4的二进制位100,

1的个数相同,且4是满足条件的最小数

输入 7
输出 11
说明

7的二进制111,

11的二进制位1011,

1的个数相同,且11是满足条件的最小数

题目解析

我们可以举几个例子来说明此题的解法:

n: 10010100

m:10011000


n: 11101001

m:11101010


n: 11100010

m:11100100


可以发现,想要找到符合要求的m,其实只需要将 n 二进制串中从右往左找到的第一组 "01" 子串 变为 "10" 即可。

这样就能在不新增二进制'1'的情况下,且差距最小的情况下,找到比n大的最小的m的二进制串

那么对于:

n = 111111

n = 10000

这种找不到 "01" 子串的情况,该怎么处理呢?

很简单,给n的二进制串最前面拼接一个0即可,即上面两个n的二进制串变为

n = 0111111  => m = 1011111 

n = 010000  => m = 100000

此时前面方法依旧适用。

但是上面方法依旧是存在问题的,什么问题,因为我们将"01"变为"10"的过程中实际上对于该子串后面的部分也会产生影响。

比如

n =  10000111100

如果我们将 01 子串变为 10,则m的二进制串为

m = 10001011100

此时m虽然比n大,但是并不是最小的m,此时由于红色部分发生了进位操作,因此红色部分后面的子串还有变小的可能,比如更优的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] = {''};
    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("%dn", m);

    return 0;
}

免责声明:

1、IT资源小站为非营利性网站,全站所有资料仅供网友个人学习使用,禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享,本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员,一律视为同意网站规定,本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

0

评论0

站点公告

没有账号?注册  忘记密码?