分享几个

计算器题（包含加减乘除和括号）

class Solution {
public:
   
    stack<int> num;
    stack<char> ops;
   
    void eval() {
        auto b = num.top(); num.pop();
        auto a = num.top(); num.pop();
        auto c = ops.top(); ops.pop();
        int x;
        if (c == '+') x = a + b;
        else if (c == '-') x = a - b;
        else if (c == '*') x = a * b;
        else x = a / b;
        num.push(x);
    }

   
    int calculate(string s) {
        unordered_map<char, int> pred = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
        for (int i = 0; i < s.size(); ++i) {
            if (isdigit(s[i])) {
                int curr = 0, j = i;
                while (j < s.size() && isdigit(s[j])) {
                    curr = curr * 10 + (s[j] - '0');
                    j++;
                }
                i = j - 1;
                num.push(curr);
            }
            else if (s[i] == '(') ops.push(s[i]);
            else if (s[i] == ')') {
                while (ops.top() != '(')
                    eval();
                ops.pop();
            } else {
                while (ops.size() && ops.top() != '(' && pred[ops.top()] >= pred[s[i]])
                    eval();
                ops.push(s[i]);
            }
        }
        while (ops.size())
            eval();
        return num.top();
    }
};
Dijkstra算法（单源最短路径，要求路径权值大于0）

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& pro, int start, int end) {
        vector<vector<pair<int, double>>> g(n);
        for(int i=0; i<edges.size(); i++) {
            g[edges[i][0]].push_back({edges[i][1], pro[i]});
            g[edges[i][1]].push_back({edges[i][0], pro[i]});   
        }
        vector<int> seen(n, 0);
        
        priority_queue<pair<double, int>> q;
        q.push({(double)1.0, start});
        
        vector<double> mx(n, (double)0.0);
        mx[start] = 1.0;
        
        while(!q.empty()) {
            auto top = q.top();
            q.pop();
            double proba = top.first;
            int node = top.second;
            if(!seen[node]) {
                seen[node]++;
                for(auto &to: g[node]) {
                    if (mx[to.first] < to.second*proba) { // relexation
                        mx[to.first] = to.second*proba;
                                q.push({mx[to.first], to.first});
                    }
                }
            }
        }
        return mx[end];
    }
};

弗洛伊德算法（多源最短路径）
class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> dist(n, vector<int>(n, 10001));
        for (auto e : edges) {
            dist[e[0]][e[1]] = e[2];
            dist[e[1]][e[0]] = e[2];
        }
        for (int i = 0; i < n; ++i)
            dist[i][i] = 0;
        for (int k = 0; k < n; ++k)
            for (int j = 0; j < n; ++j)
                for (int i = 0; i < n; ++i)
                    // if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
                    dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
        int res = 0, minCount = n;
        for (int i = 0; i < n; ++i) {//source
            int currCnt = 0;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                if (distanceThreshold >= dist[i][j]) currCnt++;
            }
            if (currCnt <= minCount) {
                res = i;
                minCount = currCnt;
            }
        }
        return res;        
    }
};

Topological Sort（有向图遍历）
vector<string> findAllRecipes(vector<string>& rec, vector<vector<string>>& ing, vector<string>& sup) {
        unordered_map<string,vector<string>> graph;
        int n = rec.size();
        unordered_set<string> s;
        for(auto x : sup) s.insert(x);            //store all the supplies in unordered set
               
        unordered_map<string,int> indegree;   //to store the indegree of all recipes
        for(auto x : rec)indegree[x] = 0;                      //initially take the indegree of all recipes to be 0
   
        for(int i = 0; i < n; i++){
            for(int j = 0; j < (int)ing[i].size(); j++){
                if(s.find(ing[i][j]) == s.end()){     
                    graph[ing[i][j]].push_back(rec[i]);    //if the ingredient required to make a recipe is not in supplies then  
                    indegree[rec[i]]++;                     //we need to make a directed edge from that ingredient to recipe
                }
            }
        }
        
        //KAHN'S ALGORITHM
        queue<string> q;
        for(auto x : indegree){
            if(x.second == 0){
                q.push(x.first);
            }
        }
       vector<string> ans;
        while(!q.empty()){
            string tmp = q.front();
            q.pop();
            ans.push_back(tmp);
            for(auto nbr : graph[tmp]){
                indegree[nbr]--;
                if(indegree[nbr] == 0)
                    q.push(nbr);
            }
        }
        return ans;
    }

time+space
计算器复杂度：O(n) + O(n)
Dijkstra复杂度：O(n * log(n))或者O(n^2) + O(n)，n为节点数
弗洛伊德复杂度：O(n^3) + O(n)，n为节点数
拓扑排序复杂度：O(V+E) + O(V+E)