“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

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

​

Their thinking

​

1. We generate all the lines from the previous one except for the first one. The rule is that 0 is converted to 01, and 1 to 10. If the number of rows is equal to 1, we can simply return 0 3. Otherwise, we can find a length of n rows 4. If the current k is greater than half the length of the current row, we take the opposite value 5. The current row k is less than half the length of the current row, so we just take the value of the previous rowCopy the code

​

Code implementation

​

* @param {number} n * @param {number} K * @return {number} */ var kthGrammar = function (n, If (n === 1) return 0; if (n == 1) return 0; Let len = math.pow (2, n-1); If (k > len / 2) {let res = kthGrammar(n-1, k-len / 2); let res = kthGrammar(n-1, k-len / 2); return res === 0 ? 1:0; } else {return kthGrammar(n-1, k);} else {return kthGrammar(n-1, k); }};Copy the code

If you have any questions about this topic, feel free to leave them in the comments section;