一、题目

题目
题解

二、思路

注意本题题目说的n和k都是从1开始的。

列出各行找规律,利用本行和上一行的关系,递归实现。

列出数字,找规律
第n=1行,0
第n=2行,01
第n=3行,0110
第n=4行,01101001
第n=5行,0110100110010110

我们可以发现如下规律:

  • 每行有 math.pow(2, n-1) 个数字
  • 对于第n行的第k个数字,若k在第n行的前半部分,其值与第n-1行的第k个数字的值相同,可利用递归思想,逐步减少数据范围,最终递归到第1行求解。
  • 对于第n行的第k个数组,若k在第n行的后半部分,其值与第n-1行的第 (k - (第n-1行的总数字个数)) 个数字的值相反。
    • 剩下的就是如何用公示描述上述问题了,具体如下:
    • 第n-1行的总数字个数,可通过 math.pow(2, n-2) 表示
    • 数字的取反(即数字0翻转为1,数字1翻转为0),可通过异或操作实现,即 1 ^ 1 = 0,1 ^ 0 = 1。
  • 递归会逐步缩小数据范围,终止条件即为到第n=1行,该行只有一个数字,返回该数字即可。

有了这些规律,我们即可实现代码了,具体编码如下:

func kthGrammar(n int, k int) int {
    if n == 1 {
        return 0
    }
    halfNumsInThisLine := 1 << (n-2)
    if k > halfNumsInThisLine {
        posInPrevLine := k - halfNumsInThisLine
        return 1 ^ kthGrammar(n-1, posInPrevLine)
    }
    return kthGrammar(n-1, k)
}

三、编码

完整的go程序,结合指定的输入数据,最终输出结果如下:

package main

import (
	"fmt"
	"math"
)

func main() {
	lines := 6
	for n := 1; n < lines; n++ {
		numsInLine := int(math.Pow(float64(2), float64(n-1)))
		for k := 1; k <= numsInLine; k++ {
			x := kthGrammar(n, k)
			fmt.Printf("第%v行, 第%2d个数, 值为%v\n", n, k, x)
		}
		println()
	}
	select {}
}

func kthGrammar(n, k int) int {
	if k == 1 {
		return 0
	}
	if k > 1<<(n-2) {
		return 1 ^ kthGrammar(n-1, k-1<<(n-2))
	}
	return kthGrammar(n-1, k)
}

输出结果如下:

第1行, 第 1个数, 值为0

第2行, 第 1个数, 值为0
第2行, 第 2个数, 值为1

第3行, 第 1个数, 值为0
第3行, 第 2个数, 值为1
第3行, 第 3个数, 值为1
第3行, 第 4个数, 值为0

第4行, 第 1个数, 值为0
第4行, 第 2个数, 值为1
第4行, 第 3个数, 值为1
第4行, 第 4个数, 值为0
第4行, 第 5个数, 值为1
第4行, 第 6个数, 值为0
第4行, 第 7个数, 值为0
第4行, 第 8个数, 值为1

第5行, 第 1个数, 值为0
第5行, 第 2个数, 值为1
第5行, 第 3个数, 值为1
第5行, 第 4个数, 值为0
第5行, 第 5个数, 值为1
第5行, 第 6个数, 值为0
第5行, 第 7个数, 值为0
第5行, 第 8个数, 值为1
第5行, 第 9个数, 值为1
第5行, 第10个数, 值为0
第5行, 第11个数, 值为0
第5行, 第12个数, 值为1
第5行, 第13个数, 值为0
第5行, 第14个数, 值为1
第5行, 第15个数, 值为1
第5行, 第16个数, 值为0

四、逐行代码断点

n=1, k=1

直接 return 0 返回,如下:

【LeetCode】779、第K个语法符号 【中等】-LMLPHP
程序日志输出如下:第1行, 第 1个数, 值为0

n=2, k=1

直接 return 0 返回,如下:

【LeetCode】779、第K个语法符号 【中等】-LMLPHP

最终返回0。

程序日志输出如下:第2行, 第 1个数, 值为0

n=2, k=2

【代码第25行】1<<(n-2) 即为 math.pow(2, (n-2)) 之意,此表达式结果为1,说明第n=2行,的上一行(即第n-1行),有1个元素

【代码第25行】而 k > 1 成立,即 k 是第 n 行的后半部分,则进入【第30行】,断点如下:

【LeetCode】779、第K个语法符号 【中等】-LMLPHP

【代码第30行】用 n - 1 行,的第k个元素,的取反即可。递归调用 KthGrammar(1, 1), 在其中用 return 0 终止递归条件。断点如下:

【LeetCode】779、第K个语法符号 【中等】-LMLPHP

【代码第30行】递归结束后的结果0,需与【代码第30行】的 1 做异或运算,得到 1 ^ 0 = 1, 最终结果为1,结束。

程序日志输出如下:第2行, 第 2个数, 值为1

n = 3, k = 1

用 return 0 直接返回,断点如下:

【LeetCode】779、第K个语法符号 【中等】-LMLPHP
程序日志输出如下:第3行, 第 1个数, 值为0

n = 3, k = 2

【代码第25行】第n=3行,的上一行(即第 n=2行),共 math.pow(2, 3-2) = 2 个数字,而 k 在第n行的前半部分,因此【代码第25行】的判断不成立,未进入【代码第30行】,而进入【代码第32行】

【代码第32行】递归调用 kthGrammar(2, 2),断点如下:

【LeetCode】779、第K个语法符号 【中等】-LMLPHP
【递归到代码第25行】kthGrammar(2, 2) 即意为求第n=2行的第k=2个数字,因为第2行的上一行(即第1行)有1个数字,而第k=2个数字大于1,因此【代码第25行】的判断成立,进入【代码第30行】

【代码第30行】n-1即为2-1即为1,k-math.pow(2,(n-2))即为2-math.pow(2,0)即为2-1即为1,即调用1 ^ KthGrammar(1,1),即意为第n-1行(第1行)的第1个数字的取反。

【代码第23行】递归调用 KthGrammar(1,1) ,通过 return 0,终结递归条件。递归结束后,向上层函数(即KthGrammar(2,2))返回。

【代码第30行】n = 2, k = 2 时,1 ^ KthGrammar(1,1) 得到 1 ^ 0 = 1。递归结束后,向上层函数(即KthGrammar(3,2))返回。

【代码第32行】n = 3, k = 2 时,直接返回 KthGrammar(2, 2) 的结果 1,因为再没有更上层的递归函数了,因此最终返回 1,结束。

程序日志输出如下:第3行, 第 2个数, 值为1

10-20 14:45