查找第K位数n变更

有一个变化规律是，0后 - > 01，1 - > 10。例如，在改变之后，10是1001查找第K位数n变更

假定输入为0，后n这种规则的变化，什么是K数字？

我只能拿出残酷的解决方案，如下所示。但是我相信有更好的解决方案，任何人都可以提出一些新的想法吗？

public char lalala(int n, int k) { 
    String str = "0"; 
    for (int i = 0; i < n; i++) { 
     StringBuilder sb = new StringBuilder(); 
     for (int j = 0; j < str.length; j++) { 
      if (str.charAt(j) == '0') { 
       sb.append("01"); 
      } else { 
       sb.append("10"); 
      } 
     } 
     str = sb.toString(); 
    } 
    return str.charAt(k); 
}

来源

2014-09-20 laviier

你在执行什么规则？ – 2014-09-20 00:31:11

对不起，忘了添加它。有一个变化的规则，0 - > 01,1 - > 10。例如，更改后，10是1001. – laviier 2014-09-20 00:37:44

您的程序不正确：（1）程序中第k个数字是（k-1） -th。（2）使用StringBuilder在你的方式追加字符是不正确的，使用替换。 – 2014-09-20 00:49:41

所以您生成的字符串看起来像

0110100110010110....

现在，让我们写垂直这个数字和支持，让每一位

value|position -> position binary 
-----+--------------------------- 
0 | 0  -> 0000 
1 | 1  -> 0001 
1 | 2  -> 0010 
0 | 3  -> 0011 
1 | 4  -> 0100 
0 | 5  -> 0101 
0 | 6  -> 0110 
1 | 7  -> 0111 
.  .   .... 
.  .   ....

的位置打印二进制表示如果你把你仔细看看将会看到：

如果在position二进制表示1数量是偶数value是0
如果1在position二进制表示数量为奇数value是1

这意味着

0001，0010，0100 ，0111包含奇数1值 wil我是1。

换句话说value等于number of ones模2的。

使用这个事实，你可以创建代码将你的n转换为表示它的二进制形式的字符串，总和所有1，并检查它是奇数还是偶数。

代码转换n到value可以这个样子

public static int value(int n) { 
    String binary = Integer.toBinaryString(n); 
    return binary.chars().map(e -> e == '1' ? 1 : 0).sum() % 2; 
}

（长一点的版本，如果你不熟悉的Java 8中引入的流）

public static int value(Integer n) { 
    String binary = Integer.toBinaryString(n); 
    int count = 0; 
    for (char ch : binary.toCharArray()) 
     if (ch == '1') count ++; 
    return count % 2; 
}

，当你使用它像

for (int i = 0; i < 20; i++) 
    System.out.print(value(i));

你会得到输出01101001100101101001这似乎是正确的。

来源

2014-09-20 01:25:57 Pshemo

查找第K位数n变更

回答

相关问题