【位运算】B017

【位运算】B017

一、Problem

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）

输入: N = 4, K = 5
输出: 1解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

注意：

N 的范围 [1, 30].
K 的范围 [1, 2^(N-1)].

二、Solution

方法一：递归

思考

K 很大，休想骗我拿出暴力法；

规律是：第 N 行的前半段由第 N-1 行整行构成，后半段由第 N-1 行的每位数字取反得到；也就是说如果 K > 第 N-1 行数字的个数 last_sz，则第 K 位数字一定在第 N 行的后半段的 K-last_sz 位置处，且和前半段对称位置的数字"不同"

class Solution {
public:int dfs(int n, int k) {if (n==1) return 0;if (n==2) return k==1 ? 0 : 1;int sz = (1 << n-1) >> 1;if (k <= sz) return  dfs(n-1, k);else         return !dfs(n-1, k-sz);}int kthGrammar(int N, int K) {return dfs(N, K);}
};

复杂度分析

• 时间复杂度： O ( n ) O(n) O(n)，
• 空间复杂度： O ( 1 ) O(1) O(1)