関小君刷题记

题目大意：

找出第 N 个二进制字符串中的第 K 位

给你两个正整数 n 和 k，二进制字符串  Sn 的形成规则如下：

• S1 = “0”
• 当 i > 1 时，Si = Si-1 + “1” + reverse(invert(Si-1))

其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）

例如，符合上述描述的序列的前 4 个字符串依次是：

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。

示例 1：

输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。

示例 2：

输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。

示例 3：

输入：n = 1, k = 1
输出："0"

示例 4：

输入：n = 2, k = 3
输出："1"

提示：

• 1 <= n <= 20
• 1 <= k <= 2n - 1

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1545

解题思路分析：

解法一：字符串操作

周赛时由于时间原因，并没有考虑太多，直接采用了操作字符串的方式来解题，虽然效率上不高，但通过TC还是可以的。本解法没有任何难度，这里直接上代码：

public char findKthBit(int n, int k) {
    String s="0";
    for(int i=2;i<=n;i++){
        s=s+"1"+reverse(invert(s));
    }
    return s.charAt(k-1);
}

String reverse(String s) {
    StringBuilder sb= new StringBuilder(s);
    sb.reverse();
    return sb.toString();
}

String invert(String s){
    char[] arr=s.toCharArray();
    StringBuilder sb= new StringBuilder();
    for(int i=0;i<s.length();i++){
        sb.append(arr[i]=='1'?'0':'1');
    }
    return sb.toString();
}

---

解法二：二分法，位运算（参考了网友的思路）

1. 首先明确一点，S(n)的长度应为2^n -1.
2. 确定k在S(n)中的位置（前一半，中间位置，后一半）
   1. 当k在中间位置时，解为1。
   2. 当k在前一半，那么，其实是求S(n-1)和k的子问题。
   3. 当k在后一半，那么，k的位置要逆转，使其落在S(n)的前半部分。
   4. k在前半部分的对应位置kk =((2^n -1)/2-1) – (k-1 – ((2^n -1)/2+1))。
   5. 再反转位置kk的处的值，才是位置k的值。S(n)[k] = 反转S(n)[kk] = 反转S(n-1)[kk]。
   6. 这样，问题就变成了S(n-1)和kk的子问题了。

实现代码：

public char findKthBit(int n, int k) {
    int length=(1<<n)-1;
    k--;
    int flip=0;
    while(n > 1){
        length = (1<<n)-1;
        int b=length>>1;
        if(k == b){
            //此位置为1
            return (char)((1 ^ flip)+'0');
        }else if(k > b){
            //在后一半，逆转再反转。将k转到n-1的前一半
            k -= b+1;
            k = b-1-k;
            flip = (flip+1)%2;
        }else{
            //在前一半
        }
        n--;
    }
    return (char)((0 ^ flip)+'0');
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Kth Bit in Nth Binary String.

Memory Usage: 36.4 MB, less than 83.33% of Java online submissions for Find Kth Bit in Nth Binary String.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1545-find-kth-bit-in-nth-binary-string-解题思路分析/