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

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

思路:拓补排序,哈希表

在思路上其实很好发现,我们需要有一个明确的做菜顺序,也就是说需要定下来我们根据原材料先做哪些菜,然后做完该做的菜之后,后来又能做哪些菜。

你也发现了,这个顺序其实就是拓补排序的顺序,我们构造出来这样的一个图就行了,虽然说处理起来很麻烦....需要用到哈希表进行映射才行。

这里哈希表用了两个,一个是用来构建拓补排序的图的,一个是用来存储入度的,因为我们需要判断哪个可以先开始制作。

OK,构造出来做菜的顺序了,也与处理完了入度,我们首先开始下手的肯定是原材料,因为原材料肯定入度为0,这是题目中推出的信息,只有菜谱上的菜之间才可能会有入度。

在处理完原材料之后,减去对应的入度之后,我们开始判断食谱。

注意,食谱这里你需要经过多次循环才能说得出结果,根据数据范围定义循环的次数,因为我们在每一次遍历完数组之后,可能会有原先入度不是0但是遍历完之后入度为0的情况出现,所以这里需要多次对于数组进行遍历。

class Solution {
public:vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {map<string,int>m;map<string,vector<string>>s;for(int i=0;i<recipes.size();i++)m[recipes[i]]=0;for(int i=0;i<ingredients.size();i++){for(int j =0;j<ingredients[i].size();j++){m[ingredients[i][j]]=0;}}for(int i=0;i<recipes.size();i++){for(int j=0;j<ingredients[i].size();j++){s[ingredients[i][j]].push_back(recipes[i]);}m[recipes[i]]+=ingredients[i].size();}vector<string>res;for(int i=0;i<supplies.size();i++){if(m[supplies[i]]==0){for(int j=0;j<s[supplies[i]].size();j++){m[s[supplies[i]][j]]--;}}}vector<bool>st(recipes.size(),false);int i=0;int n=1e5;while(n--){if(m[recipes[i]]==0&&!st[i]){res.push_back(recipes[i]);st[i]=true;for(int j=0;j<s[recipes[i]].size();j++){m[s[recipes[i]][j]]--;}}i=(i+1)%recipes.size();}return res;}
};

上代码:

相关文章:

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

思路&#xff1a;拓补排序&#xff0c;哈希表 在思路上其实很好发现&#xff0c;我们需要有一个明确的做菜顺序&#xff0c;也就是说需要定下来我们根据原材料先做哪些菜&#xff0c;然后做完该做的菜之后&#xff0c;后来又能做哪些菜。 你也发现了&#xff0c;这个顺序其实…...

Opencompass模型评测教程

模型评测 模型评测非常关键&#xff0c;目前主流的方法主要可以概括为主观评测和客观评测&#xff0c;主观评测又可以分为两种形式&#xff1a;人工判断或者和模型竞技场。客观评测一般采用评测数据集的形式进行模型评测。本教程使用Opencompass工具进行对Internlm2-7b模型进行…...

什么是安全测试,如何进行安全测试?

什么是安全测试&#xff1f; 概述 安全测试是一种旨在识别系统、网络或应用程序中的安全漏洞的测试方法。其目标是确保系统能够抵御恶意攻击&#xff0c;保护数据的机密性、完整性和可用性。安全测试通常包括漏洞扫描、渗透测试、代码审计和安全评估等多个方面。 安全测试的…...

ros的pcl库中对于自己定义的消息,调用pcl库时总是报错 c++

首先定义自己的消息类型 struct CustomPoint { // 定义点类型结构PCL_ADD_POINT4D; // 该点类型有4个元素float intensity 0.0;uint32_t zone;uint32_t ring;uint32_t sector;EIGEN_MAKE_ALIGNED_OPERATOR_NEW // 确保new操作符对齐操作 } EIGEN_ALIGN16; // 强制SSE对齐POIN…...

DataFrame—数据汇总6

文章最前&#xff1a; 我是Octopus&#xff0c;这个名字来源于我的中文名--章鱼&#xff1b;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github &#xff1b;这博客是记录我学习的点点滴滴&#xff0c;如果您对 Python、Java、AI、算法有兴趣&#xff0c;可以关注我的…...

Java入门基础学习笔记41——实体类

实体JavaBean/实体类&#xff1a; 就是一种特殊形式的类。 1&#xff09;这个类中的成员变量都要私有&#xff0c;并且要对外提供相应的getXXX&#xff0c;setXXX的方法。 2&#xff09;类中必须要有一个公共的无参的构造器。其他的构造器可写可不写。 右键菜单中&#xff0…...

【Linux】信号之信号的保存和处理详解

&#x1f916;个人主页&#xff1a;晚风相伴-CSDN博客 &#x1f496;如果觉得内容对你有帮助的话&#xff0c;还请给博主一键三连&#xff08;点赞&#x1f49c;、收藏&#x1f9e1;、关注&#x1f49a;&#xff09;吧 &#x1f64f;如果内容有误或者有写的不好的地方的话&…...

基于Django的图书管理系统

文章目录 前言一、页面展示1.登录2.前端页面3.后端页面 二、项目上传&#xff08;1&#xff09;导入数据库&#xff08;2&#xff09;导入项目&#xff08;3&#xff09;数据库密码修改&#xff08;4&#xff09;进入网站 总结 前言 本网站调用Django编写了图书管理网站&#…...

js实现元素根据鼠标滚轮滚动向左右上下滑动着从模糊到清楚显示出来

html代码 <div ref{test} id"animatedElement" className"not-animated"> <div style{{width:"100px",height:"50px",backgroundColor:"red"}}> </div> </div> JS代码 const te…...

yocto学习

bitbake命令单独编译u-boot&#xff1a; $ bitbake -c compile -f u-boot-imx $ bitbake -c deploy -f u-boot-imx //部署编译生成的u-boot镜像到deploy bitbake命令单独编译kernel&#xff1a; bitbake -c compile -f linux-imx //编译内核 bitbake -c deploy -f linux-imx /…...

【IC设计】牛客网-序列检测习题总结

文章目录 状态机基础知识VL25 输入序列连续的序列检测VL26 含有无关项的序列检测VL27 不重叠序列检测VL28 输入序列不连续的序列检测参考资料 状态机基础知识 VL25 输入序列连续的序列检测 timescale 1ns/1ns module sequence_detect(input clk,input rst_n,input a,output re…...

python爬虫登录到海康相机管理页面

简述 1.最近接到个任务是在管理页面更改相机的某个参数&#xff0c;下载官方的sdk貌似没有提供这个接口&#xff0c;所以只能自己写爬虫登录发请求了。 1.主要步骤 1.1 发送get请求获取到salt&#xff0c;sessionID&#xff0c;challenge等信息 http://admin:123456192.168.…...

9.Docker网络

文章目录 1、Docker网络简介2、常用基本命令3、网络模式对比举例3.1、bridge模式3.2、host模式3.3、none模式3.4、container模式3.5、自定义网络 1、Docker网络简介 作用&#xff1a; 容器间的互联和通信以及端口映射容器IP变动时候可以通过服务名直接进行网络通信而不受到影…...

Windows VS2022 C语言使用 sqlite3.dll 访问 SQLite数据库

今天接到一个学生C语言访问SQLite数据库的的需求: 第一步,SQLite Download Page下载 sqlite3.dll 库 下载解压,发现只有两个文件: 于是使用x64 Native Tools Command Prompt 终端 生成 sqlite3.lib 和 sqlite3.exp文件 LIB -def:sqlite3.def -out:sqlite3.lib -machin…...

java库和包的概念

在Java中&#xff0c;"库"和"包"是两个不同的概念&#xff0c;但它们之间存在着密切的关联。 库&#xff08;Library&#xff09; 定义&#xff1a;库是一组已经编写好的代码和资源&#xff0c;用于解决特定的问题或提供特定的功能。它可以包含一个或多个…...

mysql内存结构

一&#xff1a;逻辑存储结构&#xff1a;表空间->段->区->页->行、 表空间&#xff1a;一个mysql实例对应多个表空间&#xff0c;用于存储记录&#xff0c;索引等数据。 段&#xff1a;分为数据段&#xff0c;索引段&#xff0c;回滚段。innoDB是索引组织表&…...

Python | Leetcode Python题解之第111题二叉树的最小深度

题目&#xff1a; 题解&#xff1a; class Solution:def minDepth(self, root: TreeNode) -> int:if not root:return 0que collections.deque([(root, 1)])while que:node, depth que.popleft()if not node.left and not node.right:return depthif node.left:que.appen…...

c++二进制输出

输入一个数&#xff0c;输出n个数&#xff0c;数可以是0或1&#xff1b;输入&#xff1a;4输出&#xff1a;0010&#xff1b;提示&#xff1a;本题要用到rand(),srand(time(0));代码如下&#xff1a;#include<bits/stdc.h> #include<windows.h> using namespace s…...

5. C++网络编程-UDP协议的实现

UDP是无连接的。 UDP Server网络编程基本步骤 创建socket&#xff0c;指定使用UDP协议将socket与地址和端口绑定使用recv/send接收/发送数据 由于UDP是无连接的&#xff0c;直接侦听就行使用close关闭连接 这个UDP接收数据的时候用的API是recvfrom,发送数据是sendto 客户端 …...

Altium Designer 中键拖动,滚轮缩放,并修改缩放速度

我的版本是AD19&#xff0c;其他版本应该都一样。 滚轮缩放 首先&#xff0c;要用滚轮缩放&#xff0c;先要调整一下AD 设置&#xff0c;打开Preferences&#xff0c;在Mouse Wheel Configuration 里&#xff0c;把Zoom Main Window 后面Ctrl 上的对勾取消掉&#xff0c;再把…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

FFmpeg 低延迟同屏方案

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

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...