C ++语法中的第K个符号

假设在第一行上，我们有一个0。现在，在每一行中，我们查看前一行，并将每个出现的0替换为01，并将每个出现的1替换为10。假设我们有N行，索引为K，必须在第N行中找到第K个索引符号。（K的值是1索引。）（1索引）。因此，如果N = 4且K = 5，则输出将为1。这是因为-

• 第1行：0

• 第2行：01

• 第3列：0110

• 第4列：01101001

为了解决这个问题，我们将遵循以下步骤-

• 假设方法的名称是kthGrammar。这需要N和K。

• 如果N为1，则返回0

• 如果k为偶数，则当kthGrammar（N – 1，K / 2）为0时返回1，否则为0

• 否则返回kthGrammar（N – 1，（K + 1）/ 2）

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int kthGrammar(int N, int K) {
      if(N == 1) return 0;
      if(K % 2 == 0){
      return kthGrammar(N - 1, K / 2) == 0 ? 1 : 0;
      }else{
         return kthGrammar(N - 1, (K + 1) / 2);
      }
   }
};
main(){
   Solution ob;
   cout << (ob.kthGrammar(4, 5));
}

输入值

4
5

输出结果

1