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

LeetCode2115. 从给定原材料中找到所有可以做出的菜

拓扑排序

题面

题目链接:2115. 从给定原材料中找到所有可以做出的菜 - 力扣(LeetCode)

你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ,如果你有它 所有 的原材料 ingredients[i] ,那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜,也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。

同时给你一个字符串数组 supplies ,它包含你初始时拥有的所有原材料,每一种原材料你都有无限多。

请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。

注意两道菜在它们的原材料中可能互相包含。

解题思路

做出一个菜,可以由这个菜作为原料做出另一个,且原料无限

很容易幻想出一个有向图,从原料指向各个目标菜,而拥有公共原料,且之间存在互相作为原料的情况则可以看作图的后序

了解过或者学习过拓扑排序的,到这里应该就能判断谁作为队列的初始元素了

但是题目给出的是原料有哪些,需要做的菜有哪些,它们又各自需要哪些作为原料

所以我们需要用哈希表存储这些关系,避免大量重复的遍历寻找

哈希表1:一个原料能做出哪些菜

哈希表2:一个菜的入度为几(因为每个元素都为string类型,所以也是需要用哈希表)

拓扑排序套路写法

class Solution {
public:vector<string> findAllRecipes(vector<string>& recipes,vector<vector<string>>& ingredients,vector<string>& supplies) {unordered_map<string, int> indegree;unordered_map<string, vector<string>> out;queue<string> q;vector<string> ans;for (string i : supplies)q.push(i);for (int i = 0; i < recipes.size(); i++) {indegree[recipes[i]] = ingredients[i].size();for(string var:ingredients[i]){out[var].push_back(recipes[i]);}}while (!q.empty()) {string now = q.front();q.pop();for(string aim:out[now]){if(--indegree[aim]==0){ans.push_back(aim);q.push(aim);}}}return ans;}
};

相关文章:

LeetCode2115. 从给定原材料中找到所有可以做出的菜

拓扑排序 题面 题目链接&#xff1a;2115. 从给定原材料中找到所有可以做出的菜 - 力扣&#xff08;LeetCode&#xff09; 你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] &#xff0c;如果你有它 所有…...

项目性能优化—性能优化的指标、目标

项目性能优化—性能优化的指标、目标 性能优化的终极目标是什么 性能优化的目标实际上是为了更好的用户体验&#xff1a; 一般我们认为用户体验是下面的公式&#xff1a; 用户体验 产品设计&#xff08;非技术&#xff09; 系统性能 ≈ 系统性能 快 那什么样的体验叫快呢…...

蓝桥杯刷题(三)

一、P8752 [蓝桥杯 2021 省 B2] 特殊年份&#xff08;洛谷&#xff09; 题目描述 今年是 2021 年&#xff0c;2021 这个数字非常特殊, 它的千位和十位相等, 个位比百位大 1&#xff0c;我们称满足这样条件的年份为特殊年份。 输入 5 个年份&#xff0c;请计算这里面有多少个…...

20240312-算法复习打卡day21||● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

530.二叉搜索树的最小绝对差 1.中序遍历得到升序数组 class Solution { private:vector<int> vec;void traversal(TreeNode* root) {if (root NULL) return;if (root->left) traversal(root->left);vec.push_back(root->val);if (root->right) traversal(r…...

今天我们来学习一下关于MySQL数据库

目录 前言: 1.MySQL定义&#xff1a; 1.1基础概念&#xff1a; 1.1.1数据库&#xff08;Database&#xff09;&#xff1a; 1.1.2表&#xff08;Table&#xff09;&#xff1a; 1.1.3记录&#xff08;Record&#xff09;与字段&#xff08;Field&#xff09;&#xff1a; …...

长期护理保险可改善老年人心理健康 | CHARLS CLHLS CFPS 公共数据库周报(3.6)...

欢迎报名2024年“真实世界临床研究”课程&#xff01; 本周郑老师开讲&#xff1a;“真实世界临床研究”培训班&#xff0c;3月16-17日两天&#xff0c;欢迎报名&#xff01; CHARLS公共数据库‍ CHARLS数据库简介中国健康与养老追踪调查(China Health and Retirement Longitud…...

49、C++/友元、常成员函数和常对象、运算符重载学习20240314

一、封装类 用其成员函数实现&#xff08;对该类的&#xff09;数学运算符的重载&#xff08;加法&#xff09;&#xff0c;并封装一个全局函数实现&#xff08;对该类的&#xff09;数学运算符的重载&#xff08;减法&#xff09;。 代码&#xff1a; #include <iostream…...

SQL Server错误:15404

执行维护计划失败&#xff0c;提示SQL Server Error 15404 无法获取有关... 异常如下图&#xff1a; 原因&#xff1a;数据库用户名与计算机名称不一致 解决办法&#xff1a;1.重名称数据库用户名 将前缀改成计算机名 2.重启SQL Server代理...

Halcon文件操作

1、Region读写操作 region&#xff08;区域&#xff09;是一种重要的数据类型&#xff0c;用于表示图像中的特定区域。这些区域可以代表图像中的目标、感兴趣的区域、边缘、形状等等 read_image (Image, printer_chip/printer_chip_01) dev_open_window (0, 0, 512, 512, black…...

【测试知识】业务面试问答突击版1

高内聚低耦合 高内聚指的是将相关的功能或数据组织在一起&#xff0c;使得模块内部的各个元素紧密地联系在一起&#xff0c;完成特定的任务。 低耦合指的是模块之间的依赖关系尽可能地降低&#xff0c;模块之间的接口简单清晰&#xff0c;减少模块之间的相互影响。 文章目录 整…...

使用el-row及el-col页面缩放时出现空行解决方案

问题&#xff1a; 当缩放到90%或者110%&#xff0c;选中下拉后&#xff0c;下方就会出现空行 如下图所示&#xff1a; 关于el-row 和 el-col &#xff1a; 参数说明类型可选值默认值span栅格占据的列数number—24offset栅格左侧的间隔格数number—0push栅格向右移动格数number…...

java中几种对象存储(文件存储)中间件的介绍

一、前言 在博主得到系统中使用的对象存储主要有OSS&#xff08;阿里云的对象存储&#xff09; COS&#xff08;腾讯云的对象存储&#xff09;OBS&#xff08;华为云的对象存储&#xff09;还有就是MinIO 这些玩意。其实这种东西大差不差&#xff0c;几乎实现方式都是一样&…...

网络工程师——2024自学

一、怎样从零开始学习网络工程师 当今社会&#xff0c;人人离不开网络。整个IT互联网行业&#xff0c;最好入门的&#xff0c;网络工程师算是一个了。 什么是网络工程师呢&#xff0c;简单来说&#xff0c;就是互联网从设计、建设到运行和维护&#xff0c;都需要网络工程师来…...

SwiftUI的Picker

SwiftUI的Picker 本章来记录一下SwiftUI中三种不同Picker的用法 &#xff0c;分别为normalPicker &#xff0c; wheelPicker&#xff0c; segmentedPicker 。可以根据不同需求展示不同的Picker import SwiftUIstruct PickerBootCamp: View {State var selection: String &quo…...

物联网技术助力智慧城市转型升级:智能、高效、可持续

目录 一、物联网技术概述及其在智慧城市中的应用 二、物联网技术助力智慧城市转型升级的路径 1、提升城市基础设施智能化水平 2、推动公共服务智能化升级 3、促进城市治理现代化 三、物联网技术助力智慧城市转型升级的成效与展望 1、成效显著 2、展望未来 四、物联网技…...

YOLOv7_pose-Openvino和ONNXRuntime推理【CPU】

纯检测系列&#xff1a; YOLOv5-Openvino和ONNXRuntime推理【CPU】 YOLOv6-Openvino和ONNXRuntime推理【CPU】 YOLOv8-Openvino和ONNXRuntime推理【CPU】 YOLOv7-Openvino和ONNXRuntime推理【CPU】 YOLOv9-Openvino和ONNXRuntime推理【CPU】 跟踪系列&#xff1a; YOLOv5/6/7-O…...

通过ACPI检测沙箱-反虚拟机

ACPI & ACPI table ACPI 表示高级配置和电源管理接口&#xff08;Advanced Configuration and Power Management Interface&#xff09;&#xff0c;对于Windows2000&#xff0c;ACPI定义了Windows2000、BIOS和系统硬件之间的新型工作接口。这些新接口包括允许Windows 200…...

计算点集的最小外接矩形——OpenCV的minAreaRect函数

计算点集的最小外接矩形——OpenCV的minAreaRect函数 函数原型 输入一系列二维点&#xff0c;返回其最小外接矩形。 RotatedRect minAreaRect( InputArray points );根据函数原型&#xff0c;输入的数据可以是vector<Point>类型&#xff0c;包含1个以上的点&#xff1…...

Stripe Web 购买集成

图片被吞了可以来这里看&#xff1a;https://juejin.cn/post/7346388511338381364 1. 准备事项 Stripe 账号域名以及配套的网站Stripe 账号付款信息公钥和私钥 2. 配置产品以及价格 可以通过 API 或者 Stripe 管理后台来进行配置 产品&#xff1a;就是商品&#xff0c;只需…...

加密货币在网络违法犯罪活动中的利用情况调查

一、调查背景 区块链基于分布式共识和经济激励等手段&#xff0c;在开放式、无许可的网络空间中&#xff0c;为价值的确立、存储、转移提供了新的解决方案。然而随着加密生态在过去若干年的快速发展&#xff0c;加密货币也越来越多地被用于各类风险活动&#xff0c;为网络赌博…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

【java面试】微服务篇

【java面试】微服务篇 一、总体框架二、Springcloud&#xff08;一&#xff09;Springcloud五大组件&#xff08;二&#xff09;服务注册和发现1、Eureka2、Nacos &#xff08;三&#xff09;负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...