779.第k个语法符号.md

779.第 k 个语法符号

/*
 * @lc app=leetcode.cn id=779 lang=typescript
 *
 * [779] 第K个语法符号
 */

// @lc code=start
function kthGrammar(n: number, k: number): number {}
// @lc code=end

解法 1: 递归

function kthGrammar(n: number, k: number): number {
  const dfs = (num: number, i: number, k: number): number => {
    if (i === 0) return num
    if (k <= 2 ** (i - 1)) {
      return dfs(num, i - 1, k)
    } else {
      return dfs(num ^ 1, i - 1, k - 2 ** (i - 1))
    }
  }
  return dfs(0, n - 1, k)
}

Case

test.each([
  { input: { n: 1, k: 1 }, output: 0 },
  { input: { n: 2, k: 1 }, output: 0 },
  { input: { n: 2, k: 2 }, output: 1 },
])('input: n = $input.n, k = $input.k', ({ input: { n, k }, output }) => {
  expect(kthGrammar(n, k)).toEqual(output)
})