Third Chapter
Stack && Queue
1 Valid Parentheses
https://leetcode.com/problems/valid-parentheses/
>
bool isValid(string s) {
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='('||s[i]=='{'||s[i]=='[') st.push(s[i]);
else if(s[i]==')'){
if(st.empty()||st.top()!='(') return false;
st.pop();
}else if(s[i]=='}'){
if(st.empty()||st.top()!='{') return false;
st.pop();
}else if(s[i]==']'){
if(st.empty()||st.top()!='[') return false;
st.pop();
}else continue;
}
return st.empty();
}
2 Implement Queue using Stacks
https://leetcode.com/problems/implement-queue-using-stacks/
>
class Queue {
public:
// Push element x to the back of queue.
void push(int x) {
input.push(x);
}
// Removes the element from in front of queue.
void pop(void) {
int top=peek();
output.pop();
}
// Get the front element.
int peek(void) {
if(output.empty()){
while(!input.empty()){
output.push(input.top());
input.pop();
}
}
return output.empty();
}
// Return whether the queue is empty.
bool empty(void) {
return input.empty()&&output.empty();
}
private:
stack<int> input,output;
};
3 Implement Stack using Queues
https://leetcode.com/problems/implement-stack-using-queues/
One Queue
>
class Stack {
public:
// Push element x onto stack.
void push(int x) {
input.push(x);
for(int i=0;i<input.size()-1;i++){
input.push(input.front());
input.pop();
}
}
// Removes the element on top of the stack.
void pop() {
input.pop();
}
// Get the top element.
int top() {
return input.front();
}
// Return whether the stack is empty.
bool empty() {
return input.empty();
}
private:
queue<int> input;
};
4 Min Stack
https://leetcode.com/problems/min-stack/
>
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
minE=INT_MAX;
}
void push(int x) {
st.push(x);
count[x]++;
if(x<minE) minE=x;
}
void pop() {
int t=st.top();
if(--count[t]==0){
if(t==minE){
minE=INT_MAX;
for(auto it:count) minE=min(minE,it.first);
}
}
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return minE;
}
private:
unordered_map<int,int> count;
int minE;
stack<int> st;
};
5 Verify Preorder Sequence in Binary Search Tree
>
bool verifyPreorder(vector<int> preorder){
return preorder(preorder,0,preorder.size()-1);
};
bool preorder(vector<int>& preorder,int left,int right){
if(left>right) return true;
int val=preorder[left];
int i=left+1;
for(;i<=right;i++) if(preorder[i]>val) break;
int j=i;
for(;j<=right;j++) if(preorder[i]<val) break;
if(j<=right) return false;
return preorder(preorder,left+1,i-1)&&preorder(preorder,i,right);
}
>
bool verifyPreorder(vector<int> preorder){
long low=INT_MIN-1;
stack<int> st;
for(auto p:preroder){
if(p<low) return false;
while(!st.empty()&&st.top()<p){
low=st.top();
st.pop();
}
st.push(p);
}
return true;
};
6 Binary Tree Inorder Traversal
https://leetcode.com/problems/binary-tree-inorder-traversal/
>
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode *cur=root,*temp;
while(cur){
st.push(cur);
cur=cur->left;
}
while(!st.emtpy()){
temp=st.top();
st.pop();
res.push_back(temp->val);
cur=temp->right;
while(cur){
st.push(cur);
cur=cur->left;
}
}
return res;
};
>
#include<iostream>
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root,res);
return res;
}
void traversal(TreeNode* root,vector<int>& res){
if(!root) return;
traversal(root->left,res);
res.push_back(root->val);
traversal(root->right,res);
return;
}
7 Binary Tree Zigzag Level Order Traversal
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
>
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > res;
if(!root) return res;
stack<TreeNode*> oldS,newS,emptyS;
int level=0;
TreeNode* temp;
oldS.push(root);
while(!oldS.empty()){
temp=oldS.top();
oldS.pop();
if(level==res.size()) res.push_back({});
res[level].push_back(temp->val);
if(level%2==0){
if(temp->left) newS.push(temp->left);
if(temp->right) newS.push(temp->right);
}else{
if(temp->right) newS.push(temp->right);
if(temp->left) newS.push(temp->left);
}
if(oldS.empty()){
level++;
oldS=newS;
newS=emptyS;
}
}
return res;
};
>
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > res;
traversal(root,0,res);
return res;
}
void traversal(TreeNode* root,int level,vector<vector<int> >& res){
if(!root) return;
if(level==res.size()) res.push_back({});
res[level].push_back(root->val);
traversal(root->right,level+1,res);
traversal(root->left,level+1,res);
return;
}
8 Binary Tree Preorder Traversal
https://leetcode.com/problems/binary-tree-preorder-traversal/
>
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> st;
TreeNode *temp;
st.push(root);
while(!st.empty()){
temp=st.top();
st.pop();
res.push_back(temp->val);
if(temp->right) st.push(temp->right);
if(temp->left) st.push(temp->left);
}
return res;
}
>
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root,res);
return res;
}
void traversal(TreeNode *root, vector<int>& res){
if(!root) return;
res.push_back(root->val);
traversal(root->left,res);
traversal(root->right,res);
}
9 Verify Preorder Serialization of a Binary Tree
https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
>
bool isValidSerialization(string preorder) {
stack<string> st;
string s="";
for(int i=0;i<preorder.size();i++){
if(isdigit(preorder[i])){
s.push_back(preorder[i]);
if(i==preorder.size()-1) st.push_back(s);
}else if(preorder[i]=='#'){
while(st.size()>1&&st.top()=="#"){
st.pop();
if(st.top()=="#") return false;
else st.pop();
}_
s.push_back(preorder[i]);
if(i==preorder.size()-1) st.push_back(s);
}else{
st.push_back(s);
s="";
}
}
return st.size()==1&&st.top()=="#";
}
10 Flatten Nested List Iterator
https://leetcode.com/problems/flatten-nested-list-iterator/
>
bool isValidSerialization(string preorder) {
stack<string> st;
string s="";
for(int i=0;i<preorder.size();i++){
if(isdigit(preorder[i])){
s.push_back(preorder[i]);
if(i==preorder.size()-1) st.push_back(s);
}else if(preorder[i]=='#'){
while(st.size()>1&&st.top()=="#"){
st.pop();
if(st.top()=="#") return false;
else st.pop();
}_
s.push_back(preorder[i]);
if(i==preorder.size()-1) st.push_back(s);
}else{
st.push_back(s);
s="";
}
}
return st.size()==1&&st.top()=="#";
}
11 Flatten Nested List Iterator
https://leetcode.com/problems/flatten-nested-list-iterator/
> /**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // 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;
*
* // 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 NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for(int i=nestedList.size()-1;i>=0;i--) st.push(nestedList[i]);
}
int next() {
NestedInteger temp=st.top();
st.pop();
return temp.getInteger();
}
bool hasNext() {
NestedInteger temp;
vector<NestedInteger> list;
while(!st.emtpy()){
temp=st.top();
if(temp.isInteger()) return true;
list=temp.getList();
st.pop();
for(int i=list.size()-1;i>=0;i--) st.push(list[i]);
}
return false;
}
private:
stack<NestedInteger> st;
};
12 Remove Duplicate Letters
https://leetcode.com/problems/binary-search-tree-iterator/
>
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
TreeNode *cur=root;
while(cur){
st.push(cur);
cur=cur->left;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !st.isEmpty();
}
/** @return the next smallest number */
int next() {
TreeNode *temp,*cur;
temp=st.top();
st.pop();
cur=temp->right;
while(cur){
st.push(cur);
cur=cur->left;
}
return temp->val;
}
private:
stack<TreeNode*> st;
};
13 Evaluate Reverse Polish Notation
https://leetcode.com/problems/evaluate-reverse-polish-notation/
>
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(int i=0;i<tokens.size();i++){
if((tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")&&st.size()>1){
int val2=st.top();
st.pop();
int val1=st.top();
st.pop();
if(tokens[i]=="+") st.push(val1+val2);
else if(tokens[i]=="-") st.push(val1-val2);
else if(tokens[i]=="*") st.push(val1*val2);
else if(tokens[i]=="/"){
if(val2==0) st.push(INT_MAX);
else st.push(val1/val2);
}
}else st.push(stoi(tokens[i]));
}
return st.empty()?INT_MAX:st.top();
}
**14** Maximal Rectangle
https://leetcode.com/problems/maximal-rectangle/
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size()==0||matrix[0].size()==0) return 0;
int m=matrix.size(),n=matrix[0].size();
int maxA=0;
vector<int> left(n,0),right(n,n),height(n,0);
for(int i=0;i<m;i++){
int curL=0,curR=n;
for(int j=0;j<n;j++){
if(matrix[i][j]=='1') height[j]++;
else height[j]=0;
}
for(int j=0;j<n;j++){
if(matrix[i][j]=='1') left[j]=max(left[j],curL);
else{
curL=j+1;
left[j]=0;
}
}
for(int j=n-1;j>=0;j--){
if(matrix[i][j]=='1') right[j]=min(right[j],curR);
else{
curR=j;
right[j]=n;
}
}
for(int j=0;j<n;j++){
maxA=max(maxA,height[j]*(right[j]-left[j]));
}
}
return maxA;
}
>
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.size()==0||matrix[0].size()==0) return 0;
int maxA=0;
int m=matrix.size(),n=matrix[0].size();
vector<int> heights(n+1,0);
for(int i=0;i<m;i++){
stack<int> st;
for(int j=0;j<n;j++){
if(matrix[i][j]=='1') heights[j]++;
else heights[j]=0;
}
for(int j=0;j<=n;j++){
if(st.empty()||heights[j]>=heights[st.top()]){
st.push(j);
}else{
int idx=st.top();
st.pop();
maxA=max(maxA,heights[idx]*(st.empty()?j:j-1-st.top()));
j--;
}
}
}
return maxA;
}
15 Largest Rectangle in Histogram
>
int largestRectangleArea(vector<int>& heights) {
int maxA=0;
stack<int> st;
heights.push_back(0);
for(int i=0;i<heights.size();i++){
if(st.empty()||heights[i]>=heights[st.top()]){
st.push(i);
}else{
int idx=st.top();
st.pop();
maxA=max(maxA,heights[idx]*(st.empty()?i:i-1-st.top()));
i--;
}
}
return maxA;
}
16 Binary Tree Postorder Traversal
https://leetcode.com/problems/binary-tree-postorder-traversal/
>
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> st;
TreeNode *cur=root,*temp;
while(cur){
st.push(cur);
cur=cur->left;
}
while(!st.empty()){
temp=st.top();
cur=temp->right;
if(cur){
while(cur){
st.push(cur);
cur=cur->left;
}
temp->right=NULL;
}else{
res.push(temp->val);
st.pop();
}
}
return res;
}
17 Basic Calculator
https://leetcode.com/problems/basic-calculator/
>
int calculate(string s) {
stack<int> st;
int res=0,sign=1,num=0;
for(int i=0;i<s.size();i++){
if(isdigit(s[i])){
num=num*10+s[i]-'0';
}else if(s[i]=='+'){
res+=sign*num;
num=0;
sign=1;
}else if(s[i]=='-'){
res+=sign*num;
num=0;
sign=-1;
}else if(s[i]=='('){
st.push(res);
st.push(sign);
res=0;
sign=1;
}else if(s[i]==')'){
res+=sign*num;
num=0;
res*=st.top();
st.pop();
res+=st.top();
st.pop();
}else continue;
}
if(num!=0) res+=sign*num;
return res;
}
18 Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/
>
int trap(vector<int>& height) {
int add=0,water=0;
stack<int> st;
for(int i=0;i<height.size();i++){
if(st.empty()||height[i]<=height[st.top()]){
st.push(i);
}else{
int idx=st.top();
st.pop();
add=st.empty()?0:(min(height[i],height[st.top()])-height[idx])*(i-1-st.top());
water+=add;
i--;
}
}
return water;
}
>
int trap(vector<int>& height) {
int add=0,water=0;
int i=0;
stack<int> st;
while(i<height.size()){
if(st.empty()||height[i]<=height[st.top()]){
st.push(i++);
}else{
int idx=st.top();
st.pop();
add=st.empty()?0:(min(height[i],height[st.top()])-height[idx])*(i-1-st.top());
water+=add;
}
}
return water;
}
>
int trap(vector<int>& height) {
int left=0,right=height.size()-1;
int water=0;
int maxL=0,maxR=0;
while(left<=right){
if(height[left]<height[right]){
if(height[left]<maxL) water+=maxL-height[left];
else maxL=height[left];
left++;
}else{
if(height[right]<maxR) water+maxR-height[right];
else maxR=height[right];
right--;
}
}
return water;
}
>
int trap(vector<int>& height) {
int water=0;
if(height.size()==0) return 0;
int i=0,j=height.size()-1,left=height[i],right=height[j];
while(i<j-1){
if(left<right){
water+=max(0,left-height[++i]);
left=max(left,height[i]);
}else{
water+=max(0,right-height[--j]);
right=max(right,height[j]);
}
}
return water;
}
19 Closest Binary Search Tree Value II
>
vector<int> closeatKValues(TreeNode* root, double target, int k){
vector<int> res;
if(!root) return res;
priority_queue<pair<double,int> > q;
stack<TreeNode*> st;
TreeNode *cur=root,*temp;
whiler(cur){
st.push(cur);
cur=cur->left;
}
while(!st.empty()){
temp=st.top();
st.pop();
cur=temp->right;
while(cur){
st.push(cur);
cur=cur->left;
}
q.push(make_pair(abs(temp->val-target),temp->val));
while(q.size()>k){
q.pop();
}
}
while(!q.empty()){
res.push_back(q.top().second);
q.pop();
}
return res;
}
20 Remove Duplicate Letters
https://leetcode.com/problems/remove-duplicate-letters/
>
string removeDuplicateLetters(string s) {
vector<int> count(26,0);
int idx=0;
string temp;
for(int i=0;i<s.size();i++) count[s[i]-'a']++;
for(int i=0;i<s.size();i++){
if(s[i]<s[idx]) idx=i;
if(--count[s[i]-'a']==0) break;
}
for(int i=idx+1;i<s.size();i++){
if(s[i]!=s[idx]) temp.push_back(s[i]);
}
return s.size()==0?"":s[i]+removeDuplicateLetters(temp);
}
>
string removeDuplicateLetters(string s) {
vector<int> count(26,0);
vector<bool> visited(26,false);
stack<char> st;
string res;
for(auto c: s) count[c-'a']++;
for(auto c:s){
int idx=c-'a';
count[idx]--;
if(visited[idx]) continue;
while(!st.emtpy()&&c<st.top()&&count[st.top()-'a']>0){
visited[st.top()-'a']=false;
st.pop();
}
st.push(c);
visited[idx]=true;
}
while(!st.empty()){
res.push_back(st.top());
st.pop();
}
reverse(res.begin(),res.end());
return res;
}
21 Moving Average from Data Stream
>
class MovingAverage {
public:
double next(int i){
queue.push(i);
sum+=i;
while(q.size()>k){
int t=q.front();
q.pop();
sum-=t;
}
return sum*1.0/q.size();
}
MovingAverage(int s){
k=s;
sum=0;
}
queue<int> q;
int k;
int sum;
};
22 Mini Parser
>
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){
NestedInteger cur;
if(s.empty()) return cur;
if(isdigit(s[0])||s[0]=='-'){
cur.setInteger(stoi(s));
return cur;
}
stack<NestedInteger> st;
int j=0;
for(int i=0;i<s.size();i++){
if(s[i]=='['){
if(i!=0) st.push(cur);
NestedInteger temp;
cur=temp;
j=i+1;
}else if(s[i]==']'){
string num=s.substr(j,i-j);
if(num.empty()) cur.add(stoi(num));
if(!st.empty()){
NestedInteger temp=st.top();
st.pop();
temp.add(cur);
cur=temp;
}
j=i+1;
}else if(s[i]==','){
if(s[i]!=']'){
string num=s.substr(j,i-j);
if(!num.empty()) cur.add(stoi(num));
}
j=i+1;
}
}
return cur;
}
};
23 Trapping Rain Water II
https://leetcode.com/problems/trapping-rain-water-ii/
>
struct cell{
int row;
int col;
int height;
cell(int r, int c, int h){
row=r;
col=c;
height=h;
}
};
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
if(heightMap.size()==0||heightMap[0].size()==0) return 0;
int water=0;
int m=heightMap.size(),n=heightMap[0].size();
vector<vector<bool> > visited(m,vector<bool>(n,false));
vector<pair<int,int> > dirs{{-1,0},{1,0},{0,-1},{0,1}};
auto cmp=[](cell left, cell right){return left.height>=right.height;};
priority_queue<cell,vector<cell>,decltype(cmp)> q(cmp);
for(int i=0;i<m;i++){
cell c1(i,0,heightMap[i][0]);
cell c2(i,n-1,heightMap[i][n-1]);
visited[i][0]=true;
visited[i][n-1]=true;
q.push(c1);
q.push(c2);
}
for(int j=0;j<n;j++){
cell c1(0,j,heightMap[0][j]);
cell c2(m-1,j,heightMap[m-1][j]);
visited[0][j]=true;
visited[m-1][j]=true;
q.push(c1);
q.push(c2);
}
while(!q.empty()){
cell temp=q.top();
q.pop();
for(auto dir:dirs){
int x=dir.first+temp.row,y=dir.second+temp.col;
if(x>=0&&x<m&&y>=0&&y<n&&!visited[x][y]){
visited[x][y]=true;
water+=max(0,temp.height-heightMap[x][y]);
cell c(x,y,max(temp.height,heightMap[x][y]));
q.push(c);
}
}
}
return water;
}
};