779. The KTH grammar symbol

# # to the chase

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

Resolution:

We first tried to derive the first few cases by hand

// first line: 0 // second line: 01 // third line: 0110 // fourth line: 01101001 / /. / / 01101001011010010110/0110011001/0110100110010110011010011001011001101001 / / 01101001100101101001011001101001011010011001011010010110011010010110100110010110Copy the code

The rest is simply too much to write.

I. Brute force cracking

In the process of derivation, it can be found that each character of the current line is determined by the character of the previous line, and must be twice the size of the previous line. Since manual derivation is possible, it is theoretically feasible to try to complete it by using a computer in accordance with the idea of manual derivation.

Therefore, the transHandle method is written to traverse each character of the string, and then each character is generated in accordance with the rules of 2 characters, and spliced together, and finally return the spliced characters


var transHandle = function (str) {
    let res = ''
    for (let index = 0 ; index < str.length; index++) {
        res += str[index] === '0' ? '01' : '10' 
    }
    return res
}
Copy the code

In the final implementation, just use this method:

var kthGrammar = function(n, k) {
    let str = '0'
    for (let index = 0; index < n - 1; index++) {
        str = transHandle(str)
    }
    return str[k - 1]
};
Copy the code

Theoretically the algorithm is feasible, so submit.

You can see that Leetcode eventually returns out of memory, which means that when n is large, the amount of computation is huge. In fact, it is very difficult to push to the first few lines when calculating manually. It can be imagined that when N is very large, there is a great amount of calculation. Even if the result is calculated in this way, the performance consumption of the computer is also very large. Therefore, this method is not desirable.

Two. Find the underlying logic

So it’s actually not that easy to solve this problem, and you need to figure out what the underlying logic of the number changes is.

1. Try to deduce

When we can’t see the correlation and the trick at first glance, we can try to start with the smallest case, and think step by step as n gets bigger.

When n = 1:

N = 1 is the number they gave us, which is 0, and this is the only number in this case that we don’t have to compute, so it’s the bottom number.

When n = 2:

When n = 2, it becomes 2 numbers, and both numbers are derived from the first number when n = 1.

When n = 3:

When n = 3, it becomes four digits, the first two digits are derived from the first digits of n = 2, and the third and fourth digits are derived from the second digits of n = 2.

From this we can draw a conclusion:

1. If k is even, the KTH in the NTH row is the KTH / 2 in the n-1 row

2. If k is odd, the KTH row is the (k + 1) / 2 of the n-1 row

2. Determine the value

With that in mind, we need to determine how the KTH number in the NTH row relates to the number in the n-1 row.

Highlight!! According to the rules of evolution:

If the n-1 number is 0, then in the NTH row you get 01, and if k is even then this number is 1, and if k is odd then this number is 0

If the n-1 number is 1, then in the NTH row you get 10, and if k is even then this number is 0, and if k is odd then this number is 1

Recursive inverse push

With the above conclusion, then we use a recursive way to reverse, the problem should be able to be solved.

First determine the final return rule, which is the condition for breaking out of recursion:

if (n === 1) {
    if (k === 1) {
        return 0
    } else {
        return 1
    }
}
Copy the code

When n is equal to 1, I just need to know whether k is 1 or 0 to get the final answer.

Start recursion:

If (k % 2 = = = 0) {/ / * * n - 1 the evolution of digital if is zero, so in the first n rows can produce 01 two Numbers, k is an even number that this number is 1, k is odd that the number is 0 / / * * * * n - 1 the evolution of digital if is 1, If k is even then this number will be 0 and k is odd then this number will be 1** return kthGrammar(n-1, k / 2) === 1? 0 : 1 } else { return kthGrammar(n-1, (k + 1) / 2) === 1 ? 1:0}Copy the code

Every time I recurse, the number of rows will be minus 1, and K will figure out what k is for n minus 1 based on parity

That way, when n recurses to the first row, we’ll be able to see where we came from.

Complete code:

/** * @param {number} n * @param {number} k * @return {number} */ 01101001 / /. / / 01101001011010010110/0110011001/0110100110010110011010011001011001101001 / / 01101001100101101001011001101001011010011001011010010110011010010110100110010110 var kthGrammar = function(n, K) {/ / k is an even number N lines of the first line K is N - 1 K / 2 variable to / / K is odd N lines of the first line K is N - 1 (K + 1) / 2 variable to / / reverse the if (N = = = 1) { If (k === 1) {return 0} else {return 1}} if (k % 2 === 0) {// ** if (k % 2 === 0) If k is even then this number will be 1, if k is odd then this number will be 0** // ** n-1 if it's 1, then the NTH row will produce 10, if k is even then this number will be 0, Return kthGrammar(n-1, k / 2) === 1? 0 : 1 } else { return kthGrammar(n-1, (k + 1) / 2) === 1 ? 1:0}};Copy the code

The code is actually very simple, but the logic is very convoluted, or more complex. Brute force cracking is simple but inefficient, and the problem solving priority is to find out the rules and then cheat. Twice the work!

Finally, the submission record is attached!