LeetCode Evaluate Division

LeetCode Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.


给定一系列的除法表达式,要计算另一些除法表达式的结果。比如知道a/b=2.0,b/c=3.0,问a/c=?。

本题的解法是把一系列表达式转换为图,比如a/b=2.0转换为a指向b的边,边的值为2.0,同时b指向a的边的值为1/2.0。如果要求a/c,则在图中找一条a到c的边,并且把走过的边的值乘起来。

构建图的过程先把表达式中的string编码成int,然后把已知的直连边加入到图中。对于要查询的边start/target,首先判断一下两个端点是否在图中,如果至少有一个端点不在图中,则无法求值,返回-1。否则,在图中DFS或BFS找到target,走过的路径乘积就是结果。

题目说明所有values都是正数,所以不存在除0问题。

DFS代码如下:

class Solution {
private:
	bool dfs(vector<vector<double>>& graph, int start, int x, int y, int target) {
		graph[start][y] = graph[start][x] * graph[x][y];
		graph[y][start] = 1.0 / graph[start][y];
		if(y == target)return true;

		int n = graph.size();
		for(int i = 0; i < n; ++i){
			if(graph[start][i] == 0 && graph[y][i] != 0){
				if(dfs(graph, start, y, i, target))return true;
			}
		}
		return false;
	}
	double helper(vector<vector<double>>& graph, int start, int target) {
		if (start == target)return 1.0;
		else if (graph[start][target] != 0.0)return graph[start][target];
		int n = graph.size();
		for (int y = 0; y < n; ++y) {
			if (y == start)continue;
			if (graph[start][y] != 0.0) {
				if (dfs(graph, start, start, y, target))return graph[start][target];
			}
		}
		return -1.0;
	}
public:
	vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
		int cnt = 0, n = equations.size();
		unordered_map<string, int> hash;
		for (int i = 0; i < n; ++i) {
			if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
			if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
		}
		vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
		for (int i = 0; i < n; ++i) {
			int x = hash[equations[i].first], y = hash[equations[i].second];
			graph[x][x] = 1;
			graph[y][y] = 1;
			graph[x][y] = values[i];
			graph[y][x] = 1.0 / values[i];
		}
		vector<double> ans;
		for (int i = 0; i < queries.size(); ++i) {
			if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
			else {
				int x = hash[queries[i].first], y = hash[queries[i].second];
				ans.push_back(helper(graph, x, y));
			}
		}
		return ans;
	}
};

本代码提交AC,用时3MS。

BFS代码如下:

class Solution {
private:
	double bfs(vector<vector<double>>& graph, int start, int target) {
		if (start == target)return 1.0;
		else if (graph[start][target] != 0.0)return graph[start][target];

		int n = graph.size();
		queue<int> q;
		for(int x = 0; x < n; ++x){
			if(x != start && graph[start][x] != 0)q.push(x);
		}
		while(!q.empty()){
			int x = q.front();
			if(x == target) return graph[start][target];
			q.pop();
			for(int y = 0; y < n; ++y){
				if(graph[start][y] == 0 && graph[x][y] != 0){
					graph[start][y] = graph[start][x] * graph[x][y];
					graph[y][start] = 1.0 / graph[start][y];
					q.push(y);
				}
			}
		}
		return -1.0;
	}
public:
	vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
		int cnt = 0, n = equations.size();
		unordered_map<string, int> hash;
		for (int i = 0; i < n; ++i) {
			if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
			if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
		}
		vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
		for (int i = 0; i < n; ++i) {
			int x = hash[equations[i].first], y = hash[equations[i].second];
			graph[x][x] = 1;
			graph[y][y] = 1;
			graph[x][y] = values[i];
			graph[y][x] = 1.0 / values[i];
		}
		vector<double> ans;
		for (int i = 0; i < queries.size(); ++i) {
			if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
			else {
				int x = hash[queries[i].first], y = hash[queries[i].second];
				ans.push_back(bfs(graph, x, y));
			}
		}
		return ans;
	}
};

本代码提交AC,用时0MS,类似的题BFS显然要比DFS快,而且这题用BFS思路更清晰。

Leave a Reply

Your email address will not be published. Required fields are marked *