喜刷刷: stack

Showing posts with label stack. Show all posts

Thursday, November 27, 2014

[LeetCode] Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

思路：

Unix的path规则可以在这里了解：

http://en.wikipedia.org/wiki/Path_(computing)

归下类的话，有四种字符串：

1. "/"：为目录分隔符，用来分隔两个目录。

2. "."：当前目录

3. ".."：上层目录

4. 其他字符串：目录名

简化的核心是要找出所有的目录，并且如果遇到".."，需要删除上一个目录。

class Solution {
public:
    string simplifyPath(string path) {
        string ret, curDir;
        vector<string> allDir;
        
        path.push_back('/');
        for(int i=0; i<path.size(); i++) {
            if(path[i]=='/') {
                if(curDir.empty()) {
                    continue;
                }
                else if(curDir==".") {
                    curDir.clear();
                }
                else if(curDir=="..") {
                    if(!allDir.empty())
                        allDir.pop_back();
                    curDir.clear();
                }
                else {
                    allDir.push_back(curDir);
                    curDir.clear();
                }
            }
            else {
                curDir.push_back(path[i]);
            }
        }
        
        
        for(int i=0; i<allDir.size(); i++) 
            ret.append("/"+allDir[i]);
        if(ret.empty()) ret = "/";
        return ret;
    }
};

Wednesday, November 26, 2014

[LeetCode] Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

思路1：DP

求极值问题一般想到DP或Greedy，显然Greedy在这里不太适用，只有用DP了。

1. 状态：
DP[i]：以s[i-1]为结尾的longest valid parentheses substring的长度。

2. 通项公式：
s[i] = '('：
DP[i] = 0

s[i] = ')'：找i前一个字符的最长括号串DP[i]的前一个字符j = i-2-DP[i-1]
DP[i] = DP[i-1] + 2 + DP[j]，如果j >=0，且s[j] = '('
DP[i] = 0，如果j<0，或s[j] = ')'

......... ( x x x x )
j i-2 i-1

证明：不存在j' < j，且s[j' : i]为valid parentheses substring。
假如存在这样的j'，则s[j'+1 : i-1]也valid。那么对于i-1来说：
( x x x x x
j' j'+1 i-1
这种情况下，i-1是不可能有比S[j'+1 : i-1]更长的valid parentheses substring的。

3. 计算方向
显然自左向右，且DP[0] = 0

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), maxLen = 0;
        vector<int> dp(n+1,0);
        for(int i=1; i<=n; i++) {
            int j = i-2-dp[i-1];
            if(s[i-1]=='(' || j<0 || s[j]==')') 
                dp[i] = 0;
            else {
                dp[i] = dp[i-1]+2+dp[j];
                maxLen = max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
};

思路2：stack

括号题自然又想到了stack。仔细想下，这题目其实是Valid Parentheses的升级版。一个valid parentheses substring必然以'('开头以')'结尾，并且中间一定也是一个valid parentheses substring。这也意味着依照Valid Parentheses解法那样，用stack来存储没有配对的'('和')'，并用相应的')'来消去stack top的'('，最长substring的首尾必然会在这个过程中相消。

1. 由于我们需要知道它们之间的长度，所以stack里可以存储各个'('的坐标。
2. 为了能正确计算类似“ ) ( ) ( ) ”这种valid substring连接而组成的valid substring。我们必须也插入')'进stack，作为边界来计算长度。
3. 为了能在stack中区分左右括号，每个插入item定义为pair<int,int>。first为坐标，second表示左还是右括号。

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<pair<int,int>> stk;   // first: index, second: 0:'(', 1:')'
        int maxLen = 0, curLen = 0;
        for(int i=0; i<s.size(); i++) {
            if(s[i]=='(')   // left parenthesis
                stk.push(make_pair(i,0));
            else {          // right parenthesis
                if(stk.empty() || stk.top().second==1)
                    stk.push(make_pair(i,1));
                else {
                    stk.pop();
                    if(stk.empty())
                        curLen = i+1;
                    else
                        curLen = i-stk.top().first;    
                    maxLen = max(maxLen, curLen);
                }
            }
        }
        return maxLen;
    }
};

[LeetCode] 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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

思路1：Brute Force

对每个bar i，求它能构成的最大面积。用左右指针向两边扫，直到遇到比bar i矮的或遇到边界则停止，然后根据左右指针距离得到宽度和面积。但是这个解法过不了大集合，因为最坏情况：当整个histogram是递增或递减时，算法复杂度是O(n^2)。

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int maxArea = 0;
        for(int i=0; i<height.size(); i++) 
            maxArea = max(maxArea, calRecArea(height,i));
        return maxArea;
    }
    
    int calRecArea(vector<int> &height, int index) {
        int left = index-1, right = index+1;
        while(left>=0 && height[left]>=height[index]) 
            left--;
        while(right<height.size() && height[right]>=height[index])
            right++;
            
        return (right-left-1)*height[index];
    }
};

思路2：Stack

仔细考察Brute Force算法，发现问题在于指针重复扫描。以递增序列为例：

0 1 2 3 4 5 6

在计算s[0]的时候扫描了右边6个数，计算s[1]时继续扫描右边5个数，依次类推。而没能利用到这个序列的递增性质。当序列从i递增到j时，bar i~j的面积一定都能扩展到j。而一旦在j+1递减了，那么表示bar i~j中的部分bar k无法继续扩展，条件是h[k]>h[j+1]。

1. 利用这个性质，可以将递增序列cache在一个stack中，一旦遇到递减，则根据h[j+1]来依次从stack里pop出那些无法继续扩展的bar k，并计算面积。

2. 由于面积的计算需要同时知道高度和宽度，所以在stack中存储的是序列的坐标而不是高度。因为知道坐标后很容易就能知道高度，而反之则不行。

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        if(height.empty()) return 0;
        height.push_back(-1);
        height.insert(height.begin(),-1);
        stack<int> s;
        int maxArea = 0;
        
        for(int i=0; i<height.size(); i++) {
            while(!s.empty() && height[i]<=height[s.top()]) {
                int h = height[s.top()];
                s.pop();
                if(height[i]<h) maxArea = max(maxArea, (i-s.top()-1)*h);
            }
            s.push(i);
        }
        
        // reset height
        height.erase(height.begin());
        height.pop_back();
        return maxArea;
    }
};

Wednesday, November 19, 2014

[LeetCode] Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

思路：

括号匹配问题用stack解再合适不过。括号组合是否有效，主要看右括号。右括号的数量必须要等于相应的左括号。而左右括号之间也必须是有效的括号组合。

1. 当前括号是左括号时，压入stack。

2. 当前括号是右括号时，stack.top()如果不是对应的左括号，则为无效组合。否则，pop掉stack里的左括号。

3. 所有字符都判断处理过后，stack应为空，否则则无效。

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(int i=0; i<s.size(); i++) {
            if(isLeft(s[i])) {
                stk.push(s[i]);
            }
            else {
                if(stk.empty() || !isClose(stk.top(),s[i])) 
                    return false;
                stk.pop();
            }
        }
        return stk.empty();
    }
    
    bool isLeft(char a) {
        return (a=='(' || a=='{' || a=='[');
    }
    
    bool isClose(char a, char b) {
        if(a=='(') return b==')';
        if(a=='[') return b==']';
        if(a=='{') return b=='}';
        return false;
    }
};

[LeetCode] 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

思路：

典型的stack问题。逐一扫描每个token，如果是数字，则push入stack，如果是运算符，则从stack中pop出两个数字，进行运算，将结果push回stack。最后留在stack里的数即为最终结果。

以题中例子说明

exp: 2 1 + 3 *

stack: 2 2,1 3 3,3 9

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> s;
        for(int i=0; i<tokens.size(); i++) {
            if(isOp(tokens[i])) {
                int y = s.top();
                s.pop();
                int x = s.top();
                s.pop();
                s.push(evaluate(x, y, tokens[i]));
            }
            else {
                s.push(stoi(tokens[i], nullptr, 10));
                //s.push(atoi(tokens[i].c_str()));
            }
        }
        return s.top();
    }
    
    bool isOp(string s) {
        if(s=="+" || s=="-" || s=="*" || s=="/") return true;
        return false;
    }
    
    int evaluate(int x, int y, string op) {
        if(op=="+")
            return x+y;
        else if(op=="-")
            return x-y;
        else if(op=="*")
            return x*y;
        else if(op=="/")
            return x/y;
    }
};

总结：

1. 易犯的错误是将参与运算的两个数的顺序搞反。要计算 x op y，y是后压入的数，所以也是先被pop出来的数。第二次pop的时候才得到x的值。

2. 要注意stoi和atoi两个库函数的不同用法。

Tuesday, November 18, 2014

[LeetCode新题] Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

思路：

看到题目第一反应是用一个int minVal来记录整个stack当前的最小值就可以了。然后仔细想下，发现问题在于当这个最小值被pop以后，无法O(1)时间得到新的最小值。所以问题的关键在于要跟踪记录每个新数字压入栈时的当前最小值，而不是只记录一个总的最小值。

一种思路是将make_pair(xi, curMin)一起压入栈stack<pair<int,int>>中。但这种方法的空间复杂度为2n。再仔细观察，发现只有当push或pop的对象xi<= min(stack)时，才会影响到min(stack)的值。

用另一个stack<int> trackMin来记录min值的变化，trackMin.top()表示当前最小值。
当有新的xi<=trackMin.top()被压入时，将xi压入trackMin变为新的当前最小值。
当xi==trackMin.top()时被pop出时，trackMin也同时pop。

这里的一个关键是理解为什么是x<=trackMin.top()而不是x<trackMin.top()。加入对于push(x)只有当x<trackMin.top()时，才将x压入trackMin中。

例如压入以下数后：

xi: 3 2 1 2 1

trackMin: 3 2 1

此时如果pop，则变为
xi: 3 2 1 2
trackMin: 3 2

然而实际栈里的最小值仍旧为1，这个1因为重复数字的关系在trackMin中丢失。

class MinStack {
    stack<int> s;
    stack<int> trackMin;
public:
    void push(int x) {
        if(trackMin.empty() || x<=trackMin.top())
            trackMin.push(x);
        s.push(x);
    }

    void pop() {
        if(s.empty()) return;
        if(s.top()==trackMin.top())
            trackMin.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return trackMin.top();
    }
};

Sunday, November 16, 2014

[LeetCode] 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.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

思路1：stack解法

能积水的地方必然是一个中间低两边高的凹陷。所以寻找的目标是一个递减序列之后的递增。由于积水量只有在递增时才能计算，而计算又可能需要用到递减序列中的多个bar。因此必须将递减序列cache起来。这里使用stack。为了便于面积计算中宽度的计算，stack存放的不是递减序列bar的高度，而是每个bar的坐标。

class Solution {
public:
    int trap(int A[], int n) {
        if(n<3) return 0;
        stack<int> s;
        s.push(0);
        int water = 0;
        
        for(int i=1; i<n; i++) {
            if(A[i]>A[s.top()]) {
                int bottom = A[s.top()];
                s.pop();
                while(!s.empty() && A[i]>=A[s.top()]) {
                    water += (A[s.top()]-bottom)*(i-s.top()-1);
                    bottom = A[s.top()];
                    s.pop();
                }
                if(!s.empty()) water += (A[i]-bottom)*(i-s.top()-1);
            }
            s.push(i);
        }
        
        return water;
    }
};

思路2：two pointers解法

对任意位置i，在i上的积水，由左右两边最高的bar：A[left] = max{A[j], j<i}, A[right] = max{A[j], j>i}决定。定义Hmin = min(A[left], A[right])，则积水量Si为：

Hmin <= A[i]时，Si = 0
Hmin > A[i]时，Si = Hmin - A[i]

class Solution {
public:
    int trap(int A[], int n) {
        if(n<3) return 0;
        vector<int> leftHeight(n,0);
        vector<int> rightHeight(n,0);
        int water = 0;
        
        for(int i=1; i<n; i++) 
            leftHeight[i] = max(leftHeight[i-1], A[i-1]);
        
        for(int i=n-2; i>=0; i--) {
            rightHeight[i] = max(rightHeight[i+1], A[i+1]);
            int minHeight = min(leftHeight[i], rightHeight[i]);
            if(minHeight>A[i]) water += (minHeight - A[i]);
        }
        
        return water;
    }
};

Tuesday, November 11, 2014

[LeetCode] Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路：

Binary Tree Level Order Traversal那题的变种。一样的层序访问，区别仅仅在于访问是左向右，右向左交替进行。

1. 用两个stack来存储curLevel和nextLevel的节点可以实现这样的左右顺序反转。因为stack是先进后出的，节点push进stack的顺序和pop出stack的顺序正好是相反的：

假设stack curLevel pop出的第一个节点是该层的最左节点x，压入x->left和x->right进stack nextLevel。这样依次类推，等整个curLevel的节点都pop出来后，x->left和x->right在nextLevel的最底部。当之后开始pop nextLevel时，最后才pop到x->left和x->right。换句话说，curLevel第一个被访问到的节点的子节点，将在nextLevel中最后被访问到。

2. 这里还需注意的是push left/right child进nextLevel的顺序。当curLevel从左向右访问时，应当先push(x->left)再push(x->right)，反之则应该先push(x->right)再push(x->left)。实现时可以用一个bool变量left2right来表示顺序，每访问完一层后反转left2right的值。

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> levelNodeValues;
        if(!root) return levelNodeValues;
        
        stack<TreeNode*> *curLevel = new stack<TreeNode*>();
        stack<TreeNode*> *nextLevel = new stack<TreeNode*>();
        curLevel->push(root);
        bool left2right = true;
        
        while(!curLevel->empty()) {
            vector<int> curLevelValues;
            while(!curLevel->empty()) {
                TreeNode *cur = curLevel->top();
                curLevel->pop();
                curLevelValues.push_back(cur->val);
                
                if(left2right) {
                    if(cur->left) nextLevel->push(cur->left);
                    if(cur->right) nextLevel->push(cur->right);
                }
                else {
                    if(cur->right) nextLevel->push(cur->right);
                    if(cur->left) nextLevel->push(cur->left);
                }
            }
            levelNodeValues.push_back(curLevelValues);
            
            // swap curLevel and nextLevel, no need to clear since curLevel is already empty 
            stack<TreeNode*> *temp = curLevel;
            curLevel = nextLevel;
            nextLevel = temp;
            
            left2right  = !left2right;
        }
        
        return levelNodeValues;
    }
};

[LeetCode] Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

But the following is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

1. 递归解法：

这题看着很tricky，实际上本质思路算法和Same Tree那题换汤不换药。让我们来比较下两题。

T(p)和T(q)是same tree的条件：

(1) p和q等价（同时为NULL，或同时不为NULL且val相同）

(2) T(p->left)和T(q->left)为same tree，且T(p->right)和T(q->right)为same tree。

T(r)是symmetric的条件：实际就是判断T(r->left)和T(r-right)是否互为镜像的问题。假设p和q分别指向同一个tree内部两个镜像对称的节点，例如题目例子中的两个节点2

(1) p和q等价（同时为NULL，或同时不为NULL且val相同）

(2) T(p->left)和T(q->right)必须互为镜像，且T(p->right)和T(q->left)必须互为镜像。

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        return isSym(root, root);
    }
    
    bool isSym(TreeNode *lr, TreeNode *rr) {
        if(!lr && !rr) return true;
        if((!lr && rr) || (lr && !rr)) return false;
        if(lr==rr) return isSym(lr->left, lr->right); // lr and rr both point to root
        if(lr->val != rr->val) return false;
        return isSym(lr->left, rr->right) && isSym(lr->right, rr->left);
    }
};

总结：

ln 10有一个特殊处理，当lr和rr指向同一节点时，必然这个节点是整个树的root。此时避免重复判断，只要判断它的左和右子树是否互为镜像即可。

2. 迭代解法：

迭代解法本质上和递归解法是一回事，尽管理解上没有递归这么直观简洁。通常用stack或queue来暂时存放之后要处理的节点。这里由于要判断左右子树是否镜像，用两个queue分别对左右子树进行BFS的一层一层地访问。在访问中压入子节点到两个queue时，采用完全相反的顺序：对左子树先压入left child再right child；对右子树先压入right child再left child。这样一来将symmetric tree问题又转换为了same tree问题。

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if(!root) return true;
        queue<TreeNode*> ql, qr;
        ql.push(root->left);
        qr.push(root->right);
        
        while(!ql.empty() && !qr.empty()) {
            TreeNode *lnode = ql.front();
            TreeNode *rnode = qr.front();
            ql.pop();
            qr.pop();
            
            if(!lnode && !rnode) continue;
            if((!lnode && rnode) || (lnode && !rnode)) return false;
            if(lnode->val != rnode->val) return false;
            ql.push(lnode->left);
            qr.push(rnode->right);
            ql.push(lnode->right);
            qr.push(rnode->left);
        }
        
        if(!ql.empty() || !qr.empty()) return false;
        return true;
    }
};

总结：

ln 15 -17对应了递归解法的ln 8, 9 , 11。除了用queue外，也可用两个stack进行左右镜像的dfs访问。

Monday, November 10, 2014

[LeetCode] Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

1. 递归解法：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> allNodeValues;
        postorderTrav(root, allNodeValues);
        return allNodeValues;
    }
    
    void postorderTrav(TreeNode *root, vector<int> &allNodeValues) {
        if(!root) return;
        postorderTrav(root->left, allNodeValues);
        postorderTrav(root->right, allNodeValues);
        allNodeValues.push_back(root->val);
    }
};

2. 迭代解法：

[LeetCode] Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

1. 递归解法：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> allNodeValues;
        preorderTrav(root, allNodeValues);
        return allNodeValues;
    }
    
    void preorderTrav(TreeNode *root, vector<int> &allNodeValues) {
        if(!root) return;
        allNodeValues.push_back(root->val);
        preorderTrav(root->left, allNodeValues);
        preorderTrav(root->right, allNodeValues);
    }
};

2. 迭代解法：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> allNodeValues;
        TreeNode *cur = root;
        stack<TreeNode*> s;
        
        while(cur || !s.empty()) {
            if(!cur) {
                cur = s.top();
                s.pop();
            }
            allNodeValues.push_back(cur->val);
            if(cur->right) s.push(cur->right);
            cur = cur->left;
        }
        
        return allNodeValues;    
    }
};

[LeetCode] Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

1. 递归解法：

连题目都说recursive solution is trivial，没啥好说的，这解法两分钟写不出来就要被鄙视了。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> allNodeValues;
        inorderTrav(root, allNodeValues);
        return allNodeValues;
    }
    
    void inorderTrav(TreeNode *root, vector<int> &allNodeValues) {
        if(!root) return;
        inorderTrav(root->left, allNodeValues);
        allNodeValues.push_back(root->val);
        inorderTrav(root->right, allNodeValues);
    }
};

2. 迭代解法：

面试中应该不会只考递归这么简单。所以迭代解法才是真正的重点。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> allNodeValues;
        TreeNode *cur = root; 
        stack<TreeNode*> s;
        
        while(cur || !s.empty()) {
            if(!cur) {
                cur = s.top();
                s.pop();
                allNodeValues.push_back(cur->val);
                cur = cur->right;
            }
            else {
                s.push(cur);
                cur = cur->left;
            }
        }
        
        return allNodeValues;
    }
};