399 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:

1

2

3
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,则构造一个自a到b的边,边上的权值为2,以此类推。

构造邻接表,分配数组下标,利用BFS的方法遍历图。如果我们需要提高执行效率的话,还可以给图的邻接表增加新的项目以缓存结果。 Shell32的博客

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80
class Solution {

public:

    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {

        vector<double> result;

        int count = 1;

        unordered_map<string, int> index;

        

        for (int i = 0; i < equations.size(); i++){

            string tmp1 = equations[i].first;

            string tmp2 = equations[i].second;

            if(index.find(tmp1) == index.end()){

                index[tmp1] = count;

                count++;

            }

            if(index.find(tmp2) == index.end()){

                index[tmp2] = count;

                count++;

            }

        }

        vector< vector<double> > graph(index.size());

        for (int i = 0; i < index.size(); i++){

            graph[i].resize(index.size());

        }

        for (int i = 0; i < equations.size(); i++){

            int tmp1 = index[equations[i].first] - 1;

            int tmp2 = index[equations[i].second] - 1;

            graph[tmp1][tmp2] = values[i];

            graph[tmp2][tmp1] = 1.0 / values[i];

        }

        

            for(int j = 0; j < graph[i].size(); j++){

                cout << graph[i][j] << " ";

            }

            cout << endl;

        }*/

        for (int i = 0; i < queries.size(); i++){

            int start = index[queries[i].first] - 1;

            int end = index[queries[i].second] - 1;

            if (start < 0 || end < 0){

                result.push_back(-1.0);

            }

            else{

                if (start == end) result.push_back(1.0);

                else{

                    vector<int> visited(index.size());

                    queue<int> q;

                    queue<double> ans;

                    q.push(start);

                    ans.push(1);

                    bool hasResult = false;

                    while(!q.empty()){

                        int tmp = q.front();

                        double value = ans.front();

                        visited[tmp] = 1;

                        for(int j = 0; j < graph.size(); j++){

                            if(visited[j] == 0 && graph[tmp][j] > 0){

                                if (j != end) {

                                    q.push(j);

                                    ans.push(value * graph[tmp][j]);

                                }

                                else{

                                    result.push_back(value * graph[tmp][j]);

                                    hasResult = true;

                                }

                            }

                        }

                        q.pop();

                        ans.pop();

                    }

                    if (!hasResult) result.push_back(-1.0);

                }

            }

        }

        return result;

    }

};  

—|—

最后注意几个C++语言当中的小技巧。

迭代器访问,注意用it->first访问pair的第一个元素,it是一个指向迭代器的指针。

1

2

3
for(auto it = equations.begin(); it != equations.end(); ++it){

	cout << it->first << " " << it->second << endl;

}  

—|—

C++当中,STL标准库当中的set求交集的代码。

1

2

3

4

5

6
string a = queries[i].first;

string b = queries[i].second;

set<string> pick;

set_intersection(sets[a].begin(), sets[a].end(), sets[b].begin(), sets[b].end(), inserter(pick, pick.begin()));

string element = *pick.begin();  

—|—

有问题的一段代码,从图的观点来看,只做到了第一层DFS,并没有进一步往下走。所以失败了QAQ

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41
class Solution {

public:

    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {

        unordered_map<string, unordered_map<string, double> > stats;

        unordered_map<string, set<string> > sets;

        for(int i=0; i<values.size(); i++){

            stats[equations[i].first][equations[i].first] = 1.0;

            stats[equations[i].first][equations[i].second] = values[i];

            stats[equations[i].second][equations[i].second] = 1.0;

            stats[equations[i].second][equations[i].first] = 1.0 / values[i];

            sets[equations[i].first].emplace(equations[i].first);

            sets[equations[i].first].emplace(equations[i].second);

            sets[equations[i].second].emplace(equations[i].first);

            sets[equations[i].second].emplace(equations[i].second);

        }

        vector<double> result;

        for(int i=0; i<queries.size(); i++){

            string a = queries[i].first;

            string b = queries[i].second;

            set<string> pick;

            set_intersection(sets[a].begin(), sets[a].end(), sets[b].begin(), sets[b].end(), inserter(pick, pick.begin()));

            if (pick.empty()){

                result.push_back(-1.0);

            }

            else{

                string element = *pick.begin();

                double ans = stats[a][element] / stats[b][element];

                result.push_back(ans);

            }

        }

        return result;

    }

};  

—|—

糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017