779. 第K个语法符号解法

题目

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

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

用例

输入: N = 1, K = 1
输出: 0

输入: N = 2, K = 1
输出: 0

输入: N = 2, K = 2
输出: 1

输入: N = 4, K = 5
输出: 1

//这里用了递归的思想，可以按照路线并返回到原来的位置，然后输出数据
class Solution {
public:
    int kthGrammar(int N, int K) {
        if(N==1)
        return 0;
        else
        {
            int f=K/2;
            int m;
            if(K%2==0)
            {
                m=kthGrammar(N-1,f);
                if(m==0)
                    m=1;
                else
                    m=0;
            }
            else
            {
                m=kthGrammar(N-1,f+1);
                if(m==0)
                    m=0;
                else
                    m=1;
            }
            return m;
        }
    }
};
此题为Leetcode上，779号题