LeetCode 1545. Find the k-th bit in the nth binary string

1545. Find out the N Of the binary strings K position

Here are two positive integers n and k, Binary string Sn The formation rules of are as follows ：

• S1 = "0"
• When i > 1 when ,Si = Si-1 + "1" + reverse(invert(Si-1))

among + Indicates series operation ,reverse(x) Return to reverse x The resulting string , and invert(x) Will flip x Every one of you （0 Turn into 1, and 1 Turn into 0）.

for example , The first of the sequences described above 4 The strings are ：

• S1 = "0"
• S2 = "0**1**1"
• S3 = "011**1**001"
• S4 = "0111001**1**0110001"

Please return Sn Of The first k Bit character , Topic data assurance k It must be Sn Within the length range .

Example 1：

 Input ：n = 3, k = 1
 Output ："0"
 explain ：S3  by  "0111001", Its first  1  Position as  "0" .

Example 2：

 Input ：n = 4, k = 11
 Output ："1"
 explain ：S4  by  "011100110110001", Its first  11  Position as  "1" .

Example 3：

 Input ：n = 1, k = 1
 Output ："0"

Example 4：

 Input ：n = 2, k = 3
 Output ："1"

Tips ：

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

Two 、 Method 1

recursive

class Solution {
    
    public char findKthBit(int n, int k) {
    
        if (k == 1) {
    
            return '0';
        }
        int mid = 1 << (n - 1);
        if (k == mid) {
    
            return '1';
        } else if (k < mid) {
    
            return findKthBit(n - 1, k);
        } else {
    
            k = mid * 2 - k;
            return invert(findKthBit(n - 1, k));
        }

    }
    public char invert(char a) {
    
       return (char) ('0' + '1' - a); 
    }
}

Complexity analysis

• Time complexity ：O(n). character string S_n The length of is 2^n-1, Each recursive call can reduce the search range by half , So the time complexity is zero O(log2n)=O(n).

• Spatial complexity ：O(n). The space complexity mainly depends on the stack space generated by recursive calls , The number of recursive call layers will not exceed n.