当前位置: 首页 > 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;为网络赌博…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...