fiska
BAN USERAn efficient solution in C++, does not need Regex nor extra space!
#include <iostream>
#include <vector>
#include <string>
void
getCCPatterns(std::vector<std::string>& A, std::string& P) {
for(int i = 0; i < A.size(); ++i) {
std::string E = A[i];
int c = 0;
for(int j = 0; j < E.size() && c < P.size(); ++j) {
if(islower(P[c]) && P[c] != E[j]) break;
if(E[j] == P[c]) c++;
}
if(c == P.length()) std::cout << E << std::endl;
}
}
int main() {
std::vector<std::string> A = {"HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"};
std::string P = "HeWorM";
getCCPatterns(A, P);
return 0;
}
Since the encoder was provided by many, here is the decoder in C++, running time: O(N).
void
decoder(std::string A) {
int x = 0;
for(int i = 0; i<A.size(); ++i) {
while(A[i] >= '0' && A[i] <= '9') {
x = x*10 + (A[i] - '0');
i++;
}
if(x>0 && A[i] == 'x') {
i++;
for(int j = 0; j < x; ++j) {
std::cout<< A[i];
}
x = 0;
} else if(x>0 && A[i] != 'x') {
std::cout<< x << A[i];
x = 0;
} else {
std::cout<< A[i];
}
}
std::cout<<std::endl;
}
Output:
p14a8xkpq => p14akkkkkkkkpq
abc11kresf10xAddd => abc11kresfAAAAAAAAAAddd
#include <iostream>
#include <vector>
#include <set>
#include <string>
typedef unsigned int uint;
std::vector<uint> E = { 1,2,3,4 };
std::set<std::string> S;
inline bool test(uint A, uint pos) {
return (A & (1u << pos));
}
void construct(uint A, uint N) {
bool conjunctive_1 = false;
bool conjunctive_0 = false;
std::string str;
for(uint i = 0; i < N; i++) {
if(test(A, i)) {
if(conjunctive_0) {
str += ')';
conjunctive_0 = false;
}
if(!conjunctive_1) {
str += '(';
str += E[i] + '0';
conjunctive_1 = true;
} else {
str += E[i] + '0';
}
} else {
if(conjunctive_1) {
str += ')';
conjunctive_1 = false;
}
if(!conjunctive_0) {
str += '(';
str += E[i] + '0';
conjunctive_0 = true;
} else {
str += E[i] + '0';
}
}
}
str += ')';
if(!S.count(str)) {
S.emplace(str);
}
}
void brackets(uint N) {
for(uint i = 0; i < (1u << N)-1; i++) {
construct(i, N);
}
for(auto& a : S)
std::cout << a << std::endl;
}
int main() {
brackets(E.size());
return 0;
}
Solution in C++
#include <iostream>
#include <vector>
typedef std::vector<int> vec_t;
int
findMax(vec_t& aVec) {
int lMax = 0;
for(int i = 0; i < aVec.size(); ++i)
if (aVec[i] > lMax) lMax = aVec[i];
return lMax;
}
void
print(vec_t& aVec) {
for(auto& a : aVec)
std::cout << a << ' ';
std::cout << std::endl;
}
int
maxZigZag(vec_t& aVec) {
vec_t pos(aVec.size(),1);
vec_t neg(aVec.size(),1);
for(int i = 1; i < aVec.size(); ++i) {
for(int j = 0; j <= i-1; ++j) {
if(aVec[i] - aVec[j] > 0) {
pos[i] = std::max(neg[j]+1, pos[i]);
} else if (aVec[i] - aVec[j] < 0) {
neg[i] = std::max(pos[j]+1, neg[i]);
}
}
}
int l1 = findMax(pos);
int l2 = findMax(neg);
/* print(pos); print(neg); */
return std::max(l1, l2);
}
A simple solution in C++
#include <iostream>
#include <vector>
int bitcount(int aArg) {
int c = 0; // bit count
for(; aArg; c++)
aArg &= aArg -1; // clears the least significat bit
return c;
}
void printBitCombinations(int K) {
std::vector<int> A;
for(int i = 0; i <= K; ++i) {
for(int j = 0; j < 1 << K; ++j) {
if(bitcount(j) == i)
A.push_back(j);
}
}
for(auto& a : A) {
std::cout << a << std::endl;
}
}
int
main() {
printBitCombinations(4);
return 0;
}
- fiska July 23, 2016