当前位置: 首页 > news >正文

399. 除法求值【 力扣(LeetCode) 】

文章目录

  • 零、LeetCode 原题
  • 一、题目描述
  • 二、测试用例
  • 三、解题思路
    • 3.1 图的路径搜索
    • 3.2 路径压缩
  • 四、参考代码
    • 4.1 图的路径搜索
    • 4.2 路径压缩

零、LeetCode 原题


399. 除法求值

一、题目描述

给你一个变量对数组 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 ]
注意:x 是未定义的 => -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]

提示:

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj 由小写英文字母与数字组成

三、解题思路

3.1 图的路径搜索

  1. 基本思路:
      如果将每个 equations 看作 边 ,value 看作 边权,则 queries 相当于查询某条路径的权重和。
  2. 具体思路:
    • 构建有向图
    • 路径搜索
      • 如果顶点不存在,则存入 -1 ;
      • 如果顶点相同,则存入 1;
      • 使用深度搜索进行路径搜索,查找该路径并计算权重累加和。

3.2 路径压缩

  1. 基本思路:
      就在上一个方法的基础上,进行路径压缩即可。每搜索完一个,将结果保存。
  2. 具体思路:
      同上,在最后一步搜索完路径时,保存结果,可以作为下次搜索使用。

四、参考代码

4.1 图的路径搜索

时间复杂度: O ( k ∣ E ∣ ) \Omicron(k|E|) O(kE)【查找 k 条路径,每条路径最坏情况就是遍历所有的边】
空间复杂度: O ( ∣ E ∣ ) \Omicron(|E|) O(E)【使用空间有:图的边,图的顶点(最坏2倍边的空间),递归深度(最坏遍历所有边),已搜索顶点集合(最坏搜索过所有顶点)】

class Solution {
public:unordered_map<string, unordered_map<string, double>> m;double dfs(string now, string obj, unordered_set<string>& used) {if (m.count(now) == 0)return 0;if (m[now].count(obj))return m[now][obj];for (const auto& next : m[now]) {if (used.count(next.first))continue;used.emplace(next.first);auto ans = dfs(next.first, obj, used);if (ans)return ans * next.second;}return 0;}vector<double> calcEquation(vector<vector<string>>& equations,vector<double>& values,vector<vector<string>>& queries) {vector<double> ans;for (int i = 0; i < equations.size(); i++) {m[equations[i][0]].emplace(equations[i][1], values[i]);m[equations[i][1]].emplace(equations[i][0], 1 / values[i]);}for (int i = 0; i < queries.size(); i++) {if (m.count(queries[i][0]) == 0 || m.count(queries[i][1]) == 0) {ans.emplace_back(-1.0);} else if (queries[i][0] == queries[i][1]) {ans.emplace_back(1.0);} else {unordered_set<string> used;ans.emplace_back(dfs(queries[i][0], queries[i][1], used));if (ans.back() == 0.0)ans.back() = -1.0;}}return ans;}
};

4.2 路径压缩

时间复杂度: O ( k α ( ∣ E ∣ ) ) \Omicron(k\alpha(|E|)) O(kα(E)) α ( n ) \alpha(n) α(n) 是一个增长很慢的函数,其值都不超过 4】
空间复杂度: O ( ∣ E ∣ ) \Omicron(|E|) O(E)

class Solution {
public:unordered_map<string, unordered_map<string, double>> m;double dfs(string now, string obj, unordered_set<string>& used) {if (m.count(now) == 0)return 0;if (m[now].count(obj))return m[now][obj];for (const auto& next : m[now]) {if (used.count(next.first))continue;used.emplace(next.first);auto ans = dfs(next.first, obj, used);if (ans)return ans * next.second;}return 0;}vector<double> calcEquation(vector<vector<string>>& equations,vector<double>& values,vector<vector<string>>& queries) {vector<double> ans;for (int i = 0; i < equations.size(); i++) {m[equations[i][0]].emplace(equations[i][1], values[i]);m[equations[i][1]].emplace(equations[i][0], 1 / values[i]);}for (int i = 0; i < queries.size(); i++) {if (m.count(queries[i][0]) == 0 || m.count(queries[i][1]) == 0) {ans.emplace_back(-1.0);} else if (queries[i][0] == queries[i][1]) {ans.emplace_back(1.0);} else {unordered_set<string> used;ans.emplace_back(dfs(queries[i][0], queries[i][1], used));if (ans.back() == 0.0)ans.back() = -1.0;else{ // 保存结果m[queries[i][0]].emplace(queries[i][1],ans.back()); m[queries[i][1]].emplace(queries[i][0],1/ans.back()); }}}return ans;}
};

相关文章:

399. 除法求值【 力扣(LeetCode) 】

文章目录 零、LeetCode 原题一、题目描述二、测试用例三、解题思路3.1 图的路径搜索3.2 路径压缩 四、参考代码4.1 图的路径搜索4.2 路径压缩 零、LeetCode 原题 399. 除法求值 一、题目描述 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件&#xff0c;…...

算法日记1:洛谷p2678跳石头(二分答案)

1、题目 二、题解&#xff1a; 2.1解题思路: 1.题目要求求出最小值最大&#xff0c;明显的二分答案题目&#xff0c;所以我们可以二分可以跳跃距离int l-1,rL1; 2.此时我们思考lmid和rmid的处理,当我们的check(mid)为true时候 表明我们此时的mid是符合要求的&#xff0c; 那么…...

Unity shader中真的可以动态关闭Stencil Test吗?

这个问题很多年前就有人问了&#xff1a; https://discussions.unity.com/t/how-to-disable-the-stencil-block-via-shader-properties/600273/1 最后的答案是&#xff1a; set [_StencilComp] to CompareFunction.Disabled to disable the Stencil Op completely. 但是我测试…...

YOLOv9改进,YOLOv9自研检测头融合HyCTAS的Self_Attention自注意力机制,2024,适合目标检测、分割任务

摘要 论文提出了一种新的搜索框架,名为 HyCTAS,用于在给定任务中自动搜索高效的神经网络架构。HyCTAS框架结合了高分辨率表示和自注意力机制,通过多目标优化搜索,找到了一种在性能和计算效率之间的平衡。 # 理论介绍 自注意力(Self-Attention)机制是HyCTAS框架中的一个…...

计算机网络 (36)TCP可靠传输的实现

前言 TCP&#xff08;传输控制协议&#xff09;是一种面向连接的、可靠的、基于字节流的传输层通信协议。TCP通过多种机制实现可靠传输&#xff0c;这些机制主要包括连接管理、序列号和确认应答机制、重传机制、流量控制、拥塞控制等。 一、连接管理 TCP使用三次握手&#xff0…...

Git版本控制 - 创建使用Repository

Git版本控制 – 创建使用Repository Version Control with Git - Create and Use Repository By JacksonML 上文提到&#xff0c;Git是一种分布式版本控制系统。作为全球范围内广泛使用的工具&#xff0c;如何将项目分步骤运用到其中呢&#xff1f; 本文简要介绍如何用Git工…...

MySQL —— 在CentOS9下安装MySQL

MySQL —— 在CentOS9下安装MySQL 1.查看自己操作系统的版本2.找到对应的安装源3.上传我们在windows下&#xff0c;下载的文件&#xff0c;解压4.执行rpm命令&#xff0c;启用MySQL8仓库5.执行dnf install -y mysql-community-server6.设置开机自启动7.获得初始密码8.登录MySQL…...

LeetCode 热题 100_腐烂的橘子(52_994_中等_C++)(图;广度优先遍历(队列))

LeetCode 热题 100_腐烂的橘子&#xff08;52_994&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;广度优先遍历&#xff08;队列&#xff09;&#xff09;&#xff1a; 代码实现代码实现&#xff08;思路一…...

Nginx 可观测性最佳实践

Nginx 介绍 Nginx 是一个开源、轻量级、高性能的 HTTP 和反向代理服务器&#xff0c;也可以用于 IMAP/POP3 代理服务器。Nginx 因其采用的异步非阻塞工作模型&#xff0c;使其具备高并发、低资源消耗的特性。高度模块化设计也使得 Nginx 具备很好的扩展性&#xff0c;在处理静…...

LabVIEW光流跟踪算法

1. 光流跟踪算法的概述 光流&#xff08;Optical Flow&#xff09;是一种图像处理技术&#xff0c;用于估算图像中像素点的运动。通过比较连续帧图像&#xff0c;光流算法可以分析图像中的运动信息&#xff0c;广泛用于目标跟踪、运动检测和视频处理等场景。该示例使用了NI Vi…...

Jira用例自动去除summary重复用例

title: Jira用例自动去除summary重复用例 tags: - jira - python categories: - python一、背景与需求二、解决方案思路三、实施步骤本文永久更新地址: 在使用 Jira 进行项目管理时&#xff0c;测试用例的维护至关重要。随着项目推进&#xff0c;用例数量增多&#xff0c;可能…...

基于openEuler22.03SP4部署Prometheus+Grafana

测试环境 Virtual Box&#xff0c;openEuler-22.03-LTS-SP4-x86_64-dvd.iso&#xff0c;4 vCPU, 8G RAM, 60 vDisk。最小化安装。需联网。 系统环境 关闭防火墙 systemctl stop firewalld systemctl disable firewalld systemctl status firewalld selinux关闭 sed -ri…...

泛目录和泛站有什么差别

啥是 SEO 泛目录&#xff1f; 咱先来说说 SEO 泛目录是啥。想象一下&#xff0c;你有一个巨大的图书馆&#xff0c;里面的书架上摆满了各种各样的书&#xff0c;每一本书都代表着一个网页。而 SEO 泛目录呢&#xff0c;就像是一个超级图书管理员&#xff0c;它的任务就是把这些…...

css 布局及动画应用(flex+transform+transition+animation)

文章目录 css 布局及动画应用animationtransform&#xff0c;transition&#xff0c;animation 综合应用实例代码实例解释 css 布局及动画应用 Display用法 作用&#xff1a;用于控制元素的显示类型&#xff0c;如块级元素、内联元素、无显示等。常见属性值及示例&#xff1a;…...

springboot vue uniapp 仿小红书 1:1 还原 (含源码演示)

线上预览: 移动端 http://8.146.211.120:8081/ 管理端 http://8.146.211.120:8088/ 小红书凭借优秀的产品体验 和超高人气 目前成为笔记类产品佼佼者 此项目将详细介绍如何使用Vue.js和Spring Boot 集合uniapp 开发一个仿小红书应用&#xff0c;凭借uniapp 可以在h5 小程序 app…...

lombok在高版本idea中注解不生效的解决

环境&#xff1a; IntelliJ IDEA 2024.3.1.1 Spring Boot Maven 问题描述 使用AllArgsConstructor注解一个用户类&#xff0c;然后调用全参构造方法创建对象&#xff0c;出现错误&#xff1a; java: 无法将类 com.itheima.pojo.User中的构造器 User应用到给定类型; 需要:…...

跨境电商领域云手机之选:亚矩阵云手机的卓越优势

在跨境电商蓬勃发展的当下&#xff0c;云手机已成为众多企业拓展海外市场的得力助手。亚矩阵云手机凭借其独特优势&#xff0c;在竞争激烈的云手机市场中崭露头角。不过&#xff0c;鉴于市场上云手机服务供应商繁多&#xff0c;企业在抉择时需对诸多要素予以审慎考量。 跨境电商…...

Linux第二课:LinuxC高级 学习记录day02

2.4、shell中的特殊字符 2.4.4、命令置换符 或者 $() 反引号&#xff1a;esc下面的按键&#xff0c;英文状态下直接按 功能&#xff1a;将一个命令的输出作为另一个命令的参数 echo 不会认为hostname是一个命令 加上 之后&#xff0c;先执行hostname&#xff0c;拿到主机名…...

6. NLP自然语言处理(Natural Language Processing)

自然语言是指人类日常使用的语言&#xff0c;如中文、英语、法语等。 自然语言处理是人工智能&#xff08;AI&#xff09;领域中的一个重要分支&#xff0c;它结合了计算机科学、语言学和统计学的方法&#xff0c;通过算法对文本和语音进行分析&#xff0c;使计算机能够理解、解…...

win10电脑 定时关机

win10电脑 定时关机 https://weibo.com/ttarticle/p/show?id2309405110707766296723 二、使用任务计划程序设置定时关机打开任务计划程序&#xff1a; 按下“Win S”组合键&#xff0c;打开搜索框。 在搜索框中输入“任务计划程序”&#xff0c;然后点击搜索结果中的“任务…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

嵌入式面试常问问题

以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...