当前位置:网站首页>leetcode-399: division evaluation
leetcode-399: division evaluation
2022-07-31 01:44:00 【chrysanthemum bat】
题目
给你一个变量对数组 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 的情况,且不存在任何矛盾的结果.
示例 1:
输入:equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出:[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释:
条件:a / b = 2.0, b / c = 3.0
问题:a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果:[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2:
输入:equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出:[3.75000,0.40000,5.00000,0.20000]
示例 3:
输入:equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出:[0.50000,2.00000,-1.00000,-1.00000]
解题
方法一:并查集
Building a weighted directed graph+并查集
class UnionFind{
private:
vector<int> parent;
vector<double> weight;
public:
UnionFind(int n){
parent.resize(n);
weight.resize(n);
for(int i=0;i<n;i++){
parent[i]=i;
weight[i]=1;
}
}
int find(int index){
if(index==parent[index]) return index;
int origin=parent[index];
parent[index]=find(parent[index]);//At the same time, the parent node will be displayedweight也更新好
weight[index]*=weight[origin];
return parent[index];
}
void unite(int index1,int index2,double value){
int p1=find(index1);
int p2=find(index2);
if(p1!=p2){
parent[p1]=p2;
weight[p1]=weight[index2]*value/weight[index1];
}
}
double isConnected(int index1,int index2){
int p1=find(index1);
int p2=find(index2);
if(p1==p2){
return weight[index1]/weight[index2];
}
else return -1;
}
};
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
int equationSize=equations.size();
UnionFind uf(2*equationSize);
// 第 1 步:预处理,将变量的值与 id 进行映射,使得并查集的底层使用数组实现,方便编码
unordered_map<string,int> mp;
int id=0;
for(int i=0;i<equationSize;i++){
vector<string> equation=equations[i];
string s1=equation[0];
string s2=equation[1];
if(!mp.count(s1)){
mp[s1]=id++;
}
if(!mp.count(s2)){
mp[s2]=id++;
}
uf.unite(mp[s1],mp[s2],values[i]);
}
// 第 2 步:做查询
int queriesSize=queries.size();
vector<double> res(queriesSize);
for(int i=0;i<queriesSize;i++){
string s1=queries[i][0];
string s2=queries[i][1];
if(!mp.count(s1)||!mp.count(s2)) res[i]=-1;
else res[i]=uf.isConnected(mp[s1],mp[s2]);
}
return res;
}
};
边栏推荐
- 软件测试要达到一个什么水平才能找到一份9K的工作?
- 程序员转正述职报告/总结
- 87. Convert String to Integer
- Distributed. Idempotency
- MySql installation and configuration super detailed tutorial and simple method of building database and table
- 蛮力法/邻接表 广度优先 有向带权图 无向带权图
- 最高月薪20K?平均薪资近万...在华为子公司工作是什么体验?
- Crawler text data cleaning
- 初识C语言 -- 数组
- The PC side determines the type of browser currently in use
猜你喜欢
最高月薪20K?平均薪资近万...在华为子公司工作是什么体验?
MySQL installation tutorial (detailed, package teaching package~)
九州云获评云计算标准化优秀成员单位
【genius_platform软件平台开发】第七十四讲:window环境下的静态库和动态库的一些使用方法(VC环境)
221. 最大正方形
Bert usage and word prediction based on Keras_bert model
软件测试报告有哪些内容?
pycharm重命名后无法运行(报错: can‘t open file......No such file or directory)
12张图带你彻底搞懂服务限流、熔断、降级、雪崩
1.非类型模板参数 2.模板的特化 3.继承讲解
随机推荐
想要写出好的测试用例,先要学会测试设计
android的webview缓存相关知识收集
934. 最短的桥
Shell 脚本循环遍历日志文件中的值进行求和并计算平均值,最大值和最小值
打印任务排序 js od华为
ROS Action通信
数字图像隐写术之卡方分布
第一学年课程期末考试
Know what DTU is 4GDTU equipment
【Mysql】——索引的深度理解
leetcode-952:按公因数计算最大组件大小
成为比开发硬气的测试人,我都经历了什么?
What is the ideal college life?
Dispatch Center xxl-Job
【微信小程序】一文带你了解数据绑定、事件绑定以及事件传参、数据同步
leetcode-128:最长连续序列
Bert usage and word prediction based on Keras_bert model
ROS Action communication
【网络安全】文件上传靶场通关(1-11关)
Likou Daily Question - Day 46 - 704. Binary Search