一、题目
二、思路
注意本题题目说的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 返回,如下:
程序日志输出如下:第1行, 第 1个数, 值为0
。
n=2, k=1
直接 return 0 返回,如下:
最终返回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行】,断点如下:
【代码第30行】用 n - 1 行,的第k个元素,的取反即可。递归调用 KthGrammar(1, 1), 在其中用 return 0
终止递归条件。断点如下:
【代码第30行】递归结束后的结果0,需与【代码第30行】的 1 做异或运算,得到 1 ^ 0 = 1, 最终结果为1,结束。
程序日志输出如下:第2行, 第 2个数, 值为1
。
n = 3, k = 1
用 return 0 直接返回,断点如下:
程序日志输出如下:第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),断点如下:
【递归到代码第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
。