LeetCode 399. 除法求值(C++) DFS+回溯

解题思路

首先得理解题目意思：

equations

和

values

：

equations

中每个一维序列表示一对数进行相除（前 / 后），得到的结果就是values中相应位置的值，以上作为已知条件。

queries

：包含两个元素，目的是要我们求：第一个元素 / 第二个元素 = ？

我们可以将其抽象为一个带权图问题，对于

queries

中的两个元素

x, y，

是否有一条路径可以从

x

到

y

，并求出经过这条路径的消耗是多少。由于两个元素的比值是一个常量，所以如果有多条路径，消耗是一样的，选其中一条就可以。

以示例1为例，对于

a/c

，可以由

a/b * b/c

得到，也就是

a->b

与

b->c

两条路径的权值相乘得到，所以路径上的消耗，就是所走过的每条路径的权值之积。

由于每个基本元素类型都是

string

，所以先对所有的元素映射到数字域，方便查找：

// 将equations中的string映射到0，1，2，3...
unordered_map<string, int> map;
int cnt = 0;
for(auto &s : equations){
    for(auto &ch : s){
    	if(!map.count(ch)) map[ch] = cnt++;//map.count（ch） 返回查找的ch个数
    	//即是map中没有ch的时候，建立一个map[ch]=cnt++;
    }
}
           

下一步就是建图，使用邻接表，并且路径之间是双向的，权值互为倒数：

vector<vector<int>> G;
vector<vector<double>> W;
G = vector<vector<int>>(map.size());//map.size()个vector<int>个元素
W = vector<vector<double>>(map.size());//map.size()个vector<double>个元素
for(int i = 0; i < equations.size(); ++i)
{//map[equations[i][0]]是int类型数据，G[map[equations[i][0]]]表示一维的第map[equations[i][0]]个元素
//因此，G[map[equations[i][0]]].push_back(map[equations[i][1]]);表示某一个一维数组中内部加入元素，从而变成二维数组
	G[map[equations[i][0]]].push_back(map[equations[i][1]]);//连接关系
	W[map[equations[i][0]]].push_back(values[i]);//map[equations[i][0]]为W的key;values[i]为W的value
	G[map[equations[i][1]]].push_back(map[equations[i][0]]);
    W[map[equations[i][1]]].push_back(1 / values[i]);
}
           

建好图之后，就可以用深度优先搜索（

DFS

）和回溯算法来找路了，需要用一个数组记录走过的节点，防止重复走过，还需要一个变量

flag

表示起点与终点之间是否存在路径：

int flag = 0; // 初始为0，表示起点与终点之间没有路径。设置为全局变量，在函数中不用调用。
vector<bool> vis;
vis = vector<bool>(map.size());
for (auto& querie : queries) {
    string s1 = querie[0];
    string s2 = querie[1];
    // 如果两个元素相同并且存在于map中，结果就是1
    if (s1 == s2 && map.count(s1)) {
        res.push_back(1.0);
        continue;
    }
    // 如果有一个元素不存在于map中，结果就是-1，因为没有这条路径
    if (!map.count(s1) || !map.count(s2)) {
        res.push_back(-1.0);
        continue;
    }
    // 将起点标记为已使用
    vis[map[s1]] = true;
    // 参数：图，权值，标记数组，起点，终点，当前计算结果（初始为1）
    dfs(G, W, vis, map[s1], map[s2], 1);
    // 使用过后，再次标记为未使用
    vis[map[s1]] = false;
    // 没有路径，结果为-1
    if (flag == 0) res.push_back(-1.0);
    // 已经有路径，将flag置为0，结果已经在DFS中记录过，所以不用再次记录了
    else {
        flag = 0;
    }
}
           

DFS+回溯：

void dfs(vector<vector<int>> &G, vector<vector<double>> &W, vector<bool> &vis, int start, int end, double val){
    if(start == end){//结束条件，start == end表示 映射的数相等 // 将equations中的string映射到0，1，2，3...
        res.push_back(val);
        // 有路径，flag为1
        flag = 1;
        return;
    }
    //unordered_map<string, int> map;  G[map[equations[i][0]]].push_back(map[equations[i][1]]);  此函数的调用start实际为map[s1]，size()函数用于返回映射中存在的元素总数。
    for(int i = 0; i < G[start].size(); ++i){
        // 如果flag已经为1了，说明找到一条路径了，就不需要再找了
        // 剩下的就是一般的回溯算法
        if(vis[G[start][i]] || flag == 1) continue;
        vis[G[start][i]] = true;//G为图
        val *= W[start][i];//W[start][i]等于	W[map[equations[i][1]]].push_back(1 / values[i]);
        dfs(G, W, vis, G[start][i], end, val);// 参数：图，权值，标记数组，起点，终点，当前计算结果
		//以下两行为撤销原来的累积计算
        val /= W[start][i];
        vis[G[start][i]] = false;
    }
}
           

代码

class Solution {
public:
    vector<double> res;
    int flag = 0;
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        vector<vector<int>> G;
        vector<vector<double>> W;
        vector<bool> vis;
        unordered_map<string, int> map;
        int cnt = 0;
        for(auto &s : equations){
            for(auto &ch : s){
                if(!map.count(ch)) map[ch] = cnt++;
            }
        }
        // 建图
        G = vector<vector<int>>(map.size());
        W = vector<vector<double>>(map.size());
        vis = vector<bool>(map.size());
        for(int i = 0; i < equations.size(); ++i){
            G[map[equations[i][0]]].push_back(map[equations[i][1]]);
            W[map[equations[i][0]]].push_back(values[i]);
            G[map[equations[i][1]]].push_back(map[equations[i][0]]);
            W[map[equations[i][1]]].push_back(1 / values[i]);
        }
        for(auto &querie : queries){
            string s1 = querie[0];
            string s2 = querie[1];
            if(s1 == s2 && map.count(s1)){
                res.push_back(1.0);
                continue;
            }   
            if(!map.count(s1) || !map.count(s2)){
                res.push_back(-1.0);
                continue;
            }
            vis[map[s1]] = true;
            dfs(G, W, vis, map[s1], map[s2], 1);
            vis[map[s1]] = false;
            if(flag == 0) res.push_back(-1.0);
            else {
                flag = 0;
            }
        }
        return res;
    }
    void dfs(vector<vector<int>> &G, vector<vector<double>> &W, vector<bool> &vis, int start, int end, double val){
        if(start == end){
            res.push_back(val);
            flag = 1;
            return;
        }
        for(int i = 0; i < G[start].size(); ++i){
            if(vis[G[start][i]] || flag == 1) continue;
            vis[G[start][i]] = true;
            val *= W[start][i];
            dfs(G, W, vis, G[start][i], end, val);
            val /= W[start][i];
            vis[G[start][i]] = false;
        }
    }
};