删除字符串中的所有相邻重复
返回原本的字符串
class Solution { public: string removeDuplicates(string s) { stack<char> stack_s; stack_s.push(1); stack_s.push(s[0]); for (int i = 1; i < s.size(); i++) { if (stack_s.top() != s[i]) { stack_s.push(s[i]); } else { stack_s.pop(); } } s.erase(0, s.size()); int num = stack_s.size()-1; for(int i= 0 ;i < num; i++) { s.insert(0,1,stack_s.top());//插入函数复杂度高，每一个点都执行浪费时间 stack_s.pop(); } return s; } };
返回另一个串
class Solution { public: string removeDuplicates(string s) { stack<char> stack_s; stack_s.push(1); stack_s.push(s[0]); for (int i = 1; i < s.size(); i++) { if (stack_s.top() != s[i]) { stack_s.push(s[i]); } else { stack_s.pop(); } } string result =""; int num = stack_s.size()-1; for(int i= 0 ; i < num; i++) { result += stack_s.top();//倒叙插入，然后反转 stack_s.pop(); } reverse (result.begin(), result.end());//反转一次，节省时间 return result; } };
二刷
class Solution { public: string removeDuplicates(string s) { stack<char> my_stack; my_stack.push(s[0]); for(int i=1 ;i<s.size();i++) { if(my_stack.empty() != 1 && s[i] == my_stack.top() ) my_stack.pop(); else my_stack.push(s[i]); } string result ; while(my_stack.empty() != 1) { result += my_stack.top(); my_stack.pop(); } reverse(result.begin(),result.end()); return result; } };
