cdhsiung
BAN USERStlll O(n^2). Greedy fashion might make it a bit faster.
#include <iostream>
#include <string>
using namespace std;
bool isWordLegal(string s) //test function assuming only "hello" is in the dict.
{
if (s == "hello")
return true;
else
return false;
}
int main() {
string s = "abcdefghelloijklmnop"; //test target string
for(int i = s.length(); i > 0; i--) //i: len of the substring, start with the full string
{
for(int j = 0; i + j <= s.length(); j ++) //j: start of the substring
{
string test = s.substr(j, i);
if(isWordLegal(test))
{
cout<<"Longest legal string: "<<test;
break;
}
}
}
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int MinNumInsersertionsForBalancing(const string& s)
{
int numberLeft = 0;
int numberToInsert = 0;
for(int i = 0; i < s.size(); i++)
{
if (s[i] == '(')
{
numberLeft ++;
numberToInsert ++;
}
else if (s[i] == ')')
{
if(numberLeft)
{
numberLeft--;
numberToInsert--;
}
else
{
numberToInsert++;
}
}
else
{
cout<<"Unexpected character:" <<s[i];
return -1;
}
}
return numberToInsert;
}
int main()
{
cout<<"Enter a string consisting of '(' and ')':";
string in;
cin>>in;
int ret = MinNumInsersertionsForBalancing(in);
if(ret >= 0)
cout<<endl<<ret<<" to print to make it well-formed.";
return 0;
}
Time O(n); space O(1).
Play with it: cpp.sh/2aso5
C++ solution in O(N)
#include <iostream>
#include <string>
using namespace std;
int main()
{
string in;
cout<<"Input a string:"<<endl;
cin>>in;
cout<<endl;
int arr[26];
for (int i = 0; i < 26 ; i++)
{
arr[i] = 0;
}
for (int i = 0; i < in.size(); i++)
{
unsigned char index = in[i] - 'a';
if(index < 0 || index > 25)
{
cout<<"error input";
return 1;
}
arr[index] = 1;
}
for (int i = 0; i < 26 ; i++)
{
if(arr[i] == 1)
{
cout<<(char) (i + 'a');
}
}
return 0;
}
Succinct C++ recursive version
#include <iostream>
int count = 0;
void findSubstring(char* target, char* space)
{
if(strlen(target) == 0) //all characters are found
count ++;
for (int i = 0; i < strlen (space) ; i++)
if (target[0] == space [i])
findSubstring(target + 1, space + i);
}
int main()
{
findSubstring("cat", "catapult");
std::cout<<count;
return 0;
}
Implement using C++11 unordered_map. O(N + MlogM), if N is the length of the stream and M is the number of distinct values.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class numocc{
public:
int num;
int occ;
};
bool comp(numocc a, numocc b)
{
return a.occ > b.occ;
}
void TopKFrequent(vector <int> v, int k) {
unordered_map <int, int> m;
for(int i = 0; i < v.size(); i ++) //O(N), N: size of input, if access to unordered_map is O(1)
{
m[v[i]]++;
}
unordered_map<int, int>::iterator it = m.begin();
vector <numocc> vn;
while(it != m.end()) //O(M), M distinct values
{
numocc tmp;
tmp.num = it->first;
tmp.occ = it->second;
vn.push_back(tmp);
it++;
}
sort(vn.begin(), vn.end(), comp); //O(MlogM)
for(int j = 0; j < k && j < vn.size(); j++)
{
cout<<vn[j].num<<"/"<<vn[j].occ<<endl;
}
}
int main()
{
vector <int> in = {1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6};
TopKFrequent(in, 3);
return 0;
}
This can be solved using greedy method with a max-heap.
- cdhsiung November 18, 20151. push all elements to a max-heap
2. pop one integer from the max-heap, if (number of elements to the right + number of elements in the other array) is still greater than k - 1, output the element to the result. Otherwise, pop another element (2nd largest)... repeatedly until the element is found. When the element is found, unused, greater elements have to be pushed back.
3. Update the start of the array to the location of the picked element + 1, k--, and then repeat 2... until the length of the result equals to K
2 and 3 are nested loop and overall it's = O(K(M+N)log(M+N))