leetcode779 第k个语法符号。

作者: goto2091

直接找规律。

第一行 0

第二行 01

第三行 0110

第四行 01101001

可以发现,第n行的数量比第n-1行多了一倍,并且前半部分是和第n-1行一样的,后半部分是前半部分"按位取反"得到的。

第n行的字符数量是2(n-1)个,因此第n-1行的数量就是2(n-2)个。公式为:

func(n,k) = func(n-1,k), if k <= 2^(n-2)
func(n,k)= ^func(n-1,k-2^(n-2)), if k >2^(n-2)

写了如下的代码:

class Solution {
public:
    int kthGrammar(int N, int K) {
        if(N == 1 || N == 0)  return 0;

        int tmp = 2^(N-2);//第n行有多少个数,有2的n-1个数,
        if(K <= tmp){
            return kthGrammar(N-1,K);
            return ~kthGrammar(N-1,K-tmp);//01互换
        }
    }
};

代码报错,问题在哪?

问题就在于,C++没有求幂的运算符,所以你用2^(N-2)是错误的。得到的结果还是2。
C++求幂只能用pow(x,y),C++中的^是按位异或运算符号。

使用pow(x,y)用math.h头文件。

还有什么问题?

如果第二种情况,求到的是0,就应该返回1,求到的是1就应该返回0.使用~表达为什么会错?

不能用~运算符来计算0和1,因为得到的并不是0和1的相反。实际用C++求的时候~0是-1,~1是-2.

参考 https://www.cnblogs.com/zhgyki/p/9452637.html

那要怎么办? 使用三目运算符。

如果返回的结果是0,就换为1,如果返回的结果是1,就返回0.

class Solution {
public:
    int kthGrammar(int N, int K) {
        if(N == 1 || N == 0)  return 0;
        int tmp = pow(2,N-2);
        if(K <= tmp){
            return kthGrammar(N-1,K);
            return kthGrammar(N-1,K-tmp)==1?0:1;
        }
    }
};

leetcode题解地址: https://leetcode-cn.com/problems/k-th-symbol-in-grammar/solution/zhi-jie-zhao-gui-lu-fa-by-gradius/

原文创作:goto2091

原文链接:https://www.cnblogs.com/goto2091/p/13761732.html

更多推荐

更多
这里什么都没有

近期文章

更多
文章目录

    推荐作者

    更多