时间戳

首页 > 解决方案 > 找到没有连续 1 的最小二进制数

java - 找到没有连续 1 的最小二进制数

问题描述

所以这就是事情。我必须编写代码来显示二进制数 X 的下一个最小“code-X 数”，它大于二进制数 X。code-X 数是一个没有连续 1 的二进制数。例如：1100 不是代码 X数字，因为它有 11，而 1001001001 是代码-X 数字这是我的代码

String a = "11001110101010";
    String b = "";
    int d = 0;
    for(int i = a.length()-1; i>0;i--){
        if(a.charAt(i) == '1' && a.charAt(i-1)=='1'){
        while(a.charAt(i)=='1'){
            b = b + '0';
            if(i!=0){i--;}
            d++;
        }
        }
        b = b + a.charAt(i);
    }
    StringBuffer c = new StringBuffer(b);
    System.out.println(c.reverse());

我计划将二进制字符串复制到字符串 b，将下一个 i 为 '1' 的每个 '1' 替换为 '0' 并插入一个 '1'，例如：1100 ---> 10000 但我不知道该怎么做:) 你能帮我一些吗？谢谢

标签： java

解决方案

尝试这个。这处理任意长度的位串。算法如下。

  • 如果数字不是 codeEx 数字，则需要有条件地修改最后两位以强制更改。这确保它会更高。感谢John Mitchell的观察。
  • 从左边开始，找到第一组 1。例如 0110
  • 如果不是在开始时将其替换为 100 以获得 1000
  • 否则，在开头插入 1。
  • 在所有情况下，将分组右侧的所有内容替换为 0。
String x = "10000101000000000001000001000000001111000000000000110000000000011011";

System.out.println(x.length());
String result = codeX(x);

System.out.println(x);
System.out.println(result);


public static String codeX(String bitStr) {
    StringBuilder sb = new StringBuilder(bitStr);
    int i = 0;

   
    int len = sb.length();
    // Make adjust to ensure new number is larger than
    // original.  If the word ends in 00 or 10, then adding one will
    // increase the value in all cases.  If it ends in 01
    // then replacing with 10 will do the same.  Once done
    // the algorithm takes over to find the next CodeX number.
    if (s.equals("01")) {
        sb.replace(len - 2, len, "10");
    } else {
        sb.replace(len- 1, len, "1");
    }
    while ((i = sb.indexOf("11")) >= 0) {
        sb.replace(i, len, "0".repeat(len - i));
        if (i != 0) {
            sb.replace(i - 1, i + 2, "100");
        } else {
            sb.insert(i, "1");
        }
    }
    String str = sb.toString();
    i = str.indexOf("1");
    return i >= 0 ? str.substring(i) : str;
}

印刷

10000101000000000001000001000000001111000000000000110000000000011011
10000101000000000001000001000000010000000000000000000000000000000000

推荐阅读