【LeetCode】HOT 100（25）

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

目录

题单介绍：

题目：399. 除法求值 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：406. 根据身高重建队列 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

---

题目：399. 除法求值 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {

    }
};

解题思路：

这道题是图和并查集，

怎么说呢，就是我大概都不会，

但是使用的算法是dfs深度优先搜索，

所以还是值得一战，人生总得挑战一下困难，

具体思路是这样：

用一个map来构建无向图，再用一个map来存标记位，

通过dfs遍历图求解：

代码如下：

代码：

class Solution {
public:
    vector<double> res; //存放结果的数组
    bool Nofind;
    vector<double> calcEquation(vector<vector<string>>& equations, 
        vector<double>& values, vector<vector<string>>& queries) {

        // string - string(double) a连接上b(b带上权值)
        unordered_map<string, vector<pair<string, double>> > g; //用于构建图
        unordered_map<string, int> visit;                       //用来标记已经走过的节点

        //构建无向图，a-b的value是 3 的话，b-a就是 3 的倒数
        for(int i = 0; i < equations.size(); i++) {
            g[equations[i][0]].push_back({equations[i][1], values[i]});
            g[equations[i][1]].push_back({equations[i][0], 1.0 / values[i]});
        }

        //遍历queries，对每一组进行dfs计算
        //如果相连接，把路上的权值相乘就是结果
        for(int i = 0; i < queries.size(); i++) {
            if(g.find(queries[i][0]) == g.end()) {
                res.push_back(-1.0); //没出现就输出 -1.0
                continue;
            }

            //如果进行dfs之后，queries[0]到不了queries[1]，让Nofind = true;
            Nofind = true;

            visit[queries[i][0]] = 1;
            dfs(g, visit, queries[i][0], queries[i][1], 1);
            visit[queries[i][0]] = 0;

            if(Nofind) res.push_back(-1.0);
        }
        return res;
    }

private:
    void dfs(unordered_map<string, vector<pair<string, double>> >& g
        , unordered_map<string, int>& visit, const string& val
        , const string& target, const double& path) {
        
        //如果节点已经相连接，那就没有必要dfs搜索了
        if(Nofind == false) return;

        if(val == target) {
            Nofind = false;
            res.push_back(path);
            return;
        }

        for(int j = 0; j < g[val].size(); j++) {
            //检查该点是否访问过，没有就继续dfs
            if(visit[ g[val][j].first ] == 0) {
                visit[ g[val][j].first ] = 1;
                dfs(g, visit, g[val][j].first, target, path * g[val][j].second);
                visit[ g[val][j].first ] = 0;
            }
        }
    }
};

过过过过啦！！！！

题目：406. 根据身高重建队列 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {

    }
};

解题思路：

这道题目我读了好多遍不知道他究竟想说什么，

真的搞不懂，都不知道他为啥呀这样写题干，

我找了很多人的解释，找到了一个非常好的解释，我这里把链接贴出来，

他讲的真的是太好了，一下子就看懂了，真的是救星：题目意思解析，一看就懂

具体思路如下：

先把对列从高到矮排好，

然后根据他们看到的比自己高的人的数量逐个插入进对列即可，

代码如下：

代码：

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //这个lambda表达式的意思是，身高高的在前面，一样高的，看到的人少的在前面
        sort(people.begin(), people.end(), [](const vector<int>& x, const vector<int>& y) {
            return x[0] > y[0] || (x[0] == y[0] && x[1] < y[1]);
        });
        vector<vector<int>> ans;
        for(const auto person : people) {
            //这里就是根据他看到前面有几个人来插入进队伍
            ans.insert(ans.begin() + person[1], person);
        }
        return ans;
    }
};

过过过过啦！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~