1,Valid Parentheses
1 bool isVaild1(string& s) { // 直接列举,不易扩展 2 stack<char> stk; 3 for (int i = 0; i < s.length(); ++i) { 4 if (stk.empty()) 5 stk.push(s[i]); 6 else { 7 char top = stk.top(); 8 if (top == '(' && s[i] == ')' || top == '{' && s[i] == '}' || top == '[' && s[i] == ']') 9 stk.pop(); 10 } 11 } 12 if (stk.empty()) 13 return true; 14 else 15 return false; 16 } 17 18 bool isValid2(string& s) { 19 string left = "([{"; 20 string right = ")]}"; 21 stack<char> stk; 22 23 for (auto c = s.begin(); c != s.end(); ++c) { 24 if (left.find(*c) != string::npos) 25 stk.push(*c); 26 else { 27 if (stk.empty() || stk.top() != left[right.find(*c)]) 28 return false; 29 else 30 stk.pop(); 31 } 32 } 33 return stk.empty(); 34 }isVaild
2,Longest Valid Parentheses
1 int longestValidParentheses(const string& s) { 2 int len = 0; 3 stack<char> stk; 4 5 for (size_t i = 0; i < s.size(); ++i) { 6 if (stk.empty()) 7 stk.push(s[i]); 8 else { 9 if (stk.top() == '(' && s[i] == ')') { 10 stk.pop(); 11 ++len; 12 } 13 else 14 stk.push(s[i]); 15 } 16 } 17 return 2 * len; 18 }longestValidParentheses
3,Largest Rectangle in Histogram
1 int longestRectangleArea1(vector<int>& heights) { // 暴力求解 2 if (heights.size() == 0) return 0; 3 int result = 0; 4 for (int i = 0; i < heights.size(); ++i) { 5 int minHeight = heights[i]; 6 if (i == heights.size() - 1 || heights[i]>heights[i + 1]) { // 简单优化 7 for (int j = i; j >= 0; --j) { 8 minHeight = min(minHeight,heights[j]); 9 result = max((i - j + 1)*minHeight, result); 10 } 11 } 12 } 13 return result; 14 } 15 16 int longestRectangleArea2(vector<int>& heights) { // 用 stack实现,未看懂 17 stack<int> s; 18 heights.push_back(0); 19 int result = 0; 20 for (int i = 0; i < heights.size();) { 21 if (s.empty() || heights[i] > heights[s.top()]) 22 s.push(i++); 23 else { 24 int temp = s.top(); 25 s.pop(); 26 result = max(result, heights[temp] * (s.empty() ? i : i - s.top() - 1)); 27 } 28 } 29 return result; 30 31 }longestRectangleArea
4,Evaluate Reverse Polish Notation
1 int evalRPN(vector<string>& tokens) { 2 stack<int> stk; 3 string options = "+-*/"; 4 for (int i = 0; i < tokens.size(); ++i) { 5 if (options.find(tokens[i]) == string::npos) // 不是运算符 6 stk.push(atoi(tokens[i].c_str())); 7 else { 8 int num1 = stk.top(); 9 stk.pop(); 10 int num2 = stk.top(); 11 stk.pop(); 12 13 if (tokens[i] == "+") stk.push(num1 + num2); 14 else if (tokens[i] == "-") stk.push(num1 - num2); 15 else if (tokens[i] == "*") stk.push(num1 * num2); 16 else stk.push(num1 / num2); 17 } 18 } 19 return stk.top(); 20 }evalRPN
以上题目来源于:https://github.com/soulmachine/leetcode(leetcode-cpp.pdf)