/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param nodes a array of directed graph node
     * @return a connected set of a directed graph
     */
    int find(unordered_map<int, int> &father, int x) {
        if (father.find(x) == father.end()) {
            father[x] = x;
            return x;
        }
        while (x != father[x]) x = father[x];
        return x;
    }
    vector<vector<int>> connectedSet2(vector<DirectedGraphNode*>& nodes) {
        // Write your code here
        unordered_map<int, int> father;
        int fa, fb, fn;
        for (auto &n : nodes) {
            for (auto &nn : n->neighbors) {
                fa = find(father, n->label);
                fb = find(father, nn->label);
                if (fa != fb) {
                    if (fa > fb) father[fa] = fb;
                    else father[fb] = fa;
                }
            }
        }
        unordered_map<int, vector<int>> comp;
        for (auto &n : nodes) {
            fn = find(father, n->label);
            comp[fn].push_back(n->label);
        }
        vector<vector<int>> res;
        for (auto &c : comp) {
            sort(c.second.begin(), c.second.end());
            res.push_back(c.second);
        }
        return res;
    }
};

class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0) return false;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
};

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 1) return 1;
        vector<int> result(n);
        result[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0;
        for (int i = 1; i < n; i++) {
            result[i] = min(result[t2] * 2, min(result[t3] * 3, result[t5] * 5));
            if (result[i] == result[t2] * 2) {
                t2 ++;
            }
            if (result[i] == result[t3] * 3) {
                t3 ++;
            }
            if (result[i] == result[t5] * 5) {
                t5 ++;
            }
        }
        return result[n - 1];
    }
};

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> count(primes.size(), 0);
        vector<int> result;
        result.push_back(1);
        while (result.size() < n) {
            int next = INT_MAX;
            for (int i = 0; i < primes.size(); i ++) {
                next = min(next, primes[i] * result[count[i]]);
            }
            for (int i = 0; i < primes.size(); i ++) {
                if (next == primes[i] * result[count[i]])  count[i] ++;
            }
            result.push_back(next);
        }
        return result[n - 1];
     }
};

class Solution2 {
public:
    /**
     * @param expression: a vector of strings;
     * @return: an integer
     */
    int evaluateExpression(vector<string> &expression) {
        if (expression.empty()) {
            return 0;
        }
        vector<string> postfix;
        infixToPostfix(expression, postfix);
        return evaluatePostfixExpression(postfix);
    }

    // Evaluate Postfix Expression.
    int evaluatePostfixExpression(const vector<string> &postfix) {
        if (postfix.empty()) {
            return 0;
        }
        stack<string> s;
        for (const auto& tok : postfix) {
            if (!is_operator(tok)) {
                s.emplace(tok);
            } else {
                int y = stoi(s.top());
                s.pop();
                int x = stoi(s.top());
                s.pop();
                if (tok[0] == '+') {
                    x += y;
                } else if (tok[0] == '-') {
                    x -= y;
                } else if (tok[0] == '*') {
                    x *= y;
                } else {
                    x /= y;
                }
                s.emplace(to_string(x));
            }
        }
        return stoi(s.top());
    }

    bool is_operator(const string &op) {
        return op.length() == 1 && string("+-*/").find(op) != string::npos;
    }

    // Convert Infix to Postfix Expression.
    void infixToPostfix(vector<string>& infix, vector<string>& postfix) {
        stack<string> s;
        for (auto tok : infix) {
            // Any number would be pushed into stack.
            if (atoi(tok.c_str())) {
                postfix.emplace_back(tok);
            } else if (tok == "(") {
                s.emplace(tok);
            } else if (tok == ")") {
                // Meet ")", then pop until "(".
                while (!s.empty()) {
                    tok = s.top();
                    s.pop();
                    if (tok == "(") {
                        break;
                    }
                    postfix.emplace_back(tok);
                }
            } else {
                // Order of tokens in stack should be like "(-*",
                // The token will be added in an strictly increasing precedence order.
                while (!s.empty() && precedence(tok) <= precedence(s.top())) {
                    postfix.emplace_back(s.top());
                    s.pop();
                }
                s.emplace(tok);
            }
        }
        // Pop the remaining token and add them to the postfix.
        while (!s.empty()) {
            postfix.emplace_back(s.top());
            s.pop();
        }
    }

    int precedence(string x) {
        if (x == "(") {  // The least precedence.
            return 0;
        } else if (x == "+" || x == "-") {
            return 1;
        } else if (x == "*" || x == "/") {
            return 2;
        }
        return 3;
    }
};

class Solution {
public:
    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */
    ExpressionTreeNode* build(vector<string> &expression) {
        if (expression.empty()) {
            return 0;
        }
        vector<string> prefix;
        infixToPrefix(expression, prefix);
        int start = 0;
        return buildExpressionTree(prefix, start);
    }

    // Build expression tree by prefix expression.
    ExpressionTreeNode* buildExpressionTree(vector<string>& prefix, int& start) {
        if (prefix.empty()) {
            return nullptr;
        }
        ExpressionTreeNode *node = new ExpressionTreeNode(prefix[start++]);
        if (is_operator(prefix[start - 1])) {
            node->left = buildExpressionTree(prefix, start);
            node->right = buildExpressionTree(prefix, start);
        }
        return node;
    }

    bool is_operator(const string &op) {
        return op.length() == 1 && string("+-*/").find(op) != string::npos;
    }

    // Convert Infix to Prefix Expression.
    void infixToPrefix(vector<string>& infix, vector<string>& prefix) {
        reverse(infix.begin(), infix.end());
        stack<string> s;
        for (auto& tok : infix) {
            if (atoi(tok.c_str())) {
                prefix.emplace_back(tok);
            } else if (tok == ")") {
                s.emplace(tok);
            } else if (tok == "(") {
                while (!s.empty()) {
                    tok = s.top();
                    s.pop();
                    if (tok == ")") {
                        break;
                    }
                    prefix.emplace_back(tok);
                }
            } else {
                while (!s.empty() && precedence(tok) < precedence(s.top())) {
                    prefix.emplace_back(s.top());
                    s.pop();
                }
                s.emplace(tok);
            }
        }
        while (!s.empty()) {
            prefix.emplace_back(s.top());
            s.pop();
        }
        reverse(prefix.begin(), prefix.end());
    }

    int precedence(string x) {
        if (x == ")") {
            return 0;
        } else if (x == "+" || x == "-") {
            return 1;
        } else if (x == "*" || x == "/") {
            return 2;
        }
        return 3;
    }

};

     6
    / \
   5   3
  /   / \
 2   0   1

class Solution {
 public:
    /**
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
    TreeNode* maxTree(vector<int> A) {
        vector<TreeNode *> nodeStack;
        for (int i = 0; i < A.size(); ++i) {
            auto node = new TreeNode(A[i]);
            while (!nodeStack.empty() && A[i] > nodeStack.back()->val) {
                node->left = nodeStack.back();
                nodeStack.pop_back();
            }
            if (!nodeStack.empty()) {
                nodeStack.back()->right = node;
            }
            nodeStack.emplace_back(node);
        }
        return nodeStack.front();
    }
};