ในปัญหานี้ เราได้รับจำนวนบวก 1 หน้าที่ของเราคือค้นหาสตริงไบนารี Nth ในการเรียงลำดับ
เราจำเป็นต้องค้นหาสตริงที่ N ในรายการสตริงที่ไม่มีที่สิ้นสุดที่สร้างขึ้นโดยใช้เพียงสองสัญลักษณ์ a และ b ที่เรียงลำดับตามพจนานุกรม
รายการคือ −
a, b, aa, ab, ba, bb, aaa, aab, aba, …
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : N = 8 Output : aab
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการใช้ลูปเพื่อสร้างสตริง n ทั้งหมด แล้วส่งคืนสตริงที่ N วิธีนี้ใช้ได้ผลแต่ไม่สามารถให้วิธีแก้ปัญหาที่มีประสิทธิภาพในกรณีที่ N
ดังนั้นเราจะเห็นโซลูชันอื่นที่สามารถให้วิธีแก้ปัญหาได้ในเวลาอันสั้น
อีกวิธีในการแก้ปัญหาคือการใช้ดัชนีสัมพัทธ์สำหรับสตริง โดยใช้ข้อเท็จจริงที่ว่าจำนวนสตริงที่มีความยาว N สามารถสร้างได้โดยใช้สัญลักษณ์ 2 ตัวคือ 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
