每日两道leetcode
399. 除法求值 - 力扣(LeetCode)
题目
给你一个变量对数组 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
由小写英文字母与数字组成
思路
- 先是一般的逻辑,除法的运算也可以看成一个无向图的计算,假设a/b=x,b/c=y,则a/c=(a/b)*(b/c)=xy。所以利用深度优先搜索的方法,将被除数到除数节点的可行路径找出来,将路径的所有商值向乘即可。
- 因为输入数组给出的是有向图的构造,所以沿用上题的思路将有向图变成无向图,那么就可以直接进行搜索。
- 因为图中有环,所以每轮计算需要建立一个vis集合记录被访问过的节点,每进入下一层,先判断是否是目标节点,如果不是则寻找下一个未被访问节点继续深搜。若找到直接返回,若搜完了都找不到,直接返回-1.0。
- 因为键是string类型,所以需要将上题的vector改为哈希集合unordered_map来存储。
- 最后是特殊情况的判断
- 待计算的节点对中有未曾出现在条件中的未知数,则直接插入-1.0。
- 若是自己除以自己,直接插入1.0。
代码实现
class Solution {
public:double res;unordered_map<string, int> vis;double dfs(string dst, string from, unordered_map<string, unordered_map<string, double>> &rel) {double last;vis[from] = 1;for(auto next : rel[from]) {last = 0.0;if(next.first == dst) return next.second;if(vis[next.first]) continue;last += dfs(dst, next.first, rel);if(last != -1.0) {return next.second * last;}}return -1.0;}vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {string from, to;unordered_map<string, bool> exist;unordered_map<string, unordered_map<string, double>> e;vector<double> ans;for(int i = 0; i < values.size(); i++) {from = equations[i][0];to = equations[i][1];exist[from] = 1;exist[to] = 1;e[from][to] = values[i];if(values[i] != 0) e[to][from] = 1/values[i];}for(int i = 0; i < queries.size(); i++) {from = queries[i][0];to = queries[i][1];if(exist.count(from)==0 || exist.count(to)==0) {ans.push_back(-1.0);}else if(from == to) ans.push_back(1.0);else {ans.push_back(dfs(to, from, e));vis.clear();}}return ans;}
};
复杂度分析
- 时间复杂度:插入条件的时间复杂度为O(c),深搜的最坏时间复杂度为O(V)(V为节点数,取决于每个vis的长度),问题数设为q,则总的时间复杂度为O(c+qV)。
- 空间复杂度:节点间倍数关系的数组的大小为2c(c为条件数),搜索的深度取决于链的长度,最坏空间复杂度为O(c),所以总的空间复杂度为O(c)。
官方题解
- 官方题解里使用并查集的方法,空间复杂度和我的一致,但是时间复杂度据说是O((c+q)logV),那么就来学学(但是好长不想复现了)。
- 其主要思路就是每次在一棵树中加入节点后都通过链的计算将新节点变成与根的关系,并重新变成根的子节点,最后统一完后维持一个高度为2的树——路径压缩。
- 并查集特色:一边查询一边修改。
- 因为官方题解的JAVA实现好像是有内置的并查集结构的,而我看到评论的C++是通过矩阵实现的,空间复杂度变差了,所以暂时不做实现了,我且回去想想怎么实现。
相关文章:
每日两道leetcode
399. 除法求值 - 力扣(LeetCode) 题目 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件,其中 equations[i] [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 …...
在RK3588上使用哪个流媒体服务器合适
在RK3588平台上选择合适的流媒体服务器时,需考虑其ARM Cortex-A76/A55架构、硬件编解码能力(如支持H.264/H.265/AV1解码)以及Linux/Android系统支持。以下是推荐的方案: 1. 轻量级方案:GStreamer RTSP 适用场景&…...
分享一个DeepSeek+自建知识库实现人工智能,智能回答高级用法。
这个是我自己搞的DeepSeek大模型自建知识库相结合到一起实现了更强大的回答问题能力还有智能资源推荐等功能。如果感兴趣的小伙伴可以联系进行聊聊,这个成品已经有了实现了,所以可以融入到你的项目,或者毕设什么的还可以去参加比赛等等。 1.项…...
PyTorch 深度学习实战(38):注意力机制全面解析(从Seq2Seq到Transformer)
在上一篇文章中,我们探讨了分布式训练实战。本文将深入解析注意力机制的完整发展历程,从最初的Seq2Seq模型到革命性的Transformer架构。我们将使用PyTorch实现2个关键阶段的注意力机制变体,并在机器翻译任务上进行对比实验。 一、注意力机制演…...
Android Studio 获取配置资源与第三方包信息详解
文章目录 Android Studio 获取配置资源与第三方包信息详解一、获取资源文件中的配置1. 获取颜色值Java 中获取:Kotlin 中获取: 2. 获取字符串Java 中获取:Kotlin 中获取: 3. 获取尺寸值Java 中获取:Kotlin 中获取&…...
【网络初识】从零开始彻底了解网络编程(一)
本篇博客给大家带来的是网络的知识点. 🐎文章专栏: JavaEE初阶 🚀若有问题 评论区见 ❤ 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作的动力 . 王子,公主请阅🚀 要开心要快乐顺便进步 一. 网络…...
Vivado比特流生成、下载及板级验证操作步骤
1. 前期准备 安装Vivado软件:确保Vivado开发环境已正确安装并配置。创建工程: 打开Vivado,点击“Create Project”新建工程。设置工程名称(例如“led_flow”)和路径。选择目标FPGA型号(例如XC7A35TFFG484&…...
【Flutter DevTools】性能优化的瑞士军刀
一、性能分析:帧率与资源监控 1.1 帧率监控(Performance面板) 通过Performance面板可实时捕获应用的渲染流水线数据。开发者点击"Record"按钮后,DevTools会以时间轴形式展示每一帧的构建、布局、绘制耗时。当帧率低于…...
使用Redis实现实时排行榜
为了实现一个实时排行榜系统,我们可以使用Redis的有序集合(ZSet),其底层通常是使用跳跃表实现的。有序集合允许我们按照分数(score)对成员(member)进行排序,因此非常适合…...
HTML5 应用程序缓存:原理、实践与演进
在 Web 技术的发展历程中,HTML5 引入的应用程序缓存(Application Cache)曾是提升 Web 应用离线体验的重要技术。它允许 Web 应用进行缓存,使用户在没有因特网连接时也能访问应用,为 Web 应用带来了显著的优势。然而&am…...
Compose笔记(十七)--AsyncImage
这一节了解一下Compose中的AsyncImage的使用,AsyncImage是由 Coil库提供的一个用于异步加载图片的组件。它支持加载网络图片、本地图片资源,并提供了占位符、错误处理、过渡动画等功能,简单介绍如下: API 1. model 含义:指定要加…...
Python语法系列博客 · 第7期[特殊字符] 列表推导式与字典推导式:更优雅地处理数据结构
上一期小练习解答(第6期回顾) ✅ 练习1:统计文件行数 with open("data.txt", "r", encoding"utf-8") as f:lines f.readlines()print(f"总行数:{len(lines)}")✅ 练习2:反…...
Redis--主从复制
目录 一、配置 1.1 建立复制 1.2 断开复制 1.3 安全性 1.4 只读 1.5 传输延迟 二、拓扑 2.1 一主一从结构 2.2 一主多从结构 2.3 树形主从结构 在分布式系统中为了解决单点问题,通常会把数据复制多个副本部署到其他服务器,满足故障恢 复和负载均衡等需求…...
FPGA练习———DDS波形发生器
简介:使用DDS波形发生器可以在fpga上生成方波、正弦波等波形,其具体方法是计算相位的变化,然后根据数据表的数值进行数模转化改变波形。 DDS的第一步是生成一个相位加法器 相位加法器 在生成一个波,例如正弦波时,我们…...
力扣面试150题-- 存在重复元素 II和最长连续序列
Day 26 题目描述 思路 定义一个map用来存放每个元素以及它对应的序号从前向后遍历数组如果该元素存在于map(说明满足了重复元素的条件),用当前元素的序号值减去map中存放的序号值(因为是从前遍历的所以当前元素序号一定大于存放…...
卸载Anaconda并保留虚拟环境,重装Anaconda并还原之前的虚拟环境
参考 https://blog.csdn.net/qq_63611690/article/details/134560333 该博文是虚拟环境和Anaconda安装路径在一起 我的是虚拟环境早就搞到了别的盘 问题描述 我之前把Anaconda安装到了C盘,随之时间推移,C盘占用空间越来越大。我想把Anaconda卸载重装…...
ArcGIS及其组件抛出 -- “Sorry, this application cannot run under a Virtual Machine.“
产生背景: 使用的是“破解版本”或“被套壳过”的非官方 ArcGIS 版本 破解版本作者为了防止: 被研究破解方式 被自动化抓包/提权/逆向 被企业环境中部署多机使用 通常会加入**“虚拟化环境检测阻断运行”机制** 原因解释: 说明你当前运…...
Ubuntu 25.04 “Plucky Puffin” 正式发布
Ubuntu 25.04 “Plucky Puffin” 于 2025 年 4 月 17 日正式发布。这是一个短期支持版本,只支持到 2026 年 1 月1。以下是该版本的一些主要新变化: 内核与系统:采用 Linux 6.14 内核;systemd v257.4 带来重要上游更新,…...
2. ubuntu20.04 和VS Code实现 ros的输出 (C++,Python)
本节对应赵虚左ROS书籍的1.4.2 1)创建工作空间 mkdir -p catkin_ws/src cd catkin_ws catkin_make 2) 终端进入VS Code code . 3) vscoe 的基本配置 3.1)修改.vscode/tasks.json ,修改内容如下: { // 有关 tasks.json 格式的文档,请参见…...
0801ajax_mock-网络ajax请求1-react-仿低代码平台项目
0 vite配置proxy代理 vite.config.ts代码如下图所示: import { defineConfig } from "vite"; import react from "vitejs/plugin-react";// https://vite.dev/config/ export default defineConfig({plugins: [react()],server: {proxy: {&qu…...
前端vue+后端ssm项目
下载地址: 前端:https://download.csdn.net/download/2401_83418369/90649449 后端: https://download.csdn.net/download/2401_83418369/90649441 一、项目基础环境搭建 1、新建Maven项目 2、创建目录,结构如下: …...
Python实例题:Python获取阴阳师壁纸
目录 Python实例题 题目 实现思路 代码实现 代码解释 get_wallpaper_links 函数: download_wallpapers 函数: 主程序: 运行思路 注意事项 Python实例题 题目 Python获取阴阳师壁纸 实现思路 发送请求获取网页内容:使…...
考研408操作系统文件管理——4.2目录系统详解
考研408操作系统文件管理——目录系统详解 一、目录管理基本概念 1.1 目录的核心功能 目录是文件系统的核心管理组件,主要实现: 按名存取:通过文件名快速定位物理地址路径解析:将逻辑路径转换为物理块地址共享控制:支持多用户共享同一文件命名空间管理:维护全局唯一的…...
国产SMT贴片机自主技术突破解析
内容概要 随着电子信息产业对精密制造需求的持续升级,国产SMT贴片机的技术突破已成为装备自主化进程的关键节点。本文聚焦设备研发的三大核心领域:高动态运动控制系统通过线性电机与数字信号处理技术的融合,将重复定位精度提升至5μm级别&am…...
Ai Agent 在生活领域的深度应用与使用指南
在科技不断革新的时代,Ai Agent 正以前所未有的态势融入生活的各个角落,成为提升生活品质与效率的得力助手。它凭借强大的智能处理能力,解决了传统生活模式中的诸多痛点,在家庭、出行、健康管理等多个场景中展现出巨大的应用价值…...
CPU与GPU之间的交互
命令队列和命令列表 每个GPU都维护着一个命令队列,本质上是一个环形缓冲区,等待着cpu提交到gpu的命令,同时执行命令 在Direct3D中命令队列被抽象为ID3D12CommandQueue接口来表示。通过下面的方式创建命令队列。 ComPtr<ID3D12CommandQue…...
MySQL运维三部曲初级篇:从零开始打造稳定高效的数据库环境
文章目录 一、服务器选型——给数据库一个舒适的家二、系统调优——打造高性能跑道三、MySQL配置——让数据库火力全开四、监控体系——数据库的体检中心五、备份恢复——数据安全的最后防线六、主从复制——数据同步的艺术七、安全加固——守护数据长城 引言:从小白…...
Python制作简易PDF查看工具PDFViewerV1.0查找功能优化
原文说明 为不破坏原文结构,因此功能优化不在原文中维护了。关于这款工具原文请通过下面链接访问。Python制作简易PDF查看工具PDFViewerV1.0 这款小工具基本功能已经可以作为一款文档浏览器使用,但还有一些美中不足的地方,本文将介绍对文本查…...
MOPSO实现无人机多目标路径规划(Matlab完整源码和数据)
一、MOPSO算法核心原理 MOPSO(多目标粒子群优化算法)通过模拟鸟群觅食行为,在搜索空间中寻找满足多个冲突目标的Pareto最优解集。其核心流程包括: 粒子初始化:随机生成粒子群,每个粒子代表一条候选路径&a…...
Python:使用web框架Flask搭建网站
Date: 2025.04.19 20:30:43 author: lijianzhan Flask 是一个轻量级的 Python Web 开发框架,以简洁灵活著称,适合快速构建中小型 Web 应用或 API 服务。以下是 Flask 的核心概念、使用方法和实践指南 Flask 的核心特点: 轻量级 核心代码仅约…...
芝法酱躺平攻略(21)——kafka安装和使用
本节内容比较初级,故接着躺平攻略写 一、官网的下载 1.1 下载解压 首先,去官网下载jar包,放进linux中,解压到对应位置。 我的位置放在/WORK/MIDDLEWARE/kafka/4.0 1.2 常见配置 # 每个topic默认的分片数 num.properties4 # 数…...
C语言知识复习资料
## 第一章 C语言基本知识 ### 【考点1】C程序 - 用C语言编写的程序称为C语言源程序,源程序文件后缀名为".c" - 源程序经编译后生成后缀名为".obj"的目标文件 - 再把目标文件与各种库函数连接起来,生成后缀名为".exe"可执行文件 - C语言有三…...
CMFA在自动驾驶中的应用案例
CMFA在自动驾驶中的典型应用案例 CMFA(Cross-Modal Feature Alignment)方法在自动驾驶领域有多个成功的应用场景,以下是几个典型案例: 1. 多模态3D目标检测 应用场景:车辆、行人、骑行者等交通参与者的精确检测 …...
进程控制(下)【Linux操作系统】
文章目录 进程程序替换进程替换有关函数和指令函数:execl函数:execv函数:execlp函数:execvp函数:execvpe 进程替换的原理为什么进程替换时,原进程的环境变量不会被覆盖? 进程替换具体会造成什么…...
【后端】【python】Python 爬虫常用的框架解析
一、总结 Python 爬虫常用的框架主要分为 三类: 轻量级请求库:如 requests、httpx,用于快速发请求。解析与处理库:如 BeautifulSoup、lxml、pyquery。爬虫框架系统:如 Scrapy、pyspider、Selenium、Playwright 等&am…...
JDBC 数据库连接全解析:从驱动配置到工具类封装
目录 一. 将MySQL对应版本的jar包放入Java项目中 1. 准备工作 2. 复制到Java项目 二. 获取数据库连接 1. 连接Mysql数据库的URL 2. 连接数据库的用户名 3. 连接数据库的密码 4. 通过反射实例化 三. Properties文件用法 1. properties文件介绍 2. Properties工具类 a.…...
【图片识别分类】如何快速识别照片中的水印文字,对图片进行关键字分类,快速整理水印相机拍摄图片,基于WPF和腾讯OCR的技术实现
项目背景 在施工现场,施工人员通常会使用水印相机拍摄照片,这些照片带有时间、地点、施工阶段等水印信息。为了便于管理和归档,需要快速识别照片中的水印文字,并根据关键字对照片进行分类和整理。 界面设计 界面设计简洁直观&…...
第32讲:卫星遥感与深度学习融合 —— 让地球“读懂”算法的语言
目录 🔍 一、讲讲“遥感+深度学习”到底是干啥的? ✅ 能解决什么问题? 🧠 二、基础原理串讲:深度学习如何“看懂”遥感图? 🛰 遥感图像数据类型: 🧠 CNN的基本思路: 🧪 三、实战案例:用CNN对遥感图像做地类分类 📦 所需R包: 🗂️ 步骤一:构建训…...
Java 静态变量、静态方法及工具类介绍
目录 一、静态变量(Static Variables) 1. 基本概念 2. 核心特性 (1)类级别共享 (2)生命周期 (3)内存分配 3. 使用方法 (1)访问方式 (2)初始化时机 4. 典型应用场景 (1)共享常量 (2)计数器功能 (3)配置信息 二、静态方法(Static …...
【win 1】win 右键菜单添加 idea pycharm vscode trae 打开文件夹
编程时经常需要通过 程序 打开文件夹,有时安装时没注意选上添加到右键菜单,又不想重新安装,有什么方法? 之前教程都是改注册表有点繁琐,这里利用开源的 windows 右键管理软件,可以快捷简单的添加。 右键菜…...
XSS跨站脚本攻击漏洞
目录 一、基本概念 二、XSS分类 1、反射型XSS 2、存储型XSS 3、DOM型XSS 三、手工测试 1、反射型XSS漏洞 (1)安全等级low (2)DOM的XSS (3)安全等级medium (4)安全等级hig…...
TensorFlow 实现 Mixture Density Network (MDN) 的完整说明
本文档详细解释了一段使用 TensorFlow 构建和训练混合密度网络(Mixture Density Network, MDN)的代码,涵盖数据生成、模型构建、自定义损失函数与预测可视化等各个环节。 1. 导入库与设置超参数 import numpy as np import tensorflow as t…...
servlet-服务器内部转发和客户端重定向
服务器内部转发以及客户端重定向 服务器内部转发以及客户端重定向1)服务器内部转发:request.getRequestDispatcher("...").forward(request,response);--- 一次请求响应的过程,对于客户端而言,内部转发多少次ÿ…...
手动实现LinkedList
前言 大家好,我是Maybe。最近在学习数据结构中的链表,自己手动实现了一个LinkedList。我想与大家分享一下。 思维导图 代码部分 package Constant;public class constant {public static final String INDEX_IS_WRONG"输入的下标不合法"; }p…...
实现AWS Step Function安全地请求企业内部API返回数据
需要编写一个Step Function在AWS云上运行,它需要访问企业内部的API获取JSON格式的数据,企业有网关和防火墙,API有公司的okta身份认证,通过公司的域账号来授权访问,现在需要创建一个专用的域账号,让Step Fun…...
掌握 MySQL:从命令行操作到数据类型与字段管理
掌握 MySQL:从命令行操作到数据类型与字段管理 MySQL 作为全球最流行的开源关系型数据库管理系统,广泛应用于 Web 开发、数据分析和企业级应用中。无论是初学者还是资深开发者,掌握 MySQL 的基本命令行操作、了解其数据库类型、数据类型、字…...
基于大语言模型的自动化单元测试生成系统及测试套件评估方法
A System for Automated Unit Test Generation Using Large Language Models and Assessment of Generated Test Suites 翻译于上述论文 基于大语言模型的自动化单元测试生成系统及测试套件评估方法 摘要 单元测试是软件测试生命周期中最基础的测试层级,对确保软…...
使用vue2技术写了一个纯前端的静态网站商城-鲜花销售商城
先给大家看一下网站的整体效果截图: 这个前端静态网站项目主要实现了以下功能: 商城首页、商品分类页、登录注册页、个人中心页、我的收藏页、我的订单页、商品详情页等功能。 最近不是在学习前端开发嘛,肯定要做一些项目来练习以下自己学…...
PyTorch深度学习框架60天进阶学习计划 - 第46天:自动化模型设计(一)
PyTorch深度学习框架60天进阶学习计划 - 第46天:自动化模型设计(一) 第一部分:使用ENAS算法生成图像分类网络 大家好!欢迎来到我们PyTorch深度学习框架60天进阶学习计划的第46天。今天我们要深入探讨一个话题——使用…...
【上海大学计算机系统结构实验报告】多机环境下MPI并行编程
实验目的 学习编制多进程并行程序实现如下功能: 创建多进程,输出进程号和进程数。运行多进程并行例子程序。编程实现大规模矩阵的并行计算。 实验过程及结果分析 实验环境 操作系统:Ubuntu 20.04开发工具:GCC 9.3.0、OpenMPI…...