数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在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 次查看
广告