力扣剑指offer2第38天图

111）计算除法

class Solution{
public:
    vector calcEquation(vector>& equations, vector& values, vector>& queries){
        int nvars = 0;
        unordered_map variables;
        int n = equations.size();
        for(int i=0; i>> edges(nvars);
        for(int i=0; i ret;
        for(auto& q : queries){
            double result = -1.0;
            if(variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()){
                int ia = variables[q[0]], ib = variables[q[1]];
                if(ia==ib) result = 1.0;
                else{
                    queue points;
                    points.push(ia);
                    vector ratios(nvars, -1.0);
                    ratios[ia] = 1.0;
                    while(!points.empty() && ratios[ib]<0){
                        int x = points.front();
                        points.pop();
                        for(auto [y, val] : edges[x]){
                            if(ratios[y]<0) {
                                ratios[y] = ratios[x] * val;
                                points.push(y);
                            }
                        }
                    }
                    result = ratios[ib];
                }
            }
            ret.push_back(result);        
        }
        return ret;
    }
};

112. 最长递增路径

class Solution{
public:
    int rows, cols;
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int longestIncreaseingPath(vector>& matrix){
        if(!matrix.size() || !matrix[0].size()) return 0;
        rows = matrix.size(), cols = matrix[0].size();
        
        int ans = 0;
        vector> res(rows, vector(cols));
        for(int i=0; i>& matrix, int row, int col, vector>& res){
        if(res[row][col] != 0) return res[row][col];
        res[row][col]++;
        for(int i=0; i<4; i++){
            int newrow = row+dirs[i][0], newcol = col+dirs[i][1];
            res[row][col] = max(res[row][col], dfs(matrix, newrow, newcol, res)+1);
        }
        return res[row][col];
    }
};

113)课程顺序(课程表II)

class Solution{
public:
    vector findOrder(int numCourses, vector>& prerequisites){
        vector> edges(numCourses);
        vector indegree(numCourses);
        for(auto &item : prerequisites){
            edges[item[1]].push_back(item[0]);
            indegree[item[0]]++;
        }
        
        queue q;
        for(int i=0; i res;
        while(!q.empty()){
            int x = q.front();
            q.pop();
            res.push_back(x);
            for(auto y : edges[x]){
                indegree[y]--;
                if(indegree[y]==0){
                    q.push(y);
                }
            }
        }
        return res.size()==numCourses ? res : vector{};
    }
};