当前位置: 首页 > news >正文

【Leetcode 每日一题 - 扩展】421. 数组中两个数的最大异或值

问题背景

给你一个整数数组 n u m s nums nums,返回 n u m s [ i ] X O R n u m s [ j ] nums[i]\ XOR\ nums[j] nums[i] XOR nums[j] 的最大运算结果,其中 0 ≤ i ≤ j < n 0 ≤ i ≤ j < n 0ij<n

数据约束

  • 1 ≤ n u m s . l e n g t h ≤ 2 × 1 0 5 1 \le nums.length \le 2 \times 10 ^ 5 1nums.length2×105
  • 0 ≤ n u m s [ i ] ≤ 2 31 − 1 0 \le nums[i] \le 2 ^ {31} - 1 0nums[i]2311

解题过程

终于出现每日一题抄都抄不明白的情况了,今天的题需要改进 0 − 1 0 - 1 01背包之后将数组处理成前后缀,然后再解决两个数组中的最大异或值问题。
自己目前动态规划掌握地并不好,不强求。
不过其中涉及到的这个最大异或值是可以学着写写,积累一下的。

主要的思路是从高到低枚举数组中数字的每一位,依次判断这一位上有没有可能异或得到 1 1 1,计算出所需的另一个因子,判断它在数组中是否存在即可。
这里的判断,有点像 两数之和,可以用哈希表来实现。

具体实现

class Solution {public int findMaximumXOR(int[] nums) {// 标准流程,计算数组中数字可能的最大有效长度int max = 0;for (int num : nums) {max = Math.max(max, num);}int n = 31 - Integer.numberOfLeadingZeros(max);// 定义一个掩码变量,方便在过程中处理某一位上的问题int res = 0, mask = 0;Set<Integer> set = new HashSet<>();// 这里下标 i 需要倒序变化,因为某一位上为 1 是需要通过左移来实现的for (int i = n; i >= 0; i--) {set.clear();mask |= 1 << i;// nextRes 表示下一个可能的较大的结果int nextRes = res | (1 << i);for (int num : nums) {// 这一位之后的所有位上置零num &= mask;// 如果对应的因子在集合中存在,就更新结果if (set.contains(nextRes ^ num)) {res = nextRes;break;}set.add(num);}}return res;}
}

相关文章:

【Leetcode 每日一题 - 扩展】421. 数组中两个数的最大异或值

问题背景 给你一个整数数组 n u m s nums nums&#xff0c;返回 n u m s [ i ] X O R n u m s [ j ] nums[i]\ XOR\ nums[j] nums[i] XOR nums[j] 的最大运算结果&#xff0c;其中 0 ≤ i ≤ j < n 0 ≤ i ≤ j < n 0≤i≤j<n。 数据约束 1 ≤ n u m s . l e n g…...

计算机网络 | IP地址、子网掩码、网络地址、主机地址计算方式详解

关注&#xff1a;CodingTechWork 引言 在计算机网络中&#xff0c;IP地址、子网掩码和网络地址是构建网络通信的基本元素。无论是企业网络架构、互联网连接&#xff0c;还是局域网&#xff08;LAN&#xff09;配置&#xff0c;它们都起着至关重要的作用。理解它们的工作原理&a…...

C#如何调用执行命令行窗口(CMD)

一、引言 在 C# 的编程世界里&#xff0c;我们常常会遇到需要与操作系统底层进行交互的场景。这时&#xff0c;调用命令行窗口&#xff08;CMD&#xff09;就成为了一个强大的工具。无论是自动化日常任务&#xff0c;还是执行外部程序和批处理文件&#xff0c;通过 C# 调用 CM…...

vim练级攻略(精简版)

vim推荐配置: curl -sLf https://gitee.com/HGtz2222/VimForCpp/raw/master/install.sh -o ./install.sh && bash ./install.sh 0. 规定 Ctrl-λ 等价于 <C-λ> :command 等价于 :command <回车> n 等价于 数字 blank字符 等价于 空格&#xff0c;tab&am…...

一文速通Java的JDBC编程

目录 &#x1f43d;JDBC的引入 什么是API JDBC的概念及作用 &#x1f347;准备工作 数据库驱动包 下载第三方库 &#x1f43e;JDBC 使用 将jar包导入项目 通过代码使用JDBC的API (1)创建数据源对象并设置属性 (2)和数据库服务器建立网络连接 (3)程序构造SQL语句 (…...

laravel中请求失败重试的扩展--Guzzle

背景 开发过程中&#xff0c;跟外部接口对接时&#xff0c;很常见的要考虑到失败重新的情况&#xff0c;这里记录一下我用的失败重试的情况&#xff0c; 重试方法 1、使用 Laravel 的 HTTP 客户端和异常处理 结合异常处理和重试逻辑 use Illuminate\Support\Facades\Http;…...

如何在vue中渲染markdown内容?

文章目录 引言什么是 markdown-it&#xff1f;安装 markdown-it基本用法样式失效&#xff1f;解决方法 高级配置语法高亮 效果展示 引言 在现代 Web 开发中&#xff0c;Markdown 作为一种轻量级的标记语言&#xff0c;广泛用于文档编写、内容管理以及富文本编辑器中。markdown…...

Mysql MVCC

MVCC 什么是MVCC MVCC&#xff08;多版本并发控制&#xff0c;Multi-Version Concurrency Control&#xff09; 是一种用于数据库管理系统&#xff08;DBMS&#xff09;中的并发控制机制&#xff0c;它允许多个事务同时执行而不互相阻塞&#xff0c;并通过创建数据的多个版本…...

Spring6.0新特性-HTTP接口:使用@HttpExchange实现更优雅的Http客户端

文章目录 一、概述二、使用1、创建接口HttpExchange方法2、创建一个在调用方法时执行请求的代理3、方法参数4、返回值5、错误处理&#xff08;1&#xff09;为RestClient&#xff08;2&#xff09;为WebClient&#xff08;3&#xff09;为RestTemplate 注意 一、概述 官方文档…...

springboot医院信管系统

摘 要 随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理系统应运而生&#xff0c;各行各业相继进入信息管理时代&a…...

迅为RK3568开发板篇OpenHarmony实操HDF驱动控制LED-编写内核 LED HDF 驱动程序

接下来编译 LED 驱动&#xff0c;该驱动用于在基于华为设备框架&#xff08;HDF&#xff09;的系统中控制 LED 灯的开关&#xff0c;完整代码如下所示&#xff1a; 更多内容可以关注&#xff1a;迅为RK3568开发板篇OpenHarmony...

[javaWeb]初识Web

将该图片在浏览器中打印出来 代码&#xff1a; <html> <head> <title>HTML初识</title> </head> <body> <h1>猫猫</h1> <img src "img/1.jpg"> </body> &l…...

复健第二天之[MoeCTF 2022]baby_file

打开题目在线环境可以看到&#xff1a; 感觉要用伪协议去求&#xff0c;但是我们并不知道flag的位置&#xff0c;这里我选择用dirsearch去扫一下&#xff1a; 最像的应该就是flag.php了 于是就构建payload&#xff1a; **?filephp://filter/convert.base64-encode/resource…...

uniapp 微信小程序 editor 富文本编辑器

<view class"inp boxsizing"><view class"contentBox"><!-- 富文本编辑器 --><view classwrapper><view classtoolbar tap"format"><view :class"formats.bold ? ql-active : " class"iconfon…...

SparkSQL函数

文章目录 1. SparkSQL函数概述2. SparkSQL内置函数2.1 常用内置函数分类2.2 常用数组函数2.2.1 array()函数1. 定义2. 语法3. 示例 2.3 常用日期与时间戳函数2.4 常见聚合函数2.5 常见窗口函数 3. SparkSQL自定义函数3.1 自定义函数分类3.2 自定义函数案例演示 1. SparkSQL函数…...

从零开始学数据库 day2 DML

从零开始学数据库&#xff1a;DML操作详解 在今天的数字化时代&#xff0c;数据库的使用已经成为了各行各业的必备技能。无论你是想开发一个简单的应用&#xff0c;还是想要管理复杂的数据&#xff0c;掌握数据库的基本操作都是至关重要的。在这篇博客中&#xff0c;我们将专注…...

电脑换固态硬盘

参考&#xff1a; https://baijiahao.baidu.com/s?id1724377623311611247 一、根据尺寸和缺口可以分为以下几种&#xff1a; 1、M.2 NVME协议的固态 大部分笔记本是22x42MM和22x80MM nvme固态。 在京东直接搜&#xff1a; M.2 2242 M.2 2280 2、msata接口固态 3、NGFF M.…...

【大数据】机器学习------支持向量机(SVM)

支持向量机的基本概念和数学公式&#xff1a; 1. 线性可分的支持向量机 对于线性可分的数据集 &#xff0c;其中(x_i \in R^d) 是特征向量 是类别标签&#xff0c;目标是找到一个超平面 &#xff0c;使得对于所有 的样本 &#xff0c;对于所有(y_i -1) 的样本&#xff0c;…...

Android系统开发(八):从麦克风到扬声器,音频HAL框架的奇妙之旅

引言&#xff1a;音浪太强&#xff0c;我稳如老 HAL&#xff01; 如果有一天你的耳机里传来的不是《咱们屯里人》&#xff0c;而是金属碰撞般的杂音&#xff0c;那你可能已经感受到了 Android 音频硬件抽象层 (HAL) 出问题的后果&#xff01;在 Android 音频架构中&#xff0c…...

Golang Gin系列-2:搭建Gin 框架环境

开始网络开发之旅通常是从选择合适的工具开始的。在这个全面的指南中&#xff0c;我们将引导你完成安装Go编程语言和Gin框架的过程&#xff0c;Gin框架是Go的轻量级和灵活的web框架。从设置Go工作空间到将Gin整合到项目中&#xff0c;本指南是高效而强大的web开发路线图。 安装…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...