LeetCode

剑指 Offer II 111. 计算除法

399. 除法求值

class Solution {
public:
    vector calcEquation(vector>& equations, vector& values, vector>& queries) {
        vector r;
        //转换成图: 一维是起始索引，二维是pair{终止节点，权重}
        vector>> graph;
        unordered_map m;
        int n = buildGraph(equations, values, m, graph);
        
        for (auto& v : queries)
        {
            if (!m.count(v[0]) || !m.count(v[1]))
            {
                r.push_back(-1.0);
            }
            else
            {
                r.push_back(dijkstra(n, m[v[0]], m[v[1]], graph));
            }            
        }

        return r;
    }

    int buildGraph(vector>& equations, vector& values, unordered_map& m, vector>>& graph)
    {
        static int index = 0;
        int n = equations.size();
        graph.resize(2*n);

        for (int i=0;i
    //为了避免图中有孤立的节点，建议传入图中节点的数量
	double dijkstra(int n, int start, int end, vector>>& graph)
	{          
		// 定义：distTo[i] 的值就是起点 start 到达节点 i 的最小权重
		vector distTo(n, INT_MAX);
		// base case，start 到 start 的最小权重
		distTo[start] = 1.0;

		// 优先级队列，distFromStart 较小的排在前面
		struct cmp
		{
			//[0]: 当前节点, [1]: 从start到达当前节点的最小概率
			bool operator () (const pair& a, const pair& b)
			{
				return a.second > b.second;
			}
		};

		//构建基于权重的最小堆
		priority_queue, vector>, cmp> minHeap;
		// 从起点 start 开始进行 BFS
		minHeap.push(make_pair(start, 1.0));

		while (!minHeap.empty())
		{
			auto currNode = minHeap.top();
			minHeap.pop();
			int curNodeID = currNode.first;
			if (curNodeID == end)
				return distTo[curNodeID];

			// 将 curNode 的相邻节点装入队列
			for (auto& neighbor : graph[curNodeID])
			{
				int nextNodeID = neighbor.first;
				// int distTonextNode = distTo[curNodeID] + neighbor.second;
				double distTonextNode = distTo[curNodeID] * neighbor.second;

				if (distTo[nextNodeID] > distToNextNode)
				{
					distTo[nextNodeID] = distToNextNode;
					minHeap.push(make_pair(nextNodeID, distToNextNode));
				}
			}
		}

		return (int)distTo[end] == INT_MAX ? -1.0 : distTo[end];
	}    
};

class Solution {
public:
    vector calcEquation(vector>& equations, vector& values, vector>& queries) {
        vector r;
        unordered_map> graph;
        buildGraph(equations, values, graph);

        for (auto& v : queries)
        {
            string first = v[0], second = v[1];
            if (graph.count(first))
            {
                if (graph[first].count(second))
                {
                    r.push_back(graph[first][second]);
                }
                else
                {
                    if (first == second)
                    {
                        r.push_back(1.0);
                    }
                    else
                    {
                        double res = -1.0;
                        unordered_map visited;
                        visited[first] = true;
                        for (auto& item : graph[first])
                        {
                            res = dfs(graph[first][item.first], item.first, second, graph, visited);
                            if (-1.0 != res)
                            {
                                break;
                            }
                        }
                        visited[first] = false;
                        r.push_back(res);
                        if (-1.0 != res)
                        {
                            graph[first].insert({second, res});
                            graph[second].insert({first, 1.0 / res});
                        }
                    }                    
                }
            }
            else
            {
                r.push_back(-1.0);
            }
        }

        return r;
    }

    void buildGraph(vector>& equations, vector& values, unordered_map>& graph)
    {
        int n = equations.size();
        for (int i=0;i>& graph, unordered_map& visited)
    {
        double res = -1.0;
        do
        {
            if (visited[first])
                break;

            if (!graph.count(first) || !graph.count(second))
                break;
            
            if (first.compare(second) == 0)
            {
                res = 1.0;
                break;
            }
            else
            {
                if (graph[first].count(second))
                {
                    res = base * graph[first][second];
                }
                else
                {
                    visited[first] = true;
                    for (auto& item : graph[first])
                    {
                        res = dfs(graph[first][item.first], item.first, second, graph, visited);
                        if (-1.0 != res)
                        {
                            res *= base;                            
                            break;
                        }
                    }
                    visited[first] = false;
                }
            }
        }while(0);
        
        return res;
    }
};