每日一题做题记录，参考官方和三叶的题解

题目要求

思路：递归+倒推

• 一个经典逆向思维，假设目标位置为111（或000），倒退回第一行检查答案是否正确，毕竟只有两种数字非此即彼。
  • 构建一个递归函数DFS(row,col,cur)DFS(row,col,cur)DFS(row,col,cur)，表示第rowrowrow行第colcolcol列的数字为curcurcur；
  • 根据构造规则，若奇数列位置为111，或偶数列位置为000，那上一行对应位置应为111，反之为000；
  • 上一行对应位置与当前行位置关系满足colrow−1=⌊col+12⌋col_{row-1}=\lfloor\frac{col+1}{2}\rfloorcolrow−1​=⌊2col+1​⌋；
  • 当回到第一行时返回结果，若此时结果为000说明假设正确返回假设数字，否则说明假设错误返回另一个数字。

Java

class Solution {
    public int kthGrammar(int n, int k) {
        return DFS(n, k, 1) == 0 ? 1 : 0;
    }
    int DFS(int row, int col, int cur) {
        if (row == 1) // 首行
            return cur;
        if((col % 2 == 1 && cur == 1) || (col % 2 == 0 && cur == 0))
            return DFS(row - 1 , (col + 1) / 2, 1);
        else
            return DFS(row - 1, (col + 1) / 2, 0);
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

C++

class Solution {
public:
    int kthGrammar(int n, int k) {
        return DFS(n, k, 1) == 0 ? 1 : 0;
    }
    int DFS(int row, int col, int cur) {
        if (row == 1) // 首行
            return cur;
        if((col % 2 == 1 && cur == 1) || (col % 2 == 0 && cur == 0))
            return DFS(row - 1 , (col + 1) / 2, 1);
        else
            return DFS(row - 1, (col + 1) / 2, 0);
    }
};

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

Rust

impl Solution {
    pub fn kth_grammar(n: i32, k: i32) -> i32 {
        if Self::DFS(n, k, 1) == 0 {
            return 1;
        }
        0
    }
    fn DFS(row: i32, col: i32, cur: i32) -> i32 {
        if (row as i32 == 1) { // 首行
            return cur as i32;
        }
        if((col as i32 % 2 == 1 && cur as i32 == 1) || (col as i32 % 2 == 0 && cur as i32 == 0)) {
            return Self::DFS(row - 1 , (col + 1) / 2, 1) as i32;
        }
        else {
            return Self::DFS(row - 1, (col + 1) / 2, 0) as i32;
        }
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

思路二：找规律+位运算

• 这个思路是怎么推过来的不知道，但规律是这样出来的……
  • 首先可以发现每一行的前几位都是上一行的内容，所以第kkk个位置的内容和行数无关；
  • 这个序列走向是0110100110…0110100110\dots0110100110…
  • 若从000开始索引，索引和对应数字的对应关系如下：

    索引	数字
    0	0
    1	1
    2	1
    3	0
    4	1
    5	0
    6	0
    7	1
    ……	……

  • 为什么要从000开始呢：

    索引	索引的二进制	索引二进制中111的数量	数字
    0	0	0	0
    1	1	1	1
    2	10	1	1
    3	11	2	0
    4	100	1	1
    5	101	2	0
    6	110	2	0
    7	111	3	1
    ……	……	……	……

  • 发现当前位数字只和索引二进制表示中111的数量有关，数量为偶时为000，数量为奇时为111。Coun

Java

class Solution {
    public int kthGrammar(int n, int k) {
        return Integer.bitCount(k - 1) & 1;
    }
}

• 时间复杂度：O(1)O(1)O(1)，取决于bitCount()函数的复杂度
• 空间复杂度：O(1)O(1)O(1)

bitCount()

• 学习参考链接
  • 里面简述了源码的实现思路，很有趣很巧妙

C++

class Solution {
public:
    int kthGrammar(int n, int k) {
        return __builtin_popcount(k - 1) & 1;
    }
};

• 时间复杂度：O(1)O(1)O(1)，取决于__builtin_popcount()函数的复杂度
• 空间复杂度：O(1)O(1)O(1)

__builtin_popcount()

• 学习参考链接
  • 和java那个是一样的实现思路

Rust

impl Solution {
    pub fn kth_grammar(n: i32, k: i32) -> i32 {
        (k - 1).count_ones() as i32 & 1
    }
}

• 时间复杂度：O(1)O(1)O(1)，取决于()函数的复杂度
• 空间复杂度：O(1)O(1)O(1)

总结

• 快乐逆向思维~
• 这个找规律是真的巧

欢迎指正与讨论！