【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

相关文章

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Vue中组件之间传值的六种方式(完整版)

《Vue中组件之间传值的六种方式(完整版)》组件是vue.js最强大的功能之一,而组件实例的作用域是相互独立的,这就意味着不同组件之间的数据无法相互引用,针对不同的使用场景,如何选择行之有效的通信方式... 目录前言方法一、props/$emit1.父组件向子组件传值2.子组件向父组件传值(通过事件形式)方

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Python实现PDF与多种图片格式之间互转(PNG, JPG, BMP, EMF, SVG)

《Python实现PDF与多种图片格式之间互转(PNG,JPG,BMP,EMF,SVG)》PDF和图片是我们日常生活和工作中常用的文件格式,有时候,我们可能需要将PDF和图片进行格式互转来满足... 目录一、介绍二、安装python库三、Python实现多种图片格式转PDF1、单张图片转换为PDF2、多张图

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

Qt实现发送HTTP请求的示例详解

《Qt实现发送HTTP请求的示例详解》这篇文章主要为大家详细介绍了如何通过Qt实现发送HTTP请求,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、添加network模块2、包含改头文件3、创建网络访问管理器4、创建接口5、创建网络请求对象6、创建一个回复对

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为

SpringBoot项目注入 traceId 追踪整个请求的日志链路(过程详解)

《SpringBoot项目注入traceId追踪整个请求的日志链路(过程详解)》本文介绍了如何在单体SpringBoot项目中通过手动实现过滤器或拦截器来注入traceId,以追踪整个请求的日志链... SpringBoot项目注入 traceId 来追踪整个请求的日志链路,有了 traceId, 我们在排

Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)

《Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)》本文介绍了如何使用Python和Selenium结合ddddocr库实现图片验证码的识别和点击功能,感兴趣的朋友一起看... 目录1.获取图片2.目标识别3.背景坐标识别3.1 ddddocr3.2 打码平台4.坐标点击5.图