LEETCODE 1545. Find Kth Bit in Nth Binary String 解题思路分析

题目大意:

找出第 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 个字符串依次是:

  • S= "0"
  • S= "011"
  • S= "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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。