資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中長度為 n 的所有快樂字串的第 k 個字典序字串
假設我們有一個字串。當它僅由 ['a', 'b', 'c'] 字母組成，並且對於從 1 到 s 長度 - 1 的所有 i 值，s[i] != s[i + 1]（這裡字串為 1 索引）時，我們將其稱為快樂字串。
因此，如果我們有兩個整數 n 和 k，請考慮按字典順序排序的所有長度為 n 的快樂字串的列表。我們必須找到該列表的第 k 個字串，或者如果長度為 n 的快樂字串少於 k 個，則返回空字串。
因此，如果輸入類似於 n = 3 和 k = 9，則輸出將為“cab”，有 12 個不同的快樂字串，它們是 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]，第 9 個是“cab”。
為了解決這個問題，我們將遵循以下步驟 -
定義一個數組 ret
定義一個函式 solve()，它將接收 s，l 並將其初始化為 1，
如果 l 與 x 相同，則 -
將 s 插入 ret 的末尾
返回
對於初始化 i := 0，當 i < 3 時，更新（將 i 增加 1），執行 -
如果 s 的最後一個元素不等於 c[i]，則 -
solve(s + c[i], l + 1)
從主方法中，執行以下操作 -
x := n
如果 n 與 0 相同，則 -
返回空字串
solve("a")
solve("b")
solve("c")
對陣列 ret 進行排序
返回（如果 k > ret 的大小，則返回空白字串，否則返回 ret[k - 1]）
示例
讓我們檢視以下實現以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
struct Cmp{
bool operator()(string& a, string& b) {
return !(a < b);
}
};
char c[3] = {'a', 'b', 'c'};
class Solution {
public:
vector<string> ret;
int x;
void solve(string s, int l = 1){
if (l == x) {
ret.push_back(s);
return;
}
for (int i = 0; i < 3; i++) {
if (s.back() != c[i]) {
solve(s + c[i], l + 1);
}
}
}
string getHappyString(int n, int k){
x = n;
if (n == 0)
return "";
solve("a");
solve("b");
solve("c");
sort(ret.begin(), ret.end());
return k > ret.size() ? "" : ret[k - 1];
}
};
main(){
Solution ob;
cout << (ob.getHappyString(3,9));
}輸入
3,9
輸出
cab
更新於: 2020-11-17
161 次檢視
廣告