您现在的位置是:首页 > 正文

1029-除法求值

2024-04-01 03:57:37阅读 3

题目如下

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件,其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题,其中 queries[j] = [Cj, Dj] 表示第 j 个问题,请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回所有问题的答案 。如果存在某个无法确定的答案,则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串,也需要用 -1.0 替代这个答案。

注意:输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况,且不存在任何矛盾的结果。

在这里插入图片描述

解题思路

class UnionFind {
private:
    vector<int> parent; // 存放父节点
    vector<double> weight; // 指向父节点的权值
    
public:
    UnionFind(int n) {
        for (int i = 0; i < n; ++i) {
            parent.push_back(i);
            weight.push_back(1.0); // 权重初始化为1
        }
    }
    // 路径压缩。返回根节点id
    int find(int x) {
        // 递归寻找根节点,更新该点到根的权重为该点父节点到根的权重
        if (x != parent[x]) {
            int origin = parent[x];
            parent[x] = find(parent[x]);
            weight[x] *= weight[origin];
        }
        return parent[x];
    }
    // 返回除法结果。如果两个值不存在则-1
    double isConected(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        // 如果两个值有共同的根也就是可以计算,则算结果。否则不在同一个并查集,-1
        if (rootX == rootY) {
            return weight[x] / weight[y];
        } else {
            return -1.00000;
        }
    }
    void myunion(int x, int y, double value) {
        // 分别找到二者的根节点
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) {
            return; // 二者已经指向同一个根节点
        }
        // 令分子指向分母的根节点,权重为分母到根的权重*分母除分子的值/分子到根的权重。一开始都是1
        parent[rootX] = rootY;
        weight[rootX] = weight[y] * value / weight[x];
    }
};
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // 初始化并查集
        int equationsSize = equations.size();
        UnionFind unionFind(2 * equationsSize);
        // 第 1 步:预处理,将变量的值与 id 进行映射
        map<string, int> hashMap;
        int id = 0;
        for (int i = 0; i < equationsSize; ++i) {
            // 存分子,分母,值为id
            vector<string> equation = equations[i];
            string var1 = equation[0];
            string var2 = equation[1];
            if (!hashMap.count(var1)) {
                hashMap[var1] = id;
                ++id;
            }
            if (!hashMap.count(var2)) {
                hashMap[var2] = id;
                ++id;
            }
            // 把分子分母用有向边连起来
            unionFind.myunion(hashMap[var1], hashMap[var2], values[i]);
        }
        // 第 2 步:做查询
        int queriesSize = queries.size();
        vector<double> res(queriesSize, -1.00000);
        for (int i = 0; i < queriesSize; ++i) {
            string var1 = queries[i][0];
            string var2 = queries[i][1];
            int id1, id2;
            // 如果两个值有至少一个不在equations中,结果为-1,否则做除法
            if (hashMap.count(var1) && hashMap.count(var2)) {
                id1 = hashMap[var1];
                id2 = hashMap[var2];
                res[i] = unionFind.isConected(id1, id2);
            }
        }
        return res;
    }
};

网站文章

  • 【蓝桥杯每日一练:数列排序】

    问题描述 给定一个长度为n的数列,将这个数列按从小到大的顺序排列。1&lt;=n&lt;=200输入格式 第一行为一个整数n。 第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。输出格式: 输出一行,按从小到大的顺序输出排序后的数列。 ...

    2024-04-01 03:56:56
  • 简洁精美源于分析透彻,构思明确、求精,逻辑练达。(1)

    /*用户输入100~999999范围之内的任意数(如果不是此范围,则报错),判断是否是自方幂数,用户可以反复输入判断直到不需要为止。自方幂数: 一个n位正整数如果等于它的n个数字的n次方和,该数称为n位自方幂数 123=1的3次方+2的3次方+3的3次方?*/ int 范围 = 10, 位 = 位数(范围), 和 = 0, 判断 = 范围; do { 和 += 乘方(判断 % 10,

    2024-04-01 03:56:47
  • 651. 4键键盘(动态规划)

    651. 4键键盘(动态规划)

    651. 4键键盘题目解题思路代码 题目 假设你有一个特殊的键盘包含下面的按键: Key 1: (A):在屏幕上打印一个 &#39;A&#39;。 Key 2: (Ctrl-A):选中整个屏幕。 Ke...

    2024-04-01 03:56:41
  • 深度解析ngx_command_t结构

    因为HTTP框架可以使用预设的14种方法自动 地将解析出的配置项写入HTTP模块代码定义的结构体中,但HTTP模块中可能会定义3个结 构体,分别用于存储main、srv、loc级别的配置项(对应于cr...

    2024-04-01 03:56:35
  • 性能调优11:查询统计

    数据库引擎的工作流程可以归纳为接收请求、执行请求和返回结果。数据库引擎每接收到一个新的查询请求(Query Request),查询优化器就会执行以下工作流程:编译请求:对TSQL语句进行语法解析,编译请求,生成TSQL语句表示的逻辑结构。查询优化:根据TSQL语句的逻辑结构,生成多个预估的执行方案,并根据统计信息,评估每个预估方案的开销,选择开销最低的方案作为最优方案。执...

    2024-04-01 03:55:54
  • Linux Shell 定时删除某几天前文件夹下文件

    脚本 #!/bin/sh echo &#39;清除文件开始&#39;; find /tmp/email -mtime +1 -name &quot;*.*&quot; -exec rm -Rf {} ...

    2024-04-01 03:55:46
  • 前后端分离单点登录

    前后端分离单点登录

    单点登录基于 Apereo CAS实现,不是此次记录的重点。 登陆过程中,需要重定向至CAS Server,前端Vue+axios,需要从单页面跳转至login页面,后端如果使用response.sendRedirect(),返回302,axios并不能拦截到302,浏览器会自动跳转,就会出问题。 解决: 后端判断请求是否是axios(Ajax)请求,如果是,不返回302,约定一个返回码...

    2024-04-01 03:55:38
  • Harbor仓库的管理

    Harbor仓库的管理

    2024-04-01 03:54:58
  • APT(Advanced Persistent Threat高级持续性威胁)——网络安全

    APT(Advanced Persistent Threat高级持续性威胁)——网络安全

    网络安全APT(Advanced Persistent Threat高级持续性威胁)是一种复杂的网络攻击,旨在长期潜伏在目标网络中,有组织的黑客或攻击者利用高级技术手段对目标系统进行持续的渗透和监视,以获取敏感信息、窃取数据或进行其他恶意攻击活动。下面是一些关于网络安全有关APT的介绍:

    2024-04-01 03:54:52
  • Lucene .NET 全文检索

    Lucene .NET 全文检索

    近期做项目中有用到过Lucene,那个模块是由一位前端大神负责的,空闲时间我也做了个关于Lucene做全文检索的Demo,记录下来,方便以后学习。 关于Lucene的原理,网上有长篇大论的文章,有兴趣的话可以去阅读,再次我就直奔主题,在代码中分析其原理。 1、创建索引(此处我用的是盘古分词) 注:在后台代码的第一行上加上 #definenotes这样一行代码,目的是可以用外侧代码的#if,

    2024-04-01 03:54:44