推 NTHUlagka: 大師 10/25 15:23
https://leetcode.com/problems/k-th-symbol-in-grammar/description
779. K-th Symbol in Grammar
給你一個數字 n 和一個數字 k，n 表示第幾列 k 表示第幾行（列和行從 1 開始）
第一列的數字固定為 0，第一列之後的數字按照以下規律：
取代前一列的所有 0 -> 01 取代前一列的所有 1 -> 10
Example：
n = 3，則
ROW1=0
ROW2=01
ROW3=0110
求出第 n 列的第 k 個數字是多少。
思路：
1.題目的測資範圍 n 最大為30，如果我們一個一個轉換數字的話會產生一個 2^30
長度的值，int 長度不夠，存到 string 的話記憶體會超出限制，我們必須找到
一個方法看能不能不找出整個字串但卻可以知道他指定位置的數字。
2.因為每一個數字在下一列可以產生兩個數字，所以我們可以把問題轉為一個完滿
二元樹，當 n = 3 的時候樹如下所示：
0
/ \
0 1
/ \ / \
0 1 1 0
3.觀察圖形，發現一個規律，一個位置是 1 還是 0 取決於：
(1) 這個位置是左子節點還是右子節點。
(2) 這個位置的父節點值。
如果當前節點是左子節點，那他就和他的父節點編號相同。
如果當前節點是右子節點，那他就和他的父節點編號相反。
4.所以我們要從指定層數的節點往上找出當前點的父節點值是什麼，找父節點的方式
可以寫成遞迴關係式去找，因為他是一個完滿二元樹，所以要判斷當前點是左還是
右子節點可以用 (k + 1)/2 去判斷，如果為奇數就表示為左子節點反之為右。
Java Code：
-------------------------------------------------
class Solution {
public int kthGrammar(int n, int k) {
if (n == 1) {
return 0;
}
int parent = kthGrammar(n - 1, (k + 1) / 2);
return k % 2 == 1 ? parent : parent ^ 1;
}
}
-------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698215390.A.678.html