[B] [C] [D]

Let’s put a 0 in the first line. For each subsequent line, replace the 0 in the previous line with 01 and the 1 with 10.

Given line number N and ordinal number K, return the KTH character in the NTH line. (K starts at 1)

Example:

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: First line: 0 Second line: 01 Third line: 0110 Line 4:01101001Copy the code

Note:

  1. NThe scope of the30] [1,.
  2. KThe scope of the[1, 2^(N-1)].

The simplest and most direct way to solve the problem is to find the result of the NTH line, and then return the KTH character.

The code is as follows:

Var kthGrammar = function(n, k) {let pre = '0',cur = ''; For (let I = 2; i<=n; i++){ cur = ''; for(let j = 0; j<pre.length; j++){ if(pre[j]==='0') cur += '01' else cur += '10' } pre = cur; } // return cur.substr(k-1,1)};Copy the code

But this version of the code will burst when the test case enters line 30, because the result string at line 30 is 2 ^ 31, which is out of memory

So since we can’t solve this problem directly, let’s say that we need to find the relationship between the characters of the lines, and deduce the NTH row and the KTH character from this relationship

Here we construct the first five rows of data as follows

The results are shown below:

You can see this by looking at the picture above

Rule 1

The k value of a node in the following row is equal to the k value of the node that created it multiplied by 2 or multiplied by 2 and subtracted by 1

Thus, the formula for calculating the value of k of the parent node by the value of k of the current node => math.ceil (k/2)

Rule 2

If the k value of the child node is odd, it will have the same value as the parent node, and conversely, it will have the opposite value

With these two rules in mind, let’s think of a process that starts at the bottom node and goes up to k = 1, where the current node is the far left of the row and all nodes with k = 1 have a value of 0

So we go back up from the target node, and as we go back we record the flag as its relationship to the parent node

Finally, when the node k = 1 is backtracked, because the value of this node must be 0, the value of the target node can be deduced according to the state of flag at this time

If flag = true, the target node has the same value as the object and returns 0; otherwise, 1 is returned

The code is as follows:

Var kthGrammar = function(n, k) {// flag let flag = true; / / when k! While (k>1){// If (k>1){ (k%2)) flag = ! flag; K = math.ceil (k/2); } if(flag) return 0; return 1; };Copy the code

At this point we are done with leetcode-779- the KTH syntactic symbol

If you have any questions or suggestions, please leave a comment!