779. K-th Symbol in Grammar ---M

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

Note:

1. N will be an integer in the range [1, 30].
2. K will be an integer in the range [1, 2^(N-1)].

 

A:

这个就是自己好好观察，找出来的解法。挺好

class Solution {
public:
    int kthGrammar(int N, int K) {
        return helper(N, K, 0);
    }
private:
    int helper(int N, int K, int start){ // start can only be 0 or 1
        if(N==1)
            return start;        
        int halfCount = pow(2,N-2);
        if(halfCount >= K){//on left side
            return helper(N-1,K,start);
        }else{
            return helper(N-1, K - halfCount,1-start);
        }
    }
};

思路如下：

每一次，减少一层。记录下起始数字。知道只有一层的时候，

-------------------------另一种思路，直接每次计算上一个--------

1. Get previous result
   a. Be careful of computing the K for previous row
2. Determine if K is at odd position or even position
3. Return the answer of current row
4. Terminal condition happens when N == 1

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N==1) 
            return 0;        
        int previous = kthGrammar(N-1, (K+1)/2);
        int pos = K%2;
        return previous ? (pos) : (pos?0:1);
    }
};