查找第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變更

回答

相關問題