Leetcode 779. K-th Symbol in Grammar

Welcome to the 70th LeetCode Weekly Contest hosted by App Academy

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

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

Note:

1. N will be an integer in the range [1, 30].
2. K will be an integer in the range [1, 2^(N-1)].

分析:

解法一(暴力法)：

从row 1开始直到row N，每行基于前一行结果替换0为01，1为10. 时间复杂度高，提交会报超时错误。

解法二(递归法)：

仔细分析row 1到4，可以看出这几条规律：

1. row n二进制个数是 row n-1的两倍
2. row n前一半二进制等于row n-1
3. row n后一半二进制是row n-1二进制取反

因此，经验证我们可以得到如下两个结论：

1. 如果K位于当前row的二进制个数前一半，即K<=n/2(当前行二进制个数n=2^(N-1))，那么第k个数等于上一行(row-1)第k个数.
2. 相反如果位于后一半，那么第K个数等于上一行(row-1)第K-n/2的相反值

代码：

class Solution {
  public int kthGrammar(int N, int K) {
    boolean grammar = findkth(N, K);
    return grammar == false ? 0 : 1; // false为0， true为1
  }

  private boolean findkth(int N, int K) {
    if (N == 1) {
      return false;
    }
    int n = (int) Math.pow(2, N - 1);
    if (K > n / 2) { // K位于二进制个数后一半,对应前一行的相反值
      return !findkth(N - 1, K - n / 2);
    } else { // K位于二进制个数前一半，等于前一行的值
      return findkth(N - 1, K);
    }
  }
}