資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告