題目敘述
We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. 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.
For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.
Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.
Example 1.
Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0
Example 2.
Input: n = 2, k = 1
Output: 0
Explanation:
row 1: 0
row 2: 01
Example 3.
Input: n = 2, k = 2
Output: 1
Explanation:
row 1: 0
row 2: 01
限制:
- 1
<= n <=30 - 1
<= k <=
解題思路：
相信大家看到這題的第一個想法都會是想要把 第 n 行 整個找出來之後再去找那一行的 第 k 個元素 就好了！
但這個方法如果用到迴圈的話會佔據大量的記憶體（每一層迴圈都會需要一個 string 的記憶體），所以我們就會需要找一個空間複雜度更好的解法。
認真觀察每一層的字串我們可以發現每一層的字串都可以分成前後兩部分，前半長個跟上一層一樣，而後半則是上一層的相反
例如：n = 3時，第一層為 0，第二層是 01，也就可以看成前半和第一層相同的 0 和後半是第一層相反的 1。同理第三層的 0110 可以看成前半和第二層相同的 01 還有第二層相反的 02。
有了這個脈絡之後其實我們就可以利用迴圈的方式，一圈一圈的往下找，如果 k 是在字串的後半部的話，再找下一圈的時候就找 k - mid（也就是 k 在前半的對照）之後再把那個值顛倒過來就可以了！
解題步驟：
- 先設定迴圈的跳出條件也就是如果
n = 1且k = 1的時候回傳0 - 找到每一行的中間值
- 如果 k < 中間值在下一行就找第 k 個，如果 k > 中間值的話就找他映射在前半的值之後在反過來。
Java 解法
class Solution {
public int kthGrammar(int n, int k) {
if (n == 1 && k == 1) {
return 0;
}
int mid = (int) (Math.pow(2, n-1) / 2);
if (k <= mid) return kthGrammar(n - 1, k);
else return kthGrammar(n - 1, k - mid) == 1 ? 0 : 1;
}
}Complexity
- Time Complexity: O(n);
- Space Complexity: O(1);