力扣406-根据身高重建队列(java详细题解)

2024-08-31 22:52

本文主要是介绍力扣406-根据身高重建队列(java详细题解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:406. 根据身高重建队列 - 力扣(LeetCode)

前情提要:

因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。

贪心方法:局部最优推出全局最优。

如果一个题你觉得可以用局部最优推出全局最优,并且没有反例来反驳的话就可以用贪心来试试。

题目思路:

如果你看过我对于力扣135-分发糖果那篇题解的话,会发现这个题好像跟那个有一点类似。

类似在哪里?

这俩道题都是有俩个维度,这个题分别有k和h俩个维度。

那么遇到这种有俩个维度的题,我们应该优先处理一个维度,再去处理另外一个维度。

那这个题,我们先处理n还是k呢?

如果按照k来从小到大排序,排完之后,会发现k的排列并不符合条件,身高也不符合条件,两个维度哪一个都没确定下来。

所以我们按照n来从大到小排序,那么我们每一个数的前面都是比后面要大的,这样我们就可以确定一个维度,前面节点都比后面节点要高。

然后继续根据每个元素的k来插入到k位置即可。

因为k是前面节点比当前节点大的数量,我们已经按升高排序了,前面节点全比后面高,所以当k等于几,你插入到该位置后面就可以。

举个例子。

在这里插入图片描述

那肯定有人会有疑问 插入到该位置不会对他后面的位置有影响吗 ?

其实不会 ,因为他插入的都是h比他高的人 就算他插进来对比他高的k也不会有任何影响 随便他插到哪里去。

局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性。

全局最优:最后都做完插入操作,整个队列满足题目队列属性。

最终代码:

class Solution {public int[][] reconstructQueue(int[][] people) {//该题与分发糖果有些类似,也是一个多维度的题目//多维度的题目 我们要讲究先把一个维度处理好再处理另一个维度//那么该题到底是先处理k还是处理h呢//如果先处理k 我们按从小到大排 得到的结果不仅k没处理好 h也没处理好 所以我们先处理h//如果先处理h 我们得到了一个根据h从大到小的一个队列 此时每一个数前面都是大与等于自身的//所以此时h就已经处理好了 我们该处理k了//我们从大到小处理k 当他的k等于多少时,就将他插入到该位置//那肯定有人会有疑问 插入到该位置不会对他后面的位置有影响吗 其实不会 //因为他插入的都是h比他高的人 就算他插进来他们的k也不会有任何影响 随便他插到哪里去//局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性//全局最优:最后都做完插入操作,整个队列满足题目队列属性//根据身高降序排 如果身高一样按k升序排 因为k越大 说明他前面大与等于他的越多Arrays.sort(people,(a,b) -> {//h相等时 k按从小到大排if(a[0] == b[0])return a[1] - b[1];//h不相等,按从大到小排return b[0] - a[0];});LinkedList<int []> list = new LinkedList<>();for(int[] arr : people){//将arr插入指定k处list.add(arr[1],arr);}return list.toArray(new int [people.length][]);}
}

这道题代码量很少,但是逻辑可能不是那么好理解,我们可以多画画图,多模拟几遍就能弄懂啦。

这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。

我很乐意为你解答。那么我们下篇再见!

这篇关于力扣406-根据身高重建队列(java详细题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听