第K个语法符号

题目描述：

从第一层开始，第一层0，第二层01，第三层0110，规律是把上面一层的0用01替换，1用10替换
现在要求取得第N层的第K个数字。

思路分析：

拿到题目的时候首先想到的是递归，考虑取到第N-1层，然后遍历第N-1层的每个字符，是0就替换成01，是1就替换成10。

代码实现：

自己测试根据该递归得到的具体第N行的结果：

显然，根据该递归，得到的结果是正确的，但是放力扣上提交就会提示超出时间限制

pic-1599023154635.png

超出时间限制，肯定是因为程序运行的时间太长了。分析可能原因是对递归的中间值未做map存储，可是加了map之后还是无效，这是因为这个递归是从上至下的递归，对中间递归值的缓存是无效的。只有对从下至上的递归缓存中间递归值才可以改善运行时间。
所以，这里就需要找另外一种递归方法了，参考该题解。

自己总结分析：

pic-1599023154636.png

第一种：

pic-1599023154637.png

第二种：

pic-1599023154638.png

分析：

如果第n行的第k个值所对应的父节点是0，那么再去判断k的奇偶性，如果k是奇数，那么则表示为0，如果是偶数则表示为1。
同理可知，第n行的第k个值所对应的父节点是1，那么再去判断k的奇偶性，如果k为奇数，那么表示该值为1，如果是偶数，那么表示该值为0。

代码：

pic-1599023154639.png