資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學檢查二進位制字串在 C++ 中是否包含所有長度為 k 的排列
假設我們有一個二進位制字串，另外一個整數 k。我們必須檢查字串是否包含 k 位二進位制的所有排列。假設一個字串類似於 “11001”，如果 K = 2，則它必須具有 k 位數字的所有排列。(00, 01, 10, 11)，給定的字串具有所有排列。因此，這是有效的字串。
透過獲取二進位制字串和 k 的值，我們必須檢查二進位制序列是否匹配。二進位制序列的大小為 k。因此，將有 2k 個不同的二進位制排列。我們將在列表中將所有 k 長度二進位制值的排列儲存為字串，然後比較列表中存在的所有元素作為給定字串的子集。如果我們對列表中存在的所有字串都得到 True，則字串有效，否則無效。
示例
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<string> binaryPermutations(int k){
vector<string> list;
int n = 0;
string bin_str = "";
for(int i = 0; i<k; i++){
bin_str += "0";
}
int limit = pow(2, k);
list.push_back(bin_str);
for(int i=1; i<limit; i++){
int j = 0;
while(j <= k){
if(bin_str[k-1-j] == '0'){
bin_str[k - 1 - j] = '1';
break;
} else {
bin_str[k - 1 - j] = '0';
j++;
}
}
list.push_back(bin_str);
}
return list;
}
bool hasAllPermutation(string str, int k){
vector<string> list = binaryPermutations(k);
for(int i = 0; i<list.size(); i++){
string substr = list[i];
std::size_t found = str.find(substr);
if(found == std::string::npos){
return false;
}
}
return true;
}
int main() {
int k = 2;
string str = "11001";
if(hasAllPermutation(str, k)){
cout << "Has All Permutations";
} else {
cout << "Not All Permutations are found";
}
}輸出
Has All Permutations
更新於:22-Oct-2019
103 次瀏覽
廣告