【leetcode刷题第43天】2016.增量元素之间的最大差值、1361.验证二叉树、1601.最多可达成的换楼请求的数目

本文主要是介绍【leetcode刷题第43天】2016.增量元素之间的最大差值、1361.验证二叉树、1601.最多可达成的换楼请求的数目,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第四十三天

2016 增量元素之间的最大差值

给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算nums[j] - nums[i] 能求得的 最大差值 ,其中 0 <= i < j < nnums[i] < nums[j]

返回 最大差值 。如果不存在满足要求的 ij ,返回 -1

示例 1:

输入:nums = [7,1,5,4]
输出:4
解释:
最大差值出现在 i = 1 且 j = 2 时,nums[j] - nums[i] = 5 - 1 = 4 。
注意,尽管 i = 1 且 j = 0 时 ,nums[j] - nums[i] = 7 - 1 = 6 > 4 ,但 i > j 不满足题面要求,所以 6 不是有效的答案。
方法

记录前缀最小值,然后遍历每一个元素,得到差值,取最大的差值即可。

class Solution {public int maximumDifference(int[] nums) {int res = -1;int[] min = new int[nums.length + 1];min[0] = Integer.MAX_VALUE;for (int i = 1; i <= nums.length; ++i) {if (nums[i - 1] < min[i - 1]) min[i] = nums[i - 1];else min[i] = min[i - 1];res = Math.max(res, nums[i - 1] - min[i - 1] > 0 ? nums[i - 1] - min[i - 1] : -1);}return res;}
}

1361 验证二叉树

二叉树上有 n 个节点,按从 0n - 1 编号,其中节点 i 的两个子节点分别是 leftChild[i]rightChild[i]

只有 所有 节点能够形成且 形成 一颗 有效的二叉树时,返回 true;否则返回 false

如果节点 i 没有左子节点,那么 leftChild[i] 就等于 -1。右子节点也符合该规则。

注意:节点没有值,本问题中仅仅使用节点编号。

方法

首先我们遍历一遍所有节点的左右孩子,找出其中最顶层的父节点,最顶层的父节点满足:它不是任何一个节点的子节点。因此对于最顶层的父节点,当我们遍历所有节点的左右孩子的时候,将这些孩子标记为已访问,最后我们检验一遍所有已经被访问的节点的数量是否为n-1,同时找出那个唯一没有被标记的节点就是最顶层的父节点。

当我们找到了这个父节点之后,我们使用广度有限搜索遍历所有节点的孩子节点,同时将遍历过的节点标记为已访问,最后我们校验所有的节点是否都被访问过,并且只被访问了一次,如果存在没有被访问的节点或者存在一个节点被访问了一次以上,那么就返回false。否则返回true

class Solution {public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {boolean[] isVisited = new boolean[n];Queue<Integer> queue =new LinkedList<>();int cnt = 0;for (int i = 0; i < n; ++i) {if (leftChild[i] != -1) {if (isVisited[leftChild[i]]) return false;isVisited[leftChild[i]] = true;cnt++;}if (rightChild[i] != -1) {if (isVisited[rightChild[i]]) return false;isVisited[rightChild[i]] = true;cnt++;}}if (cnt != n - 1) return false;for (int i = 0; i < n; ++i) {if (isVisited[i])  isVisited[i] = false;else {queue.offer(i);isVisited[i] = true;}}while (!queue.isEmpty()) {int index = queue.poll();if (leftChild[index] != -1) {if (isVisited[leftChild[index]]) return false;queue.offer(leftChild[index]);isVisited[leftChild[index]] = true;}if (rightChild[index] != -1) {if (isVisited[rightChild[index]]) return false;queue.offer(rightChild[index]);isVisited[rightChild[index]] = true;}}for (boolean flag : isVisited) if (!flag) return false;return true;}
}

1601 最多可达成的换楼请求数目

我们有 n 栋楼,编号从 0n - 1 。每栋楼有若干员工。由于现在是换楼的季节,部分员工想要换一栋楼居住。

给你一个数组 requests ,其中 requests[i] = [fromi, toi] ,表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。

一开始 所有楼都是满的,所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼搬入 的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ,一个员工要离开楼 1 ,一个员工要离开楼 2 ,如果该请求列表可行,应该要有两个员工搬入楼 0 ,一个员工搬入楼 1 ,一个员工搬入楼 2

请你从原请求列表中选出若干个请求,使得它们是一个可行的请求列表,并返回所有可行列表中最大请求数目。

输入:n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
输出:5
方法

我们使用二进制数来枚举所有可能满足的换楼请求,然后检查这些换楼请求是否合法。

由于换楼请求的数量最多只有16个,我们可以使用一个32位整数的后16位来完成所有情况的枚举。

对于检查函数,出楼会让人数--,进楼会让人数++,保证每一栋楼的净变化人数为0即可。

class Solution {public int maximumRequests(int n, int[][] requests) {int res = 0;for (int choose = (1 << requests.length) - 1; choose > 0; --choose) {if (check(n, choose, requests)) res = Math.max(res, getLength(choose));}return res;}public boolean check(int n,int choose, int[][] requests) {int[] status = new int[n];int index = 0;while (choose > 0) {if ((choose & 1) == 1) {status[requests[index][0]]--;status[requests[index][1]]++;}index++;choose >>= 1;}for (int i : status) if (i != 0) return false;return true;}public int getLength(int check){int res = 0;while (check > 0) { if ((check & 1) == 1) res++; check >>= 1;}return res;}
}

这篇关于【leetcode刷题第43天】2016.增量元素之间的最大差值、1361.验证二叉树、1601.最多可达成的换楼请求的数目的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907804

相关文章

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后

java父子线程之间实现共享传递数据

《java父子线程之间实现共享传递数据》本文介绍了Java中父子线程间共享传递数据的几种方法,包括ThreadLocal变量、并发集合和内存队列或消息队列,并提醒注意并发安全问题... 目录通过 ThreadLocal 变量共享数据通过并发集合共享数据通过内存队列或消息队列共享数据注意并发安全问题总结在 J

Java文件与Base64之间的转化方式

《Java文件与Base64之间的转化方式》这篇文章介绍了如何使用Java将文件(如图片、视频)转换为Base64编码,以及如何将Base64编码转换回文件,通过提供具体的工具类实现,作者希望帮助读者... 目录Java文件与Base64之间的转化1、文件转Base64工具类2、Base64转文件工具类3、

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧,

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

Java后端接口中提取请求头中的Cookie和Token的方法

《Java后端接口中提取请求头中的Cookie和Token的方法》在现代Web开发中,HTTP请求头(Header)是客户端与服务器之间传递信息的重要方式之一,本文将详细介绍如何在Java后端(以Sp... 目录引言1. 背景1.1 什么是 HTTP 请求头?1.2 为什么需要提取请求头?2. 使用 Spr

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制