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

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

  • 第一行：0
  • 第二行：01
  • 第三行：0110
  • 第四行：01101001

为解决这个问题，我们将按照以下步骤进行 −

  • 假设方法的名称为 kthGrammar。这将接受 N 和 K。
  • 如果 N 为 1，则返回 0
  • 如果 k 为偶数，则当 then 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

更新日期：2020-05-04

933 次浏览

开启你的 职业生涯

完成课程以获得认证

立即开始
广告