Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

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

Train of thought

  1. Write a way to change, each round replace 0 with 01,1 with 10;
  2. After going through a loop and making the substitution, the final string is stored asresult;
  3. resultThe first[k-1]That’s what we’re looking for.

implementation

/ * * *@param {number} n
 * @param {number} k
 * @return {number}* /
var kthGrammar = function(n, k) {
    let result = "0";
    while (n > 1) {
        result = replaceNumber(result);
        n--;
    }

    return result[k - 1];
};

// Replace the current value
function replaceNumber(str) {
    let arr = str.split("");

    return arr.reduce((total, cur) = > {
        total += cur === "0" ? "01" : "10";
        return total;
    }, "");
}
Copy the code

The results of

The space spills out, which means the problem refuses to use violence, so we need to find a pattern.

Looking for a regular

We can look directly at the output of the previous rounds and see an interesting pattern:

Through observation, it is found that the value of the current row is equal to the value of the previous row + the value of the previous row. So we can turn this into a recursive problem: we can slice the entire string so that if the current row is in the left half, it is equal to the last round, and if it is in the right half, it is equal to the last round, and so on.

/ * * *@param {number} n
 * @param {number} k
 * @return {number}* /
var kthGrammar = function(n, k) {
    / / boundary
    if (n === 1) return 0;

    // First calculate the current total length, starting from 1 and doubling each round
    let len = Math.pow(2, n - 1);

    // If k is in the left half, take the value directly; if k is in the right half, take the value invert
    if (k > len / 2) {
        return Number(! kthGrammar(n -1, k - len / 2));
    } else {
        return kthGrammar(n - 1, k); }};Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.