大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

  • 图的建立和查找
  • 深度优先搜索 (DFS) 或广度优先搜索 (BFS)

题目解答方法的文字分析

本题需要根据给定的牛群体重比关系，找出问题中给定的牛群体重之间的比值。可以将牛群体重比关系建立成一个图，然后利用深度优先搜索或广度优先搜索的方法来找到问题中牛群体重的比值。如果在搜索过程中找不到某个牛的体重比关系，则返回-1.0作为答案。

具体步骤如下：

  1. 遍历 weightRatios 数组，将其中的牛群体重比关系建立成一个图。图可以用一个哈希表来表示，其中键是牛的编号，值是一个包含与该牛有体重比关系的其他牛的编号和比值的二元组。
  2. 遍历 questions 数组，对于每个问题 [Cj, Dj]，用深度优先搜索或广度优先搜索的方法在图中找到 Cj 和 Dj 的体重比值。如果找不到，则返回-1.0作为答案。
  3. 将每个问题的答案存入结果数组，并返回结果数组。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <string>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightRatios string字符串vector<vector<>> 
     * @param ratioValues double浮点型vector 
     * @param questions string字符串vector<vector<>> 
     * @return double浮点型vector
     */
    vector<double> calcWeightRatios(vector<vector<string> >& weightRatios, vector<double>& ratioValues, vector<vector<string> >& questions) {
        // 建立图的哈希表，键是牛的编号，值是一个包含与该牛有体重比关系的其他牛的编号和比值的二元组
        unordered_map<string, vector<pair<string, double>>> graph;
        for (int i = 0; i < weightRatios.size(); i++) {
            string Ai = weightRatios[i][0];
            string Bi = weightRatios[i][1];
            double value = ratioValues[i];
            graph[Ai].emplace_back(Bi, value);
            graph[Bi].emplace_back(Ai, 1.0 / value);
        }

        vector<double> answers;

        // 遍历问题数组，对每个问题进行搜索
        for (auto& question : questions) {
            string Cj = question[0];
            string Dj = question[1];

            // 如果起点或终点不在图中，返回-1.0
            if (graph.find(Cj) == graph.end() || graph.find(Dj) == graph.end()) {
                answers.push_back(-1.0);
            } else {
                double answer = dfs(graph, Cj, Dj);
                answers.push_back(answer);
            }
        }

        return answers;
    }

private:
    double dfs(unordered_map<string, vector<pair<string, double>>>& graph, const string& start, const string& target) {
        // 如果起点和终点相同，则返回1.0
        if (start == target) {
            return 1.0;
        }

        // 使用队列进行广度优先搜索
        queue<pair<string, double>> q;
        q.push({start, 1.0});
        unordered_map<string, bool> visited;

        while (!q.empty()) {
            auto [node, value] = q.front();
            q.pop();
            visited[node] = true;

            for (auto& neighbor : graph[node]) {
                if (neighbor.first == target) {
                    return value * neighbor.second;
                }

                if (!visited[neighbor.first]) {
                    q.push({neighbor.first, value * neighbor.second});
                }
            }
        }

        // 如果搜索完毕后仍未找到目标节点，则返回-1.0
        return -1.0;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！