【LeetCode】779. 第K个语法符号

思路

参考自Ikaruga的题解

通过上图分析，可以得到其实第N行的第K个数字，可以从第N-1行的第(K-1)/2+1个数字产生
因此可以采用递归的方法进行处理

代码

//公式法
//通过找规律可以发现
//第n行的第k个等于第n-1行的第(k-1)/2+1个数产生
//第n-1行的第(k-1)/2+1个数可能为0，可能为1，所以要分两种情况
//判断第n行中的第k个数字，属于奇数还是偶数，奇数选择第一个数字，偶数选择第二个数字（通过%号来选择）
class Solution {
public:
	int kthGrammar(int N, int K) {
		if (N == 1) return 0;
		return kthGrammar(N - 1, (K - 1) / 2 + 1) == 0 ? (K - 1) % 2 : 1 - (K - 1) % 2;
	}
};