Good Problem List Summary -3-


  • 0
    F

    Find the Weak Connected Component in the Directed Graph

    Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a connected set of a directed graph is a subgraph in which any two vertices are connected by direct edge path.)

    Solution :

    /**
     * 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;
        }
    };
    

    Ugly Number 1 & 2 & 3

    Solution 1

    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;
        }
    };
    

    Solution 2

    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];
        }
    };
    

    Solution 3

    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];
         }
    };
    

    Expression Evaluation

    Given an expression string array, return the final result of this expression

    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;
        }
    };
    

    Expression Tree Build

    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;
        }
    
    };
    

    Max Tree

    给出一个没有重复的整数数组,在此数组上建立最大树的定义如下:
    1.根是数组中最大的数
    2.左子树和右子树元素分别是被父节点元素切分开的子数组中的最大值
    利用给定的数组构造最大树。
    给出数组 [2, 5, 6, 0, 3, 1],构造的最大树如下:

         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();
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.