Stack
42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
class Solution {
public:
int trap(vector<int>& height) {
size_t len = height.size();
if (!len) return 0;
stack<int> st;
int res = 0;
int cur_max = 0;
for (auto h : height) {
if (st.empty()) {
st.push(h);
cur_max = h;
} else if (h < cur_max) {
st.push(h);
} else {
while (!st.empty()) {
res += cur_max - st.top();
st.pop();
}
st.push(h);
cur_max = h;
}
}
if (st.empty()) return res;
int pre = st.top();
st.pop();
while (!st.empty()) {
if (st.top() < pre) res += pre - st.top();
else pre = st.top();
st.pop();
}
return res;
}
};
71. Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c"
class Solution {
public:
string simplifyPath(string path) {
istringstream iss(path);
string dir;
stack<string> st;
while (getline(iss, dir, '/')) {
if (dir == "." || dir == "") continue;
else if (dir == "..") {if (!st.empty()) st.pop();}
else st.push(dir);
}
if (st.empty()) return "/";
string res;
while (!st.empty()) {
res = "/" + st.top() + res;
st.pop();
}
return res;
}
};
84. Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int res = 0;
size_t len = height.size();
if (!len) return res;
stack<int> st;
int max_area = 0;
for (size_t i = 0; i <= len; ++i) {
int cur_len = i == len ? -1 : height[i];
while (!st.empty() && cur_len <= height[st.top()]) {
int cur_height = height[st.top()];
st.pop();
int cur_width = st.empty() ? i : i - st.top() - 1;
max_area = max(max_area, cur_height * cur_width);
}
st.push(i);
}
return max_area;
}
};
85. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
size_t m = matrix.size();
if (!m) return 0;
size_t n = matrix[0].size();
if (!n) return 0;
vector<int> height(n, 0);
int max_area = 0;
for (size_t i = 0; i < m; ++i) {
stack<int> st;
for (size_t j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
height[j]++;
} else {
height[j] = 0;
}
}
for (size_t j = 0; j <= n; ++j) {
int cur_h = j == n ? -1 : height[j];
while (!st.empty() && cur_h <= height[st.top()]) {
int h = height[st.top()];
st.pop();
int w = st.empty() ? j : j - st.top() - 1;
max_area = max(max_area, w * h);
}
st.push(j);
}
}
return max_area;
}
};
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.empty()) return 0;
const int m = matrix.size();
const int n = matrix[0].size();
int left[n], right[n], height[n];
fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
int maxA = 0;
for(int i=0; i<m; i++) {
int cur_left=0, cur_right=n;
for(int j=0; j<n; j++) { // compute height (can do this from either side)
if(matrix[i][j]=='1') height[j]++;
else height[j]=0;
}
for(int j=0; j<n; j++) { // compute left (from left to right)
if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
else {left[j]=0; cur_left=j+1;}
}
// compute right (from right to left)
for(int j=n-1; j>=0; j--) {
if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
else {right[j]=n; cur_right=j;}
}
// compute the area of rectangle (can do this from either side)
for(int j=0; j<n; j++)
maxA = max(maxA,(right[j]-left[j])*height[j]);
}
return maxA;
}
150. Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples: ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long> oprand;
int ret = 0;
for (auto str : tokens) {
if (str == "+") {
doCaculation(oprand, '+');
} else if (str == "-") {
doCaculation(oprand, '-');
} else if (str == "*") {
doCaculation(oprand, '*');
} else if (str == "/") {
doCaculation(oprand, '/');
} else {
oprand.push(stol(str));
}
}
if (oprand.size()) ret = oprand.top();
return ret;
}
long doCaculation(stack<long>& oprand, char op) {
if (oprand.size() < 2) throw("error");
auto op1 = oprand.top();
oprand.pop();
auto op2 = oprand.top();
oprand.pop();
switch (op) {
case '+':
oprand.push(op2 + op1);
break;
case '-':
oprand.push(op2 - op1);
break;
case '/':
if (op1 == 0) throw("divide by zero");
oprand.push(op2 / op1);
break;
case '*':
oprand.push(op2 * op1);
break;
default:
break;
}
return oprand.top();
}
};
224. Basic Calculator
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples: "1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23 Note: Do not use the eval built-in library function.
class Solution {
public:
int calculate(string s) {
// size_t pos = 0;
// return evaluate(s, pos);
stack<int> nums, op;
int sign = 1;
int res = 0;
int num = 0;
for (auto c : s) {
if (isdigit(c)) {
num = num * 10 + (c - '0');
} else {
res += num * sign;
num = 0;
if (c == '-') sign = -1;
else if (c == '+') sign = 1;
else if (c == '(') {
nums.push(res);
op.push(sign);
res = 0;
sign = 1;
} else if (c == ')' && !nums.empty()) {
res = nums.top() + res * op.top();
nums.pop();
op.pop();
}
}
}
res += num * sign;
return res;
}
// int evaluate(const string&s , size_t& i) {
// int res = 0;
// bool isPreNeg = false;
// while (i < s.size() && s[i] != ')') {
// if (s[i] == ' ' || s[i] == '+') {
// ++i;
// } else if (s[i] == '-') {
// isPreNeg = true;
// ++i;
// } else if (s[i] == '(') {
// ++i;
// res += isPreNeg ? -evaluate(s, i) : evaluate(s, i);
// isPreNeg = false;
// } else {
// size_t j = i + 1;
// while (j < s.size() && isdigit(s[j])) ++j;
// int num = stoi(s.substr(i, j - i));
// i = j;
// res += isPreNeg ? -num : num;
// isPreNeg = false;
// }
// }
// ++i;
// return res;
// }
};
227. Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples: "3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5Note: Do not use the eval built-in library function.
class Solution {
public:
int calculate(string s) {
istringstream iss(s);
int num = 0;
char oper = '+';
stack<int> oprands;
while (iss) {
iss >> num;
switch (oper) {
case '+': oprands.push(num); break;
case '-': oprands.push(-num);break;
case '*': {
int op1 = oprands.top();
oprands.pop();
oprands.push(op1 * num);
break;
}
case '/': {
int op1 = oprands.top();
oprands.pop();
oprands.push(op1 / num);
break;
}
}
if (iss) iss >> oper;
}
int res = 0;
while (!oprands.empty()) {
res += oprands.top();
oprands.pop();
}
return res;
}
};
316. Remove Duplicate Letters
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example: Given "bcabc" Return "abc"
Given "cbacdcbc" Return "acdb"
class Solution {
public:
string removeDuplicateLetters(string s) {
string res;
unordered_map<char, int> ch_cnt;
unordered_map<char, bool> visited;
stack<char> st;
for (auto c : s) {
ch_cnt[c]++;
visited[c] = false;
}
for (auto c : s) {
ch_cnt[c]--;
if (visited[c] || !st.empty() && st.top() == c) continue;
while (!st.empty() && st.top() > c && ch_cnt[st.top()]) {
visited[st.top()] = false;
st.pop();
}
visited[c] = true;
st.push(c);
}
while (!st.empty()) {
res = st.top() + res;
st.pop();
}
return res;
}
};
Using vector as stack:
class Solution {
public:
string removeDuplicateLetters(string s) {
string res;
res.push_back('\0');
vector<int> cnt(256);
vector<bool> added(256);
for (auto c : s) cnt[c]++;
for (auto c : s) {
cnt[c]--;
if (added[c]) continue;
while (cnt[res.back()] && res.back() > c) {
added[res.back()] = false;
res.pop_back();
}
res.push_back(c);
added[c] = true;
}
return res.substr(1);
}
};
385. Mini Parser
Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:
String is non-empty. String does not contain white spaces. String contains only digits 0-9, [, - ,, ]. Example 1:
Given s = "324", You should return a NestedInteger object which contains a single integer 324.Example 2:
Given s = "[123,[456,[789]]]",Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123. 2. A nested list containing two elements: i. An integer containing value 456. ii. A nested list with one element: a. An integer containing value 789.
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
NestedInteger deserialize(string s) {
int len = s.size(), i = 0;
stack<NestedInteger> st;
st.push(NestedInteger());
while (i < len) {
if (isdigit(s[i]) || s[i] == '-') {
int start = i;
while (i < len && (isdigit(s[i]) || s[i] == '-')) ++i;
int num = stoi(s.substr(start, i - start));
st.top().add(NestedInteger(num));
} else if (s[i] == ',') {
++i;
} else if (s[i] == '[') {
st.push(NestedInteger());
++i;
} else if (s[i] == ']') {
auto cur = st.top(); st.pop();
st.top().add(cur);
++i;
}
}
return st.top().getList().front();
}
};
388. Longest Absolute File Path
class Solution {
public:
int lengthLongestPath(string input) {
stack<int> st;
st.push(0);
istringstream iss(input);
string name;
int res = 0;
while (getline(iss, name, '\n')) {
int i = 0;
while (i < name.size() && name[i] == '\t') ++i;
while(st.size() > i+1) st.pop();
int len = st.top() + name.size() - i + 1;
st.push(len);
if (name.find('.') != string::npos) res = max(res, len-1);
}
return res;
}
};
394. Decode String
Given an encoded string, return it's decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
class Solution {
public:
string decodeString(string s) {
stack<int> count;
stack<string> res;
int i = 0;
res.push("");
while (i < s.size()) {
if (isdigit(s[i])) {
int start = i;
while (i < s.size() && isdigit(s[i])) ++i;
int num = stoi(s.substr(start, i - start));
count.push(num);
} else if (s[i] == '[') {
res.push("");
++i;
} else if (s[i] == ']') {
auto cur = res.top();
res.pop();
int cnt = count.top(); count.pop();
string str;
while (cnt--) str += cur;
res.top() += str;
++i;
} else {
res.top() += s[i++];
}
}
return res.top();
}
};
Trie Serialization
Serialize and deserialize a trie (prefix tree, search on internet for more details).
You can specify your own serialization algorithm, the online judge only cares about whether you can successfully deserialize the output from your own serialize function.
Example
str = serialize(old_trie)
>> str can be anything to represent a trie
new_trie = deserialize(str)
>> new_trie should have the same structure and values with old_trie
An example of test data: trie tree <a<b<e<>>c<>d<f<>>>>, denote the following structure:
root
/
a
/ | \
b c d
/ \
e f
/**
* Definition of TrieNode:
* class TrieNode {
* public:
* TrieNode() {}
* map<char, TrieNode*> children;
* };
*/
class Solution {
public:
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a trie which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
string serialize(TrieNode* root) {
// Write your code here
if (!root) return "";
string res;
for (auto kv : root->children) {
res += kv.first;
res += serialize(kv.second);
}
return "<"+res+">";
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it's given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
TrieNode* deserialize(string data) {
// Write your code here
TrieNode* root = new TrieNode();
stack<TrieNode*> st;
TrieNode* cur = root;
for (int i = 0; i < data.size(); ++i) {
if (data[i] == '<') {
st.push(cur);
} else if (data[i] == '>') {
st.pop();
} else {
cur = new TrieNode();
st.top()->children[data[i]] = cur;
}
}
return root;
}
};
Parse a Formula String
Parse a formula string (only contains “+-()”, no “*/“).
For example,5 + 2x – ( 3y + 2x - ( 7 – 2x) – 9 ) = 3 + 4y
Parse this string, with a given float of ‘x’ value, output a float for ‘y’ value.
double evaluate(const string& f, double x_val) {
double sum_y_left = 0, sum_y_right = 0;
double sum_num_left = 0, sum_num_right = 0;
double *cur_sum_y = &sum_y_left, *cur_sum_num = &sum_num_left;
int cur_sign = 1, pre_accumulated_sign = 1;
stack<int> stk;
for(int i = 0; i <= f.size(); ++i) {
char c = f[i];
if(f[i] >= '0' && f[i] <= '9') {
int over = i + 1;
while(f[over] >= '0' && f[over] <= '9') ++over;
double number = atoi(f.substr(i, over-i).c_str()) * cur_sign * pre_accumulated_sign;
if(f[over] == 'x') {
*cur_sum_num += number * x_val;
i = over;
} else if(f[over] == 'y') {
*cur_sum_y += number;
i = over;
} else {
*cur_sum_num += number;
i = over - 1;
}
} else if( c == 'x' ) {
*cur_sum_num += cur_sign * pre_accumulated_sign * x_val;
} else if( c == 'y' ){
*cur_sum_y += cur_sign * pre_accumulated_sign;
} else if( c == '(' ) {
stk.push(cur_sign);
pre_accumulated_sign *= cur_sign;
cur_sign = 1;
} else if( c == ')' ) {
pre_accumulated_sign /= stk.top();
stk.pop();
} else if( c == '+' || c == '-' ) {
cur_sign = c == '+' ? 1 : -1;
} else if( c == '=' || c == '\0' ) {
cur_sum_num = &sum_num_right;
cur_sum_y = &sum_y_right;
cur_sign = 1;
stk = stack<int>();
}
}
return (sum_num_right - sum_num_left) / (sum_y_left - sum_y_right);
}
}
Recover a Quack Data Structure
给一个Quack的类，里面有三个方法：
pop(): 随机从头或者尾扔出一个元素；
peek(): 随机看头或者尾的一个元素，peek()之后pop()的话一定会pop()出peek()的那个元素；
push(): 向尾部插入一个元素问题是：给一个排序好的Quack,怎么把里面的元素原封不动的放到一个Array里面。
Follow up：如果quack里面有重复的元素，怎么处理。
对于不重复元素的情况，用queue存小的数，stack存大的数，先pop()一个数，再peek一下，比较这两个数，如果pop的大，就代表肯定是quack的尾巴，反之肯定是头，然后插入queue或者stack就行了。这里假设quack有empty方法。
vector<int> recover_quack(quack& qk) {
queue<int> q;
stack<int> s;
while(!qk.empty()) {
int num1 = qk.pop();
if(qk.empty()) {
q.push(num1);
break;
}
int num2 = qk.peek();
if(num1 < num2) q.push(num1);
else s.push(num1);
}
vector<int> ret;
while(!q.empty()) {
ret.push_back(q.front());
q.pop();
}
while(!s.empty()) {
ret.push_back(s.top());
s.pop();
}
return ret;
}
对于有重复元素的情况，算法跟上面差不多，但是当遇到重复的时候，可以用一个hash_map记下来这个count，最后结算的时候补上去即可
vector<int> recover_quack(quack& qk) {
queue<int> q;
stack<int> s;
unordered_map<int,int> rep;
while(!qk.empty()) {
int num1 = qk.pop();
if(qk.empty()) {
q.push(num1);
break;
}
int num2 = qk.peek();
if(num1 < num2) q.push(num1);
else if(num1 > num2) s.push(num1);
else {
++rep[num1];
}
}
vector<int> ret;
while(!q.empty()) {
int num = q.front();
ret.push_back(num);
int count = rep[num];
while(count-- > 0) ret.push_back(num);
rep[num] = 0;
q.pop();
}
while(!s.empty()) {
int num = s.top();
ret.push_back(num);
int count = rep[num];
while(count-- > 1) ret.push_back(num);
rep[num] = 0;
s.pop();
}
return ret;
}