在C++中查找排序后的第n个二进制字符串


在这个问题中,我们给定一个正数1。我们的任务是找到排序后的第N个二进制字符串。

我们需要在使用两个符号a和b创建的无限字符串列表中找到第N个字符串,这些字符串按字典序排序。

列表如下:

a, b, aa, ab, ba, bb, aaa, aab, aba, …

让我们来看一个例子来理解这个问题:

Input : N = 8
Output : aab

解决方案

解决这个问题的一个简单方法是使用循环生成所有n个字符串。然后返回第N个字符串。此解决方案可以完成工作,但在N值较大的情况下无法提供有效的解决方案。

因此,我们将看到另一种可以更快地提供解决方案的方法。

解决这个问题的另一种方法是使用字符串的相对索引。利用可以使用2个符号生成的长度为N的字符串数量为2N的事实。相对索引可用于查找*二进制形式*字符串。

          相对索引 = N + 1 - 2(floor(log(N+1)))

示例

程序说明了我们解决方案的工作原理

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
string findBinString(ll n){
   ll len = (int)log2(n + 1);
   int ri = n + 1 - pow(2, len);
   ll i = 0;
   string binString = "";
   for (i = 0; i < len; i++) {
      binString += 'a';
   }
   i = 0;
   while (ri > 0) {
      if (ri % 2 == 1)
         binString[i] = 'b';
      ri /= 2;
      i++;
   }
   reverse(binString.begin(), binString.end());
   return binString;
}
int main(){
   ll n = 245;
   cout<<"The "<<n<<"-th binary string in sorted order is "<<findBinString(n);
   return 0;
}

输出

The 245-th binary string in sorted order is bbbabba

更新于:2022年1月24日

99 次查看

启动您的职业生涯

通过完成课程获得认证

开始
广告