問題描述比較簡單，舉個例子
input: 10100011
output: 110
我曾嘗試使用 BFS，但我認為這不是一個足夠有效的解決方案（也許是某種位圖 滑動視窗解決方案？）
string IntToString(int a)
{
ostringstream temp;
temp << a;
return temp.str();
}
bool is_subsequence(string& s, string& sub) {
if(sub.length() > s.length()) return false;
int pos = 0;
for(char c : sub)
{
pos = s.find(c, pos);
if(pos == string::npos) return false;
pos;
}
return true;
}
string shortestNotSubsequence(string& s) {
Queue q(16777216);
q.push(0);
q.push(1);
while(!q.empty())
{
string str;
int num = q.front; q.pop();
str = IntToString(num);
if(!is_subsequence(s, str)) return str;
string z = str '0';
string o = str '1';
q.push(stoi(str '0'));
q.push(stoi(str '1'));
}
return "";
}
int main() {
string N;
cin >> N;
cout << shortestNotSubsequence(N) << endl;
return 0;
}
uj5u.com熱心網友回復：
您可以在 O(N) 時間內輕松完成此操作。
設 W = 天花板(log 2 (N 1))，其中 N 是輸入字串 S 的長度。
有 2 W 個長度為W 的可能字串。 S 必須有少于 N 個作為子字串，并且小于 2 W，因此至少一個長度為 W 的字串不能出現在 S 中。
W 也小于 a 中的位數size_t，并且只需要 O(N) 空間來存盤長度為 W 的所有可能字串的掩碼。將這樣的掩碼初始化為 0，然后使用最低的 W 位迭代 S在 asize_t作為您遇到的子字串的滑動視窗。將遇到的每個子字串的掩碼位設定為 1。
完成后，掃描掩碼以找到第一個 0，這將是缺少的長度為 W 的字串。
但是，也可能有更短的缺失字串，因此將掩碼位成對合并以制作長度為 W-1 的字串的掩碼，然后還為 S 中的最后 W-1 位設定掩碼位，因為那些可能不包含在任何 W 長度的字串中。然后掃描0s的掩碼，看看是否可以找到更短的缺失字串。
只要您不斷找到較短的字串，就繼續合并較小字串的掩碼，直到長度為 1。由于每個此類操作將掩碼大小除以 2，因此不會影響整個演算法的整體 O(N) 時間.
這是在 C 中的實作
#include <string>
#include <vector>
#include <algorithm>
std::string shortestMissingBinaryString(const std::string instr) {
const size_t len = instr.size();
if (len < 2) {
if (!len || instr[0] != '0') {
return std::string("0");
}
return std::string("1");
}
// Find a string size guaranteed to be missing
size_t W_mask = 0x3;
unsigned W = 2;
while(W_mask < len) {
W_mask |= W_mask<<1;
W =1;
}
// Make a mask of all the W-length substrings that are present
std::vector<bool> mask(W_mask 1, false);
size_t lastSubstr=0;
for (size_t i=0; i<len; i) {
lastSubstr = (lastSubstr<<1) & W_mask;
if (instr[i] != '0') {
lastSubstr |= 1;
}
if (i 1 >= W) {
mask[lastSubstr] = true;
}
}
//Find missing substring of length W
size_t found = std::find(mask.begin(), mask.end(), false) - mask.begin();
// try to find a shorter missing substring
while(W > 1) {
unsigned testW = W - 1;
W_mask >>= 1;
// calculate masks for length testW
for (size_t i=0; i<=W_mask; i ) {
mask[i] = mask[i*2] || mask[i*2 1];
}
mask.resize(W_mask 1);
// don't forget the missing substring at the end
mask[lastSubstr & W_mask] = true;
size_t newFound = std::find(mask.begin(), mask.end(), false) - mask.begin();
if (newFound > W_mask) {
// no shorter string
break;
}
W = testW;
found = newFound;
}
// build the output string
std::string ret;
for (size_t bit = ((size_t)1) << (W-1); bit; bit>>=1) {
ret.push_back((found & bit) ? '1': '0');
}
return ret;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/373422.html