779. The KTH grammar symbol

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

Get operation stack

Train of thought

According to the problem, we start with the first row 0 and replace the 0 and 1 in the previous row according to the problem rule

  • Violence to solve
    • Generate a string for each line, as the question asks, and get the KTH character directly

Question:

Because each line of string is twice as long as the previous line, the string grows 2 to the n, so the string grows by several degrees very fast, resulting in very slow speed

  • Get operation stack

Observing the meaning of the question, we can find that the question is actually a binary tree structure, 0 root node and child node are respectively [0,1]. Then the children of 0 are [0,1], and the children of 1 are [1,0]…

When we want the NTH row, the KTH value. If we know the value of its parent, and whether the left or right child tree currently belongs to the parent, we can deduce the value of the current node from the parent (for example: If the parent node is 0 and the current node is the left subtree of the parent node, then the current value is 0), similarly, we just need to continue to work up to the root node, and we can gradually get the value of the KTH node in the NTH row according to the operation of each step

So how do you determine whether the current KTH value is in the left subtree or the right subtree?

In fact, if you look at even and odd of k, you know that odd is the left subtree, and even is the right subtree

How do you determine which digit in the previous row the parent node belongs to?

If k is odd, the parent is (k +1) /2. If k is even, the parent is (k /2), so we just round up k/2. I know where the parent is in the previous row

Once we get the location of the parent node, how do we know if the parent node belongs to the left or right child tree of the grandparent node?

With the first step

.

Similarly up here, when we get to row 2, we know that the parent of row 2 has to be 0, and if we know whether we’re in the do or the right subtree, we can determine the value of the current row, and similarly, once we have the entire stack, we can recurse to row NTH and KTH

The code is as follows:

First we iterate over n, and n gradually diminishs. According to the above rules, we use [n,k,pos] ([NTH row, KTH element, left or right subtree (left is 0, right is 1)]) to represent the information required by the current row, and push to treeStack to obtain the left and right operation stack

Then iterate through the operation stack, using curr to represent the value of the parent node, and get the value of the next row according to the position of the left and right subtrees, and update the curr to continue, and the last updated curr is the value we need

Returns the curr

var kthGrammar = function (n, k) {
    if (n === 1 && k === 1) return '0'
    var treeStack = []
    while (n > 1) {
        var pos = k % 2= = =0 ? 1 : 0
        var opt = [n, k, pos]
        k = Math.ceil(k / 2)
        treeStack.push(opt)
        n--
    }
    var curr = '0'
    while (treeStack.length) {
        var item = treeStack.pop()
        var newCurr = curr === '1' ? '10' : '01'
        var index = item[2]
        curr = newCurr[index]
    }
    return curr
};
Copy the code