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:
N
will be an integer in the range[1, 30]
.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); } } };
思路如下:
每一次,减少一层。记录下起始数字。知道只有一层的时候,
-------------------------另一种思路,直接每次计算上一个--------
- Get previous result
a. Be careful of computing the K for previous row - Determine if K is at odd position or even position
- Return the answer of current row
- 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); } };
No comments:
Post a Comment