mt
BAN USERonly two chars in a string for example, we want to find whether "ab" is repeat
if the index of last "b" is after the index of 2nd "a" and the index of second last is after the index of 1st "a", "ab" is repeated.
We can enumerate every different two-chars-string.
Time complexity O(N)
Memory O(N)
boolean containRepeatString(string s){
vector<int> pos[26];
for (int i = 0; i < s.length; i++){
pos[s[i]-'a'].push_back(i);
}
for (char firstChar = 'a' ; firstChar <= 'z'; firstChar ++){
for (char secondChar = 'a'; secondChar <= 'z'; secondChar ++){
if (firstChar == secondChar) {
if (pos[firstChar].size() >= 4) cout << firstChar << secondChar << endl;
}
else{
if (pos[firstChar].size() >= 2 && pos[secondChar].size()>= 2){
if (pos[secondChar][pos[secondChar].size()-1] > pos[firstChar][1] && pos[secondChar][pos[secondChar].size()-2] > pos[firstChar][0]) {
cout << firstChar << secondChar << endl;
}
}
}
}
}
}
use a dfs, dfs(now, father)
start from the root node, and go to the left until the end. assign father node's right son to the node now's brother pointer .
dfs(node *now,node *father){
if (now == null) return;
if (father == null) dfs(now->left, now);
else {
now->brother = father->right;
dfs(now->left, now);
}
}
dfs(root, null);
RepJeanSwest, Data Engineer at Achieve Internet
I am a nuclear power reactor operator who is responsible for the flow of energy at a power plant. I ...
Repneilsjohn4563, Android Engineer at ABC TECH SUPPORT
Hello, I am a multimedia artist. I have 4 years experience in this.A multimedia Artist is someone who is ...
RepMyraGreen, Accountant at 8x8
I am a dedicated secretary with 2 years of experience excited to join MCL to become a key player in ...
a double linked list should have these operation
- mt October 30, 2014go_pre
go_next
insert
delete
so we can use two stack to simulate a double linked list
stack1 store the data before the pointer now ,stack2 store the data after the pointer.
insert : push this element to s1
delete: pop element from s1
go_pre operation we can pop the top element from s1, and push to s2.
go_next : pop the element from s2 and push to s1.
this is the basic solution every operation is O(1)
these is some specific part need to be pay attention to.