[LeetCode] 779. K-th Symbol in Grammar

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)].

第K个语法符号。

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）。

这道题属于数学/递归。我这里引用了一个帖子，如果你把这个替换的结果以一棵树的形式画出来，思路就比较好总结了。题目问的是找第 N 行的第 K 个数字。因为对于每一行来说，都是由他的上一行衍生出来的，所以递归函数写的时候也应该跟上一行有关，且第 N - 1 行的一个元素依次确定第 N 行的两个元素。并且我们可以分类K的奇偶和 (K+1) / 2 的取值得出递推关系。base case是当 N = 1 的时候，返回 0。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int kthGrammar(int N, int K) {
 3         // base case, first row
 4         if (N == 1) {
 5             return 0;
 6         }
 7 
 8         // normal case
 9         if (K % 2 == 0) {
10             if (kthGrammar(N - 1, K / 2) == 0) {
11                 return 1;
12             } else {
13                 return 0;
14             }
15         } else {
16             if (kthGrammar(N - 1, (K + 1) / 2) == 0) {
17                 return 0;
18             } else {
19                 return 1;
20             }
21         }
22     }
23 }

LeetCode 题目总结

[LeetCode] 779. K-th Symbol in Grammar

原文：https://www.cnblogs.com/cnoodle/p/14692047.html