《剑指 Offer》专项突破版 - 面试题 111 : 计算除法(C++ 实现)

题目链接:计算除法

题目

输入两个数组 equations 和 values,其中,数组 equations 的每个元素包含两个表示变量名的字符串,数组 values 的每个元素是一个浮点数值。如果 equations[i] 的两个变量名分别是 A_i 和 B_i,那么 A_i / B_i = values[i]。再给定一个数组 queries,它的每个元素也包含两个变量名。对于 queries[j] 的两个变量名 C_j 和 D_j,请计算 ​ C_j / D_j 的结果。假设任意 values[i] 大于 0。如果不能计算,那么返回 -1.0。

例如,输入数组 equations 为 [["a", "b"], ["b", "c"]],数组 values 为 [2.0, 3.0],如果数组 queries 为 [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]],那么对应的计算结果为 [6.0, 0.5, -1.0, 1.0, -1.0]。由数组 equations 和 values 可知,a / b = 2.0,b / c = 3.0,所以,a / c = 6.0,b / a = 0.5,a / a = 1.0。

分析

图可以用来表示物体与物体之间的关系,节点对应物体,而物体之间的关系用边表示。这个问题是关于两个变量之间的除法,因此可以将变量看作图中的节点。如果存在两个变量的除法等式,那么这两个变量对应的节点之间有一条边相连

一个除法等式除了被除数和除数,还有商。被除数和除数都对应图中的节点,商是两个变量的除法的结果,表达的是变量之间的关系,因此商是边的属性。可以给图中的每条边定义一个权重,为两个变量的除法的商

由于 a / b 一般不等于 b / a,因此从节点 a 到节点 b 的边和从节点 b 到节点 a 的边的权重不同,即这个图是有向图,节点 a 和节点 b 之间有两条不同方向的有向边

可以尝试根据数组 equations [["a", "b"], ["b", "c"]] 和数组 values [2.0, 3.0] 构建对应的图。因为 a / b = 2.0,所以图中有一条从节点 a 到节点 b 的边,权重为 2.0。同时由数学常识可知 b / a = 1/2,所以图中还有一条由节点 b 指向节点 a 的权重为 1/2 的边。类似地,因为 b / c = 3.0,所以图中有一条由节点 b 指向节点 c 的权重为 3.0 的边,还有一条由节点 c 指向节点 b 的权重为 1/3 的边。构建出来的图如下图所示。

构建出图之后就可以逐一计算数组 queries 中除法表达式的值。

代码实现

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)
        {
            graph[equations[i][0]].push_back({ equations[i][1], values[i] });
            graph[equations[i][1]].push_back({ equations[i][0], 1.0 / values[i] });
        }
​
        vector<double> result(queries.size(), -1.0);
        for (int i = 0; i < queries.size(); ++i)
        {
            if (graph.count(queries[i][0]) && graph.count(queries[i][1]))
            {
                unordered_set<string> visited;
                result[i] = dfs(graph, visited, queries[i][0], queries[i][1]);
            }
        }
        return result;
    }
private:
    double dfs(unordered_map<string, vector<pair<string, double>>>& graph, unordered_set<string>& visited, string& from, string& to) {
        if (from == to)
            return 1.0;
        
        visited.insert(from);
        for (pair<string, double>& node : graph[from])
        {
            if (!visited.count(node.first))
            {
                double ret = dfs(graph, visited, node.first, to);
                if (ret > 0)
                    return node.second * ret;
            }
        }
        visited.erase(from);
        return -1.0;
    }
};
  1. 在上述代码中,图是用 unordered_map 表示的邻接表,unordered_map 的键是图中的节点(对应一个变量,是有向边的起始节点);值是一个数组,数组中的每个元素包含有向边的终止节点和边的权重

  2. 接下来考虑如何计算除法。已知 a / b = 2.0、b / c = 3.0,那么 a / c 等于多少?由数学常识可知 \dfrac{a}{b} \times \dfrac{b}{c} = \dfrac{a}{c},所以 a / c = 6.0。由于 a / b = 2.0 对应图中从节点 a 指向节点 b 的一条权重为 2.0 的边,b / c = 3.0 对应图中从节点 b 指向节点 c 的一条权重为 3.0 的边,计算 a / c 的过程可以看成在图中找到一条从节点 a 到节点 c 的路径,并将该路径经过的边的权重相乘

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/550914.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

接口测试——postman

一.下载与安装 https://www.getPostman.com/ 界面导航说明 二.get请求 第一个get请求 批量执行接口请求&#xff1a; 1. 右击run collection 2. 会出现runner标签页 携带参数的GET请求 所谓的查询参数&#xff0c;其实就是URL地址中问号&#xff08;?&#xff09;后面的部分…

易基因: MeRIP-seq揭示lncRNA甲基化通过lncRNA-miRNA/蛋白质轴抑制胃癌干细胞凋亡|文献解读

大家好&#xff0c;这里是专注表观组学十余年&#xff0c;领跑多组学科研服务的易基因。 癌症一直是生物学研究的热门话题。关于癌症起源&#xff0c;一种主流观点是癌症干细胞&#xff08;Cancer Stem Cell&#xff0c;CSC&#xff09;的无限增殖。CSC是肿瘤内肿瘤细胞的一个…

textview允许长文本下滑

原本是用scroview textview的&#xff0c;结果长文本的时候&#xff0c;textview会把文本内容截断&#xff1b; 后面在网上找到直接使用textview就能解决长文本问题&#xff0c; 关键代码还是这两个 android:scrollbars“vertical” tv_message_message.setMovementMethod(…

5.HC-05蓝牙模块

配置蓝牙模块 注意需要将蓝牙模块接5v,实测接3.3v好像不太好使的样子 首先需要把蓝牙模块通过TTL串口模块接到我们的电脑,然后打开我们的串口助手 注意,我们现在是配置蓝牙模块,所以需要进入AT模式,需要按着蓝牙模块上的黑色小按钮再上电,这时候模块上的LED灯以一秒慢闪一次…

大数据平台搭建2024(三)

三&#xff1a;HBase安装 提前上传hbase安装包至虚拟机 1 上传、解压 tar -zxvf hbase-2.0.0-alpha2-bin.tar.gz -C /hadoop2 修改配置文件 在/hadoop/hbase-2.0.0-alpha2-bin/conf文件夹里 vi /hadoop/hbase-2.0.0-alpha2/conf/hbase-env.sh修改hbase-env.sh文件 export…

错误分析 (Machine Learning研习十九)

错误分析 您将探索数据准备选项&#xff0c;尝试多个模型&#xff0c;筛选出最佳模型&#xff0c;使用 Grid SearchCV微调其超参数&#xff0c;并尽可能实现自动化。在此&#xff0c;我们假设您已经找到了一个有前途的模型&#xff0c;并希望找到改进它的方法。其中一种方法就…

基于java+springboot+vue实现的健身俱乐部系统(文末源码+Lw+ppt)23-49

摘 要 随着社会的发展&#xff0c;健身俱乐部的管理形势越来越严峻。越来越多的用户利用互联网获得信息&#xff0c;健身信息鱼龙混杂&#xff0c;信息真假难以辨别。为了方便用户更好的获得本健身俱乐部管理信息&#xff0c;因此&#xff0c;设计一种安全高效的健身俱乐部网…

React-基础语法学习

1、教程&#xff1a;井字棋游戏 本教程将引导你逐步实现一个简单的井字棋游戏&#xff0c;并且不需要你对 React 有任何了解。在此过程中你会学习到一些编写 React 程序的基本知识&#xff0c;完全理解它们可以让你对 React 有比较深入的理解。 1.1、教程分成以下几个部分&am…

计算机视觉动作识别——YOWO用于实时时空动作定位与识别的算法解析

摘要 时空动作定位要求将两种信息源整合到设计的架构中&#xff1a;(1) 来自先前帧的时间信息和(2) 来自关键帧的空间信息。当前的最先进方法通常使用单独的网络提取这些信息&#xff0c;并使用额外的机制进行融合以获得检测结果。YOWO是一个用于视频流中实时时空动作定位的统…

宏集eX700M系列HMI实现港口设备数据上云

前言 随着港口设备信息化技术的快速发展&#xff0c;越来越多的企业想要把现场设备数据上传到云平台&#xff0c;进而实现关键数据的远程监控和分析处理。在此背景下&#xff0c;国内某信息化公司想要将港口设备数据通过MQTT上传到该公司自研IOT平台&#xff0c;实现数据上云&…

vue-treeselect 的基本使用

vue-treeselect 的基本使用 1. 效果展示2. 安装 插件3. 引入组件4. 代码 1. 效果展示 2. 安装 插件 vue-treeselect是一个树形的下拉菜单&#xff0c;至于到底有多少节点那就要看你的数据源有多少层了&#xff0c;挺方便的。下面这个这个不用多说吧&#xff0c;下载依赖 npm in…

中兴通讯AI全场景终端新品 赋能行业数智化升级发布 (2)

2024年4月11日&#xff0c;南京&#xff0c;在2024年中兴通讯云网生态峰会召开之际&#xff0c;中兴行业终端合作伙伴大会暨春季新品发布会也同期举行。本次大会主题为“强基拓新&#xff0c;价值创造”&#xff0c;中兴行业终端持续践行合作伙伴优先、深度定制更安全更高效的解…

揭秘ebay、亚马逊测评系统:从稳定环境搭建到防关联技术

在亚马逊、ebay平台上进行自养号测评、L ka等活动&#xff0c;首要问题是确保环境的安全性和稳定性。一个稳定的环境是进行测评的基础&#xff0c;如果无法解决安全性问题&#xff0c;那么从事这些项目就不值得。我们在环境技术研发领域已经有8年的经验&#xff0c;在早期测试了…

连连看游戏页面网站源码,直接使用

可以上传自己喜欢的图片 游戏页面 通关页面 源码免费下载地址抄笔记 (chaobiji.cn)

信号分解 | VMD(变分模态分解)-Matlab

分解效果 VMD(变分模态分解) 变分模态分解(Variational Mode Decomposition,VMD)是一种信号分解方法,用于将非平稳信号分解为一组模态函数。VMD是一种自适应的数据驱动方法,可以有效地处理具有非线性和非平稳特性的信号。 VMD的基本思想是通过迭代优化过程,将原始信号分…

4.16学习总结

MySQL数据库学习(一) 一.MySQL数据库的基本知识 (一).数据库 概念&#xff1a;数据仓库,软件,安装在操作系统之上 作用&#xff1a;存储数据&#xff0c;管理数据 (二).数据库的分类 关系型数据库&#xff1a;SQL&#xff08;Structured Query Language&#xff09; MySQL…

创建k8s deploy yaml文件的imagePullSecrets语句

镜像仓库是harbor kubectl create secret docker-registry key --docker-server192.168.0.190 --docker-usernameadmin --docker-passwordHarbor12345

Fluke ADPT连接器(隔离版)----发布1

代替手工记录、记录后在整理的麻烦&#xff0c;轻点鼠标&#xff08;单次采集、自动时间间隔采集自由选择&#xff09;即可完成&#xff0c;测试数据导出图片、导出数据到EXCEL文件随意选择&#xff1b; 所需设备&#xff1a; 1、Fluke ADPT连接器&#xff1b;内附链接 主要…

docker网路和主机通讯问题

#注 1&#xff0c;安装docker和启动容器服务的时候如果防火墙处于开启状态&#xff0c;那么重启docker里面的容器的时候必须开启防火墙&#xff0c;否则会出现iptable错误&#xff1b; 2&#xff0c;linux开启防火墙会导致主机和docker网络之间单向通讯&#xff0c;主机可以访…

Ubuntu 部署ChatGLM3大语言模型

Ubuntu 部署ChatGLM3大语言模型 ChatGLM3 是智谱AI和清华大学 KEG 实验室联合发布的对话预训练模型。 源码&#xff1a;https://github.com/THUDM/ChatGLM3 部署步骤 1.服务器配置 Ubuntu 20.04 8核(vCPU) 32GiB 5Mbps GPU NVIDIA T4 16GB 硬盘 100GiB CUDA 版本 12.2.2/…