力扣每日一题:3011. 判断一个数组是否可以变为有序

力扣官网:前往作答!!!!

今日份每日一题:

题目要求:

  • 给你一个下标从 0 开始且全是 正 整数的数组 nums 。

  • 一次 操作 中,如果两个 相邻 元素在二进制下数位为 1 的数目 相同 ,那么你可以将这两个元素交换。你可以执行这个操作 任意次 (也可以 0 次)。

  • 如果你可以使数组变有序,请你返回 true ,否则返回 false 。


示例如下:

示例1

输入:nums = [8,4,2,30,15]
输出:true
解释:我们先观察每个元素的二进制表示。 2 ,4 和 8 分别都只有一个数位为 1 ,分别为 “10” ,“100” 和 “1000” 。15 和 30 分别有 4 个数位为 1 :“1111” 和 “11110” 。
我们可以通过 4 个操作使数组有序:

  • 交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。
  • 交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。
  • 交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。
  • 交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 ,数组变为 [2,4,8,15,30] 。

数组变成有序的,所以我们返回 true 。
注意我们还可以通过其他的操作序列使数组变得有序。

示例2

输入:nums = [1,2,3,4,5]
输出:true
解释:数组已经是有序的,所以我们返回 true 。

示例3

输入:nums = [3,16,8,4,2]
输出:false
解释:无法通过操作使数组变为有序。

解释

剖析示例

示例1

其实还是比较好理解的:

  • 最简单的情况,也就是示例1
  • 我们可以把这一整个数组根据二进制中1的个数分为几个小组,如果在小组中能够进行排序那么就可以完成升序排序

请添加图片描述

在示例一中,按照二进制中1的个数进行划分,我们可以发现:

  • 整个数组可以分为两个小组
  • 而两个小组中间没有被分割

那么这种情况下:我们只需要判断前一个小组的最大数是否大于后面小组的任意一个数

  • 此时前一个小组的最大值为8
  • 8小于任何一个后面组的数
  • 所以可以通过交换得到有序序列
示例2

请添加图片描述
从上图我们可以看到:

  • 小组和小组之间被隔开了
  • 此时的分组应为4个:1,2为个数为1的第一组;3为个数为2的第二组;4为个数为1的第三组,5为个数为2的第四组

那么我们可以开始判断

  • 前一个小组的最大值是否大于后一个组的任意一个值:
  • 第一组的最大值2小于第二组的3
  • 第二组的最大值3小于第三组的4
  • 第三组的最大值4小于第四组的5
  • 所以可以通过交换得到有序序列
示例3

请添加图片描述
再次使用公式做题:

  • 前一个小组的最大值是否大于后一个组的任意一个值:
  • 第一组的最大值3大于后一组中的2
  • 所以不能通过交换得到有序序列。

将逻辑思路转换为代码

逻辑思路:

  • 获取当前数字的二进制中的1的个数
  • 按照1的个数进行分类
  • 前一个小组的最大值是否大于后一个组的任意一个值

这里有个小细节:我们不需要通过很多个数组将值进行物理分割,我们只需要记录当前的1的个数是否和前一个相同,相同就是一个组,不同就是不同组

代码:

  • 一个变量记录当前值的二进制中1的个数
  • 一个变量记录上一个组的二进制中1的个数
  • 一个变量记录当前组中最大的值(主要是用来传递,当进入下一个组时,当前组最大值就变为了上一个组的最大值)
  • 一个变量记录上一个组中最大的值
  • 循环遍历数组
  • 当此变量和上一个变量为同一组,那么判断此变量是否大于当前组的最大值
  • 当此变量和上一个变量不为一个组,那么更新变量(当前组最大值就变为了上一个组的最大值,上一个值的二进制中1的个数变为当前值的二进制中1的个数,当前组最大值变为了这个变量)
  • 而当上一个组别的最大值大于新组中的任意一个值,则直接返回false
  • 循环结束后,返回true(表示的是循环中没有一个前一个小组的最大值大于后一个组的任意一个值)

那么具体代码如下所示:(模仿官解,只是用于讲解,不喜勿喷)

    bool canSortArray(vector<int>& nums) {int curNum;//用来记录当前值的二进制中1的个数int lastNum;//用来记录上一个组的二进制中1的个数int lastNumMax;//用来记录上一个组的最大值int curNumMax;//用来记录这个组最大值for(int i = 0;i<nums.size();i++){int curNum = __builtin_popcount(nums[i]); 	//封装的函数,用来获取变量值转为2进制后1的个数int n = nums[i];							//简单变量,就是当前值if(curNum == lastNum){						//当当前值和上一个值为同一组curNumMax = fmax(curNumMax,n);			//判断组别中的最大值和当前值谁更大,谁更大就是谁}else{										//当当前值和上一个值不为同一组lastNum = curNum;						//上一个组的二进制中1的个数变为当前值的二进制中1的个数lastNumMax = curNumMax;					//上一个组的最大值变为这个组最大值curNumMax = n;							//当前组的最大值变为此变量}if(n < lastNumMax){							//最最重要的判断前一个小组的最大值是否大于后一个组的任意一个值return false;							//如果是,直接返回false}}return true;									//循环中没有一个前一个小组的最大值大于后一个组的任意一个值,返回true}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/376614.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

STM32G4 DMA的使用(寄存器开发)

下面以STM32G474为例&#xff0c;使用DMA来存储USART1的接收数据。 1. 查看硬件支持 首先查看要使用的DMA支持的通道数&#xff0c;在手册中有如下说明。 根据上图可以看到&#xff0c;对于不同的设备类型有不同的DMA通道数量。设备类型分类如下图所示。 我使用的是STM32G474…

【Three.js基础学习】16.Physice

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 前言 课程回顾 物理库 3D Ammo.js Cannon.js Oimo.js 2D Matter.js P2.js Planck.js Box2D.js 补充:一些看似3D的效果实际使用2D库来实现的 物理 和 three.js的结合 概念补充…

雷达视频采集卡 HPx-410

产品简介 雷达视频采集卡 HPx-410&#xff0c;应用于接入导航雷达数据&#xff0c;导航雷达视频&#xff0c;适用于JRC雷达、古野furuon雷达、Sperry雷达等多种型号的雷达。 HPx-410 可以接入导航雷达数据&#xff0c;引入导航雷达原始回波&#xff0c;然后将雷达视频采集到计…

html5——列表、表格

目录 列表 无序列表 有序列表 自定义列表 表格 基本结构 示例 表格的跨列 表格的跨行 列表 无序列表 <ul>【声明无序列表】 <li>河间驴肉火烧</li>【声明列表项】 <li>唐山棋子烧饼</li> <li>邯郸豆沫</li> <l…

python爬虫加入进度条

安装tqdm和requests库 pip install tqdm -i https://pypi.tuna.tsinghua.edu.cn/simplepip install requests -i https://pypi.tuna.tsinghua.edu.cn/simple带进度条下载 import time # 引入time模块&#xff0c;用于处理时间相关的功能 from tqdm import * # 从tqdm包中…

基于SpringBoot+Hadoop+python的物品租赁系统(带1w+文档)

基于SpringBootHadooppython的物品租赁系统(带1w文档) 基于SpringBootHadooppython的物品租赁系统(带1w文档) 物品租赁系统是电子、信息技术相结合&#xff0c;是一种必然的发展趋势。以互联网为基础&#xff0c;以服务于广大用户为目的&#xff0c;发展整体优势&#xff0c;扩…

Vue3 pdf.js将二进制文件流转成pdf预览

好久没写东西&#xff0c;19年之前写过一篇Vue2将pdf二进制文件流转换成pdf文件&#xff0c;如果Vue2换成Vue3了&#xff0c;顺带来一篇文章&#xff0c;pdf.js这个东西用来解决内网pdf预览&#xff0c;是个不错的选择。 首先去pdfjs官网&#xff0c;下载需要的文件 然后将下载…

数据仓库哈哈

数据仓库 基本概念数据库&#xff08;database&#xff09;和数据仓库&#xff08;Data Warehouse&#xff09;的异同 整体架构分层架构方法论ER模型&#xff08;建模理论&#xff09;维度模型 何为分层第一层&#xff1a;数据源&#xff08;ODS ER模型&#xff09;设计要点日志…

python中的os模块和shutil模块

目录 os 1. 获取当前脚本绝对路径 2.获得工作路径&#xff1b; 3.该路径文件和目录 4.walk&#xff0c;查看目录下所有的文件&#xff08;含子孙文件&#xff09; 5.创建文件夹 6.os.makedirs(path) 7.路径拼接 8. 获取当前文件的上级目录 9.判断路径是否存在 10.是…

一 GD32 MCU 开发环境搭建

GD32 系列为通用型 MCU &#xff0c;所以开发环境也可以使用通用型的 IDE &#xff0c;目前使用较多的是 KEIL、 IAR 、 GCC 和 Embedded Builder &#xff0c;客户可以根据个人喜好来选择相应的开发环境。 目录 1、使用 Keil 开发 GD32 目前市面通用的MDK for ARM版本有Kei…

WPF学习(2) -- 样式基础

一、代码 <Window x:Class"学习.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expression/blend/2008&…

Contact Form联系表单自动发送邮件(超级简单)

前几天发现了aoksend推出的这个联系表单的组件&#xff0c;非常好用&#xff0c;只有一个php文件&#xff0c;把php文件放到网站主目录里面。然后去aoksend注册和配置好域名和发信邮箱&#xff0c;可以得到发送密钥&#xff1a;app_key&#xff0c;然后配置好邮件模板&#xff…

Linux常见配置

linux 常见配置 一、配置固定IP Centos配置固定IP 使用vim编辑/etc/sysconfig/network-scripts/ifcfg-ens33文件&#xff0c;填入如下 二、配置环境变量 1、将要配置的环境变量写入相应文件 ~/.bashrc # 用户环境变量配置文件 /etc/profile # 全局环境变量配置文件2、执行…

安防视频监控/云存储/视频汇聚EasyCVR平台播放设备录像不稳定,是什么原因?

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;EasyCVR基于云边端一体化架构&#xff0c;具有强大的数据接入、处理及分发能力&#xff0c;可提供7*24小时实时高清视频监控、云端录像、云存储、录像检索与回看、智能告警…

无障碍全免费上手智能体:Autogen Studio结合Deepseek Coder打造一款AI旅游规划师

本文的唯一目的是通过打造一款AI旅游规划师&#xff0c;通俗易懂、深入浅出的讲清楚AI应用的大方向-智能体-的原理。 无需科学上网&#xff0c;无需付费API&#xff0c;无需编程能力&#xff0c;一小时即可部署、搭建一款复杂的、多代理交互的AI智能体-旅游规划师&#xff0c;…

【Linux】:文件fd

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家带来关于文件fd的相关知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从入门到精通 数据…

FastAPI 学习之路(四十一)定制返回Response

接口中返回xml格式内容 from fastapi import FastAPI, Responseapp FastAPI()# ① xml app.get("/legacy") def get_legacy_data():data """<?xml version"1.0"?><shampoo><Header>Apply shampoo here.</Header&…

[笔记] SEW的振动分析工具DUV40A

1.便携式振动分析仪 DUV40A 文档编号&#xff1a;26871998/EN SEW是一家国际化的大型的机械设备供应商。产品线涵盖电机&#xff0c;减速机&#xff0c;变频器等全系列动力设备。DUV40A是他自己设计的一款振动分析工具。 我们先看一下它的软硬件参数&#xff1a; 内置两路传…

国内外大模型 SuperCLUE 基准测试

本心、输入输出、结果 文章目录 国内外大模型 SuperCLUE 基准测试前言国内外大模型 SuperCLUE 基准测试榜单什么是中文大模型基准 SuperCLUE国内外大模型 SuperCLUE 基准测试 编辑 | 简简单单 Online zuozuo 地址 | https://blog.csdn.net/qq_15071263 如果觉得本文对你有帮助,…

大数据开发中的数据驱动决策:关键问题与实践指南

目录 决策前的准备工作1. 我已经掌握了哪些信息&#xff1f;2. 我们已经做出决定了吗&#xff1f;3. 我们需要哪些额外信息以及何时需要&#xff1f; 决策过程中的关键问题1. 我们需要做这个决定吗&#xff1f;2. 错误地做出这个决定的代价是什么&#xff1f; 决策后的反思1. 我…