動機

十分有趣的題目

Problem

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 = 1Output: 0Explanation: row 1: 0

Example 2:

Input: n = 2, k = 1Output: 0Explanation:row 1: 0row 2: 01

Example 3:

Input: n = 2, k = 2Output: 1Explanation:row 1: 0row 2: 01

Example 4:

Input: n = 3, k = 1Output: 0Explanation:row 1: 0row 2: 01row 3: 0110

 

Constraints:

  • 1 <= n <= 30
  • 1 <= k <= 2n - 1

Sol: complete binary tree

給定深度與第幾個就可以透過binary去locate在樹上移動的方向

詳細可以看1261

class Solution:
    def f(self,dirs):
        acc = 0
        for d in dirs:
            if acc == 0:
                acc = 0 if d == '0' else 1
            else:
                acc = 1 if d == '0' else 0
        return acc
    def kthGrammar(self, N: int, K: int) -> int:
        dirs = list(format(2**(N-1)+(K-1),'b'))[1:]
        return self.f(dirs)

Sol2: recursion

從root根據N與K會發現沒辦法判斷要怎麼走，所以改從leaf看，可以看到類似上面的走法，但這裡不用reverse是用recursion

一開始是當K為奇數時是0，偶數為1；在翻轉過後當K為奇數時是1，偶數為2

def f(n,k):
    if n == 1:
        return False
    else:
        ret = f(n-1,math.ceil(k/2))
        if k % 2 == 1:
            return ret
        else:
            return not ret
class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        return 1 if f(N,K) else 0

def f(n,k):
    if n == 1:
        return False
    else:
        ret = f(n-1,math.ceil(k/2))
        if ret: # flip
            return k % 2 == 1
        else:
            return k % 2 == 0
class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        return 1 if f(N,K) else 0

Sol3: count bit

把K扣一，變成0-based indexing，轉成binary，數有幾個1，就是被翻轉幾次，偶數次就是0，奇數次就是1

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        return bin(K-1).count('1')%2