779. K-th Symbol in Grammar - Medium

前往題目

想法

• Recursion?

思路

把圖畫出來會發現是一個類似樹的結構，可以判斷是在左分支還是右分支每次都去除一半，直到k層

1. 左右雙指針
2. 疊代n-1次，因為第一次是起始點0，所以跳過
3. 每次決定中點
4. 並判斷k是否在中點的左邊或右邊
5. 在左邊的話會和之前的數字一樣，而右邊會和之前的相反
6. 最後直接輸出數字

/*
 0
0 1
以及
 1
1 0
可以看到左邊都和上面的數字一樣，右邊都和上面的數字相反
*/

Code

class Solution {
    public int kthGrammar(int n, int k) {
        int left = 0, right = (int) Math.pow(2, n - 1);

        int cur = 0; // The digit

        // N - 1 times since skipping the first row
        for (int i = 0; i < n - 1; ++i) {
            // Decide current mid point
            int mid = (left + right) / 2;

            // Decide which side to search
            if (k <= mid) { // left side
                right = mid; // Shrink the range
            } else { // right side
                left = mid + 1;
                cur = cur == 0 ? 1 : 0;
            }
        }

        return cur;
    }
}