在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
广告