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.

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

本题要对一个逆波兰表达式求值。简单题，借助一个堆栈，遇到数字压栈，遇到操作符，把栈顶两个元素弹栈并进行运算。需要注意的是，假设先后弹出来的两个元素是v1,v2，则后续的所有操作都应该是v2 op v1，不要搞错了。 完整代码如下：

class Solution {
public:
    int evalRPN(vector<string>& tokens)
    {
        stack<int> expression;
        for (size_t i = 0; i < tokens.size(); ++i) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int v1 = expression.top();
                expression.pop();
                int v2 = expression.top();
                expression.pop();
                if (tokens[i] == "+")
                    expression.push(v2 + v1);
                else if (tokens[i] == "-")
                    expression.push(v2 – v1);
                else if (tokens[i] == "*")
                    expression.push(v2 * v1);
                else if (tokens[i] == "/")
                    expression.push(v2 / v1);
            }
            else
                expression.push(atoi(tokens[i].c_str()));
        }
        return expression.top();
    }
};

本代码提交AC，用时9MS。

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

本题要求设计一个二叉搜索树的迭代器，迭代的输出当前树中最小值，并且要求next和hasNext是O(1)时间复杂度和O(h)空间复杂度，h为树的高度。 因为二叉搜索树的中序遍历是递增有序的序列，所以如果没有O(h)空间复杂度限制，则可以提前保存中序遍历结果，然后实现对数组的迭代器。但是这样的空间复杂度就是O(sizeof(tree))，不符合题意。 立马想到树的中序遍历的非递归实现，我们可以借助一个堆栈，先只把树的根和最左边的数压栈，这样栈顶元素就是树的最下角元素，也就是最小值。每调用一次next，返回当前栈顶元素，同时把栈顶元素的右孩子及右孩子的所有最左边的节点压栈。hasNext就好办，直接返回堆栈是否为空。 这样堆栈中最多会保存树高个数的节点，所以是O(h)的空间复杂度。完整代码如下：

class BSTIterator {
private:
    stack<TreeNode*> tree;
    void putAllLeft(TreeNode* root, stack<TreeNode*>& tree)
    {
        while (root != NULL) {
            tree.push(root);
            root = root->left;
        }
    }
public:
    BSTIterator(TreeNode* root) { putAllLeft(root, tree); } /** @return whether we have a next smallest number */
    bool hasNext() { return !tree.empty(); } /** @return the next smallest number */
    int next()
    {
        TreeNode* top = tree.top();
        tree.pop();
        putAllLeft(top->right, tree);
        return top->val;
    }
};

本代码提交AC，用时19MS。

LeetCode 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][/c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level.

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

Example 1:

Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Example 4:

Input: "/a/./b/../../c/"
Output: "/c"

Example 5:

Input: "/a/../../b/../c//.//"
Output: "/c"

Example 6:

Input: "/a//b////c/d//././/.."
Output: "/a/b/c"

简化Unix路径字符串。使用栈数据结构，扫描字符串，获取/之前的字符串，如果是一点.则保持当前路径，什么也不做；如果是两点..则弹栈，否则把字符串压栈。 需要注意的是/../，/.，/…等情况，三个点应该认为一个合法的路径字符串，虽然在Windows上并不合法。所以我们在进行算法之前，不管原始字符串末尾是否包含/，我们都在末尾添加上斜杠/，以便后续统一处理。 扫描完一次字符串之后，把栈内字符串依次弹出并组合成一个简化的路径。 完整代码如下：

class Solution {
public:
    string simplifyPath(string path)
    {
        path += "/";
        stack<string> sPath;
        string p1 = "";
        for (int i = 0; i < path.size(); i++) {
            if (path[i] == ‘/’) {
                if (p1 == "" || p1 == ".") {
                }
                else if (p1 == "..") {
                    if (!sPath.empty())
                        sPath.pop();
                }
                else {
                    sPath.push(p1);
                }
                p1 = "";
            }
            else
                p1 += path[i];
        }
        if (sPath.empty())
            return "/";
        string ans = "";
        while (!sPath.empty()) {
            ans = "/" + sPath.top() + ans;
            sPath.pop();
        }
        return ans;
    }
};

本代码提交AC，用时6MS。

二刷。更简洁代码：

class Solution {
public:
	string simplifyPath(string path) {
		stack<string> stk;
		int n = path.size();
		int i = 0, j = 0;
		while (i < n) {
			while (i < n&&path[i] == '/')++i;
			if (i >= n)break;
			j = i + 1;
			while (j < n&&path[j] != '/')++j;
			string name = path.substr(i, j - i);
			if (name == ".." && !stk.empty())stk.pop();
			if (name != "."&&name != "..")stk.push(name);
			i = j;
		}
		string ans = "";
		while (!stk.empty()) {
			ans = "/" + stk.top() + ans;
			stk.pop();
		}
		if (ans == "")return "/";
		else return ans;
	}
};

本代码提交AC，用时8MS。

20. Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

判断一个带括号的字符串是否合法，直接用栈，水题，代码如下。

class Solution {
public:
    bool isValid(string s)
    {
        stack<char> pars;
        for (int i = 0; i < s.size(); i++) {
            if (pars.empty()) {
                pars.push(s[i]);
                continue;
            }
            char t = pars.top();
            if ((t == ‘(‘&& s[i] == ‘)’) || (t == ‘{ ‘&& s[i] == ‘ }’) || (t == ‘[‘&& s[i] == ‘]’))
                pars.pop();
            else
                pars.push(s[i]);
        }
        return pars.empty();
    }
};

本代码提交AC，用时0MS。