时间轴

2025-11-04

init

题目：

P399 除法求值

https://leetcode.cn/problems/evaluate-division/description/?envType=study-plan-v2&envId=top-interview-150

这题要注意，给出 a/b = val,那么b/a = 1/val, 即并非无向图。对于queries要考虑给出的变量不合法的情况。

邻接表+DFS

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <stack>
#include <utility>

using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
using std::stack;
using std::pair;

template <class T> struct Arc {
    T val;   // 边权
    int vex; // 指向的节点索引
    struct Arc<T>* next;
};

template <class T, class V> struct Node {
    T val;
    struct Arc<V>* first;
};

template <class T, class V> struct AdjGraph {
    vector<Node<T, V>> vertices;
};

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations,
                                vector<double>& values,
                                vector<vector<string>>& queries)
    {
        AdjGraph<string, double> graph;
        unordered_map<string, int> umap;
        vector<Arc<double>*> arcs;
        vector<double> res;

        int i, n = equations.size();
        string dividend, divisor;

        // ===== 构建图 =====
        for (i = 0; i < n; i++) {
            dividend = equations[i][0];
            divisor = equations[i][1];

            if (!umap.count(dividend)) {
                Node<string, double> node;
                node.val = dividend;
                node.first = nullptr;
                graph.vertices.push_back(node);
                umap[dividend] = graph.vertices.size() - 1;
            }
            if (!umap.count(divisor)) {
                Node<string, double> node;
                node.val = divisor;
                node.first = nullptr;
                graph.vertices.push_back(node);
                umap[divisor] = graph.vertices.size() - 1;
            }

            // 添加两条边：正向 + 反向
            Arc<double>* arc1 = new Arc<double>();
            arc1->val = values[i];
            arc1->vex = umap[divisor];
            arc1->next = graph.vertices[umap[dividend]].first;
            graph.vertices[umap[dividend]].first = arc1;
            arcs.push_back(arc1);

            Arc<double>* arc2 = new Arc<double>();
            arc2->val = 1.0 / values[i];
            arc2->vex = umap[dividend];
            arc2->next = graph.vertices[umap[divisor]].first;
            graph.vertices[umap[divisor]].first = arc2;
            arcs.push_back(arc2);
        }

        // ===== 查询阶段 =====
        n = queries.size();
        string start, target;
        int start_idx, target_idx;
        double ans;


        for (i = 0; i < n; i++) {
            start = queries[i][0];
            target = queries[i][1];

            if (!umap.count(start) || !umap.count(target)) {
                res.push_back(-1.0);
                continue;
            }

            start_idx = umap[start];
            target_idx = umap[target];

            if (start_idx == target_idx) {
                res.push_back(1.0);
                continue;
            }
            // index, prod
            // 节点索引，当前累乘

            stack<pair<int, double>> st;
            unordered_set<int> visited;
            
            st.push({start_idx, 1.0});

            ans = -1.0;
            // 深度优先遍历
            while (!st.empty()) {
                auto [curr, prod] = st.top();
                st.pop();

                if (curr == target_idx) {
                    ans = prod;
                    break;
                }

                if (visited.count(curr)){
                    continue;
                }
                
                visited.insert(curr);

                for (Arc<double>* p = graph.vertices[curr].first; p!=nullptr; p = p->next) {
                    if (!visited.count(p->vex)){
                        st.push({p->vex, prod * p->val});                        
                    }
                }
            }
            res.push_back(ans);
        }

        for (auto p : arcs)
            delete p;

        return res;
    }
};

unordered_map>

用 unordered_map> 构造图最为简便。

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
#include <unordered_map>
#include <vector>
#include <string>
#include <stack>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations,
                                vector<double>& values,
                                vector<vector<string>>& queries)
    {
        // ===== 构建图 =====
        unordered_map<string, vector<pair<string, double>>> graph;

        for (int i = 0; i < equations.size(); i++) {
            string a = equations[i][0];
            string b = equations[i][1];
            double val = values[i];

            graph[a].push_back({b, val});
            graph[b].push_back({a, 1.0 / val});
        }

        // ===== 查询阶段 =====
        vector<double> res;
        for (auto& q : queries) {
            string start = q[0], target = q[1];
            if (!graph.count(start) || !graph.count(target)) {
                res.push_back(-1.0);
                continue;
            }

            if (start == target) {
                res.push_back(1.0);
                continue;
            }

            // DFS 栈：{当前节点, 当前乘积}
            stack<pair<string, double>> st;
            unordered_set<string> visited;

            st.push({start, 1.0});
            double ans = -1.0;

            while (!st.empty()) {
                auto [node, val] = st.top();
                st.pop();

                if (node == target) {
                    ans = val;
                    break;
                }

                if (visited.count(node))
                    continue;

                visited.insert(node);
                for (auto& [next, weight] : graph[node]) {
                    if (!visited.count(next)) {
                        st.push({next, val * weight});
                    }
                }
            }
            res.push_back(ans);
        }

        return res;
    }
};