LeetCode-779. K-th Symbol in Grammar

LeetCode-779. K-th Symbol in Grammar

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 = 1Output: 0Input: N = 2, K = 1Output: 0Input: N = 2, K = 2Output: 1Input: N = 4, K = 5Output: 1Explanation:row 1: 0row 2: 01row 3: 0110row 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)]​​.

题解：

第一次超时：

class Solution {public: int kthGrammar(int N, int K) { vector v(1, 0); for (int i = 1; i < N; i++) { for (int j = 0; j < pow(2, i); j+= 2) { if (v[j] == 0) { v.insert(v.begin() + j + 1, 1); } else if (v[j] == 1) { v.insert(v.begin() + j + 1, 0); } } } return v[K - 1]; }};

第二次内存溢出：

class Solution {public: int kthGrammar(int N, int K) { string idx = "0"; for (int i = 0; i < N - 1; i++) { string idx2 = ""; for (int j = 0; j < idx.length(); j++) { if (idx[j] == '0') { idx2 += "01"; } else if (idx[j] == '1') { idx2 += "10"; } } idx.clear(); idx = idx2; } return idx[K - 1] - 48; }};

心态崩了哟= =，那肯定不是借助额外内存空间或者遍历来解题了，应该是数学规律，每次的串前一半跟上一串相同，后一半是前一半的取反，ac。

class Solution {public: int kthGrammar(int N, int K) { if (N == 1) { return 0; } if (K <= pow(2, N - 2)) { return kthGrammar(N - 1, K); } else { if (kthGrammar(N - 1, K - pow(2, N - 2)) == 0) { return 1; } else { return 0; } } }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。