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.从给定原材料中找到所有可以做出的菜
思路:拓补排序,哈希表 在思路上其实很好发现,我们需要有一个明确的做菜顺序,也就是说需要定下来我们根据原材料先做哪些菜,然后做完该做的菜之后,后来又能做哪些菜。 你也发现了,这个顺序其实…...
Opencompass模型评测教程
模型评测 模型评测非常关键,目前主流的方法主要可以概括为主观评测和客观评测,主观评测又可以分为两种形式:人工判断或者和模型竞技场。客观评测一般采用评测数据集的形式进行模型评测。本教程使用Opencompass工具进行对Internlm2-7b模型进行…...
什么是安全测试,如何进行安全测试?
什么是安全测试? 概述 安全测试是一种旨在识别系统、网络或应用程序中的安全漏洞的测试方法。其目标是确保系统能够抵御恶意攻击,保护数据的机密性、完整性和可用性。安全测试通常包括漏洞扫描、渗透测试、代码审计和安全评估等多个方面。 安全测试的…...
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
文章最前: 我是Octopus,这个名字来源于我的中文名--章鱼;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ;这博客是记录我学习的点点滴滴,如果您对 Python、Java、AI、算法有兴趣,可以关注我的…...
Java入门基础学习笔记41——实体类
实体JavaBean/实体类: 就是一种特殊形式的类。 1)这个类中的成员变量都要私有,并且要对外提供相应的getXXX,setXXX的方法。 2)类中必须要有一个公共的无参的构造器。其他的构造器可写可不写。 右键菜单中࿰…...
【Linux】信号之信号的保存和处理详解
🤖个人主页:晚风相伴-CSDN博客 💖如果觉得内容对你有帮助的话,还请给博主一键三连(点赞💜、收藏🧡、关注💚)吧 🙏如果内容有误或者有写的不好的地方的话&…...
基于Django的图书管理系统
文章目录 前言一、页面展示1.登录2.前端页面3.后端页面 二、项目上传(1)导入数据库(2)导入项目(3)数据库密码修改(4)进入网站 总结 前言 本网站调用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: $ bitbake -c compile -f u-boot-imx $ bitbake -c deploy -f u-boot-imx //部署编译生成的u-boot镜像到deploy bitbake命令单独编译kernel: 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.最近接到个任务是在管理页面更改相机的某个参数,下载官方的sdk貌似没有提供这个接口,所以只能自己写爬虫登录发请求了。 1.主要步骤 1.1 发送get请求获取到salt,sessionID,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网络简介 作用: 容器间的互联和通信以及端口映射容器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中,"库"和"包"是两个不同的概念,但它们之间存在着密切的关联。 库(Library) 定义:库是一组已经编写好的代码和资源,用于解决特定的问题或提供特定的功能。它可以包含一个或多个…...
mysql内存结构
一:逻辑存储结构:表空间->段->区->页->行、 表空间:一个mysql实例对应多个表空间,用于存储记录,索引等数据。 段:分为数据段,索引段,回滚段。innoDB是索引组织表&…...
Python | Leetcode Python题解之第111题二叉树的最小深度
题目: 题解: 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++二进制输出
输入一个数,输出n个数,数可以是0或1;输入:4输出:0010;提示:本题要用到rand(),srand(time(0));代码如下:#include<bits/stdc.h> #include<windows.h> using namespace s…...
5. C++网络编程-UDP协议的实现
UDP是无连接的。 UDP Server网络编程基本步骤 创建socket,指定使用UDP协议将socket与地址和端口绑定使用recv/send接收/发送数据 由于UDP是无连接的,直接侦听就行使用close关闭连接 这个UDP接收数据的时候用的API是recvfrom,发送数据是sendto 客户端 …...
Altium Designer 中键拖动,滚轮缩放,并修改缩放速度
我的版本是AD19,其他版本应该都一样。 滚轮缩放 首先,要用滚轮缩放,先要调整一下AD 设置,打开Preferences,在Mouse Wheel Configuration 里,把Zoom Main Window 后面Ctrl 上的对勾取消掉,再把…...
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.…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
Pydantic + Function Calling的结合
1、Pydantic Pydantic 是一个 Python 库,用于数据验证和设置管理,通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发(如 FastAPI)、配置管理和数据解析,核心功能包括: 数据验证:通过…...
针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...
结构化文件管理实战:实现目录自动创建与归类
手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题,进而引发后续程序异常。使用工具进行标准化操作,能有效降低出错概率。 需要快速整理大量文件的技术用户而言,这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB,…...
云原生安全实战:API网关Envoy的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口,负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...
基于django+vue的健身房管理系统-vue
开发语言:Python框架:djangoPython版本:python3.8数据库:mysql 5.7数据库工具:Navicat12开发软件:PyCharm 系统展示 会员信息管理 员工信息管理 会员卡类型管理 健身项目管理 会员卡管理 摘要 健身房管理…...
