每日一题 1601最多可达成的换楼请求数目(子集模版)
题目
1601
我们有 n 栋楼,编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节,部分员工想要换一栋楼居住。
给你一个数组 requests ,其中 requests[i] = [fromi, toi] ,表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。
一开始 所有楼都是满的,所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼 搬入 的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ,一个员工要离开楼 1 ,一个员工要离开楼 2 ,如果该请求列表可行,应该要有两个员工搬入楼 0 ,一个员工搬入楼 1 ,一个员工搬入楼 2 。
请你从原请求列表中选出若干个请求,使得它们是一个可行的请求列表,并返回所有可行列表中最大请求数目。
示例 1:
输入:n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
输出:5
解释:请求列表如下:
从楼 0 离开的员工为 x 和 y ,且他们都想要搬到楼 1 。
从楼 1 离开的员工为 a 和 b ,且他们分别想要搬到楼 2 和 0 。
从楼 2 离开的员工为 z ,且他想要搬到楼 0 。
从楼 3 离开的员工为 c ,且他想要搬到楼 4 。
没有员工从楼 4 离开。
我们可以让 x 和 b 交换他们的楼,以满足他们的请求。
我们可以让 y,a 和 z 三人在三栋楼间交换位置,满足他们的要求。
所以最多可以满足 5 个请求。
示例 2:
输入:n = 3, requests = [[0,0],[1,2],[2,1]]
输出:3
解释:请求列表如下:
从楼 0 离开的员工为 x ,且他想要回到原来的楼 0 。
从楼 1 离开的员工为 y ,且他想要搬到楼 2 。
从楼 2 离开的员工为 z ,且他想要搬到楼 1 。
我们可以满足所有的请求。
示例 3:
输入:n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
输出:4
题解
class Solution {private int max = 0;private int[][] requests;private int[] buildings;private int cnt = 0;public int maximumRequests(int n, int[][] requests) {buildings = new int[n];this.requests = requests;dfs(0);return max;}private void dfs(int i) {if (check()) {max = Math.max(cnt,max);}if (i == requests.length) {return;}for (int j = i; j < requests.length; j++) {buildings[requests[j][0]]--;buildings[requests[j][1]]++;cnt++;dfs(j+1);//返回操作buildings[requests[j][0]]++;buildings[requests[j][1]]--;cnt--;}}//判断是否分配合理private boolean check() {for (int i : buildings) {if (i != 0) {return false;}}return true;}
}
相关文章:
每日一题 1601最多可达成的换楼请求数目(子集模版)
题目 1601 我们有 n 栋楼,编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节,部分员工想要换一栋楼居住。 给你一个数组 requests ,其中 requests[i] [fromi, toi] ,表示一个员工请求从编号为 fromi 的楼搬到编号为…...
排序算法-归并排序
属性 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序&#…...
vue3 整合 springboot 打完整jar包
前端 .env.developmen VITE_APP_BASE_URL/api.env.production VITE_APP_BASE_URL/axios 配置 axios.defaults.baseURL import.meta.env.VITE_APP_BASE_URLpackage.json "scripts": {"dev": "vite --mode development","build": &…...
依赖倒转原则是什么?
依赖倒转原则(Dependency Inversion Principle)是面向对象设计中的另一个基本原则,它是由Robert C. Martin提出的,它的中心思想是面向接口编程,该原则指出高层模块不应该依赖于低层模块,两者都应该依赖于抽…...
什么是GPT与MBR
GPT(GUID Partition Table)和MBR(Master Boot Record)是两种不同的磁盘分区表格式。 MBR是一种较早的磁盘分区表格式,它使用512字节的扇区作为存储空间。MBR分区表可以定义最多4个主分区,每个主分区都可以…...
前后端开发接口联调对接参数
前言 一个完整的互联网系统项目,需要前后端配合,进行上线,针对前端开发者,现在互联网主流的项目都是前后端分离 也就是后端负责提供数据接口,前端负责UI界面数据渲染 凡是在前台数据展示与用户交互的,都是由前端来实现的,而数据来源是由后台服务提供的 在浏览器c端能够发送后端…...
定时任务框架-xxljob
1.定时任务 spring传统的定时任务Scheduled,但是这样存在这一些问题 : 做集群任务的重复执行问题 cron表达式定义在代码之中,修改不方便 定时任务失败了,无法重试也没有统计 如果任务量过大,不能有效的分片执行 …...
idea项目配置三大步
场景: 使用 idea 打开一个新项目的时候,想让项目迅速跑起来, 其实只需要下面简单三步: 1. 首先,配maven 2. 其次,配置 jdk 这里配置 project 就行了,不用管Modules中的配置。 3. 最后&#…...
学会SpringMVC之自定义注解各种场景应用,提高开发效率及代码质量
目录 一、简介 ( 1 ) 是什么 ( 2 ) 分类 ( 3 ) 作用 二、自定义注解 ( 1 ) 如何自定义注解 ( 2 ) 场景演示 场景一(获取类与方法上的注解值) 场景二( 获取类属性上的注解属性值 ) 场景三( 获取参数修…...
步态识别常见模块解读及代码实现:基于OpenGait框架
步态识别常见模块解读及代码实现:基于OpenGait框架 最近在看步态识别相关论文,但是因为记忆力下降的原因,老是忘记一些内容。因此记录下来方便以后查阅,仅供自己学习参考,没有背景知识和论文介绍。 目录 步态识别常见…...
前端八股文之“闭包”
一、定义 一句话概括闭包:能够访问函数内部变量的函数与这个变量的组合构成了闭包结构。如下代码 function fuc1(){let num 999return function fuc2(){console.log(num)}}fuc1()(); 如代码所示,fuc2和父级变量num构成了一个闭包环境。 二、原理 子…...
数据可视化:掌握数据领域的万金油技能
⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据开发、数据分析等。 🐴欢迎小伙伴们点赞👍🏻、收藏⭐️、…...
Apache Kafka 基于 S3 的数据导出、导入、备份、还原、迁移方案
在系统升级或迁移时,用户常常需要将一个 Kafka 集群中的数据导出(备份),然后在新集群或另一个集群中再将数据导入(还原)。通常,Kafka集群间的数据复制和同步多采用 Kafka MirrorMaker࿰…...
事务管理AOP
事务管理 事务回顾 概念:事务是一组操作的集合,它是一个不可分割的工作单位,这些操作要么同时成功,要么同时失败 操作: 开启事务:一组操作开始前,开启事务-start transaction/be…...
Java从Tif中抽取最大的那张图进行裁剪成x*y份
之前我有一篇帖子《kfb格式文件转jpg格式》讲述到 kfb > tif > jpg,但是针对于超大tif中的大图是无法顺利提取的,就算是能顺利提取,试想一下,2G的tif文件,如果能提取处理最大的那张图,并且在不压缩的…...
人工智能AI界的龙头企业,炸裂的“英伟达”时代能走多远
原创 | 文 BFT机器人 1、AI芯片的竞争格局已趋白热化 尽管各类具有不同功能和定位的AI芯片在一定程度上可实现互补,但同时也在机遇与挑战并存中持续调整定位。在AI训练端,英伟达的GPU凭着高算力的门槛,一直都是训练端的首选。 只有少数芯片能…...
【实战】H5 页面同时适配 PC 移动端 —— 旋转横屏
文章目录 一、场景二、方案三、书单推荐01 《深入实践Kotlin元编程》02 《Spring Boot学习指南》03 《Kotlin编程实战》 一、场景 一个做数据监控的单页面,页面主要内容是一个整体必须是宽屏才能正常展示,这时就不能用传统的适配方案了,需要…...
使用凌鲨进行聚合搜索
作为研发人员,我们经常需要在多个来源之间查找信息,以便进行研发工作。除了常用的搜索引擎如百度和必应之外,我们还需要查阅各种代码文档和依赖包等资源。这些资源通常分散在各个网站和文档库中,需要花费一定的时间和精力才能找到…...
程序设计之——手把手教你如何从Excel文件中读取学生信息
在当今信息化时代,计算机技术已经深入到各个领域,而程序设计则成为推动信息化建设的关键技术之一。在众多领域中,学生信息管理系统无疑是其中一个重要的应用。本文将从学生信息管理系统的开发入手,探讨开如何高效且保证质量的完成…...
Docker容器化技术(从零学会Docker)
文章目录 前言一、初识Docker1.初识Docker-Docker概述2.初识Docker-安装Docker3.初识Docker-Docker架构4.初识Docker-配置镜像加速器 二、Docker命令1.Docker命令-服务相关命令2.Docker命令-镜像相关命令3.Docker命令-容器相关命令 三、Docker容器的数据卷1.Docker容器数据卷-数…...
AR.js实战指南:如何在Web浏览器中构建高效增强现实应用
AR.js实战指南:如何在Web浏览器中构建高效增强现实应用 【免费下载链接】AR.js Image tracking, Location Based AR, Marker tracking. All on the Web. 项目地址: https://gitcode.com/gh_mirrors/arj/AR.js 在移动设备普及的今天,增强现实&…...
5倍效率提升:GIMP批量图像处理插件BIMP全攻略
5倍效率提升:GIMP批量图像处理插件BIMP全攻略 【免费下载链接】gimp-plugin-bimp 项目地址: https://gitcode.com/gh_mirrors/gi/gimp-plugin-bimp 在数字内容创作领域,批量图像处理是提升效率的关键环节。GIMP作为免费开源的图像编辑软件&#…...
3步搞定黑苹果配置:OpCore-Simplify自动化EFI构建终极指南
3步搞定黑苹果配置:OpCore-Simplify自动化EFI构建终极指南 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 还在为复杂的黑苹果配置头疼吗&…...
腾讯云+Astrbot个人AI部署,接入QQ机器人
1、腾讯云创建云服务器 之所以选择腾讯云是因为可以领一个月免费服务器 地址:https://cloud.tencent.com/ 服务器配置情况: 这里我获取的是轻量应用服务器(Lighthouse),适合网站搭建、开发测试等多种场景。以下是详细…...
3步解锁iOS激活锁:Applera1n工具完整使用指南
3步解锁iOS激活锁:Applera1n工具完整使用指南 【免费下载链接】applera1n icloud bypass for ios 15-16 项目地址: https://gitcode.com/gh_mirrors/ap/applera1n 当你面对一部显示"激活锁"界面的iPhone,反复输入Apple ID却始终无法进入…...
The Leather Archive应用案例:从赛博都市到极简主义的皮衣穿搭
The Leather Archive应用案例:从赛博都市到极简主义的皮衣穿搭 1. 项目概述 「The Leather Archive」是一个基于AI技术的高端皮衣穿搭生成系统,它巧妙融合了Anything V5基础模型与Stable Yogi皮衣系列LoRA的专业能力。与传统AI工具不同,该项…...
【信号处理】基于预设性能的无模型自适应分数阶快速终端滑模控制在MIMO非线性系统中的研究附matlab代码
✅作者简介:热爱科研的Matlab仿真开发者,擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。🍎 往期回顾关注个人主页:Matlab科研工作室👇 关注我领取海量matlab电子书和…...
从零开始:用正则表达式处理日期时间格式的完整指南
从零开始:用正则表达式处理日期时间格式的完整指南 在数据处理和文本分析中,日期时间格式的校验一直是个高频需求。无论是表单验证、日志分析还是数据清洗,确保日期时间格式的正确性都至关重要。正则表达式作为文本处理的瑞士军刀,…...
面向对象编程入门(下篇):继承、封装与多态
在上篇中,我们学会了如何定义类和创建对象,将现实世界的事物用代码表示。今天,我们将深入面向对象编程的三大核心特性:继承、封装和多态。这些特性将让你的代码更加灵活、可扩展和易维护。一、继承:代码复用的“家族传…...
Java笔记——JMM
在多线程编程中,共享变量的可见性、操作的原子性以及指令的重排序,常常成为导致程序出现诡异Bug的罪魁祸首。而Java之所以能够成为并发编程的首选语言之一,很大程度上归功于其强大的Java内存模型(Java Memory Model, JMMÿ…...
