首页 > 编程语言 >【教3妹学编程-算法题】数组中两个数的最大异或值

【教3妹学编程-算法题】数组中两个数的最大异或值

时间:2023-11-04 11:06:02浏览次数:37  
标签:xNext nums 二进制位 编程 妹学 int 异或 num found

【教3妹学编程-算法题】数组中两个数的最大异或值_java代码

3妹:“太阳当空照,花儿对我笑,小鸟说早早早,你为什么背上炸药包”
2哥 :3妹,什么事呀这么开心呀。
3妹:2哥你看今天的天气多好啊,阳光明媚、万里无云、秋高气爽,适合秋游。
2哥:是啊,都快立冬了,天气还是这么热。今年的冬天比以往来的要晚一些。
3妹:晚来也是要来的,看天气预报 下周要降温,估计没几天这种暖的天气了。
2哥:注意保暖啊3妹,看你们女生还穿着裙子,不能只要美丽,就冻人啊。
3妹:我才不,天冷了我就穿秋裤,卷死她们。
2哥:说到卷她们,不如做一道题,在技术上卷死她们。 内外兼修~

 1题目: 

给你一个整数数组 nums ,返回 nums[i] XOR nums[j] 的最大运算结果,其中 0 ≤ i ≤ j < n 。

示例 1:

输入:nums = [3,10,5,25,2,8]
输出:28
解释:最大运算结果是 5 XOR 25 = 28.
示例 2:

输入:nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出:127

提示:

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1

 2思路: 

【教3妹学编程-算法题】数组中两个数的最大异或值_数组_02

假设我们已经确定了 x 最高的若干个二进制位,当前正在确定第 k 个二进制位。根据题意,我们希望第 k 个二进制位能够取到 1。
解题思路如代码中注释:

 3java代码: 

class Solution {
    // 最高位的二进制位编号为 30
    static final int HIGH_BIT = 30;


    public int findMaximumXOR(int[] nums) {
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            Set<Integer> seen = new HashSet<Integer>();
            // 将所有的 pre^k(a_j) 放入哈希表中
            for (int num : nums) {
                // 如果只想保留从最高位开始到第 k 个二进制位为止的部分
                // 只需将其右移 k 位
                seen.add(num >> k);
            }


            // 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
            // 我们将 x 的第 k 个二进制位置为 1,即为 x = x*2+1
            int xNext = x * 2 + 1;
            boolean found = false;
            
            // 枚举 i
            for (int num : nums) {
                if (seen.contains(xNext ^ (num >> k))) {
                    found = true;
                    break;
                }
            }


            if (found) {
                x = xNext;
            } else {
                // 如果没有找到满足等式的 a_i 和 a_j,那么 x 的第 k 个二进制位只能为 0
                // 即为 x = x*2
                x = xNext - 1;
            }
        }
        return x;
    }
}

标签:xNext,nums,二进制位,编程,妹学,int,异或,num,found
From: https://blog.51cto.com/u_6813689/8179632

相关文章

  • UE4中的C++编程简介
    对官方文档的学习链接利用UE创建一个C++基类在编辑器中可以选择父类,根据这个父类我们可以创建一个基类用于后续的蓝图类制作。以Actor父类为例创建基类,其头文件会包含一个构造函数,一个Tick函数的重载和一个BeginPlay函数的重载。BeginPlay函数告诉Actor以可运行状态进入了游戏......
  • JUC并发编程学习笔记(七)常用的辅助类
    常用的辅助类CountDownLatch这是一个JUC计数器辅助类,计数器有加有减,这是减。使用方法packageorg.example.demo;importjava.util.concurrent.CountDownLatch;//线程计数器publicclassCountDownLatchDemo{publicstaticvoidmain(String[]args){Cou......
  • JUC并发编程学习笔记(六)Callable(简单)
    Callable(简单)callable接口和runnable接口类似,都是为了执行另外一条线程而设计的,区别是Runnable不会返回结果也不会抛出异常。1、可以有返回值2、可以抛出异常3、方法不同;run()/call();Runnable实现Runnable接口,重写run方法,无返回值//原线程classRunnableThreadimple......
  • 突破性的多语言代码大模型基CodeShell:引领AI编程新时代
    突破性的多语言代码大模型基CodeShell:北京大学与四川天府银行联合打造,引领AI编程新时代1.CodeShell简介CodeShell是北京大学知识计算实验室联合四川天府银行AI团队研发的多语言代码大模型基座。它拥有70亿参数,经过对五千亿Tokens的训练,并具有8192的上下文窗口长度。CodeShell在......
  • 突破性的多语言代码大模型基CodeShell:引领AI编程新时代
    突破性的多语言代码大模型基CodeShell:北京大学与四川天府银行联合打造,引领AI编程新时代1.CodeShell简介CodeShell是北京大学知识计算实验室联合四川天府银行AI团队研发的多语言代码大模型基座。它拥有70亿参数,经过对五千亿Tokens的训练,并具有8192的上下文窗口长度。CodeShell在......
  • 实验3—C语言函数应用编程
    1、实验任务1源代码1#include<stdio.h>2#include<stdlib.h>3#include<time.h>4#include<windows.h>5#defineN806voidprint_text(intline,intcol,chartext[]);//函数声明7voidprint_spaces(intn);//函数声明8voidprint_b......
  • 编程猫11岁学员拿到NOC决赛一等奖,妈妈分享教育心得
    来自广州的龙芷盈今年11岁,上五年级。她在编程猫学习编程快三年的时间,已经拿到了蓝桥杯国赛二等奖、NOC决赛一等奖。小盈妈妈说“小盈平常有点难管教、很倔强”,但同时也是个有主见、有规划的孩子,她会自己做好学习规划和时间管理,这也让她在学校和编程猫的学习中都收获了很好的成......
  • 零代码编程:用ChatGPT批量重命名多个子文件夹里面的文件标题名
    一个文件夹:D:\英语学习图书配套资源\亲子英语游戏书,这本最好玩,里面有多个子文件夹:子文件夹里面的文件要重命名,将文件名称中的track替换为子文件夹名称:在ChatGPT中输入提示词:你是一个Python编程专家,要完成一个批量删除掉对话音频文件开头的任务,具体步骤如下:打开文件夹:D:\英语学习图......
  • 字节笔试题-区间异或
    题目给两个长度为n的数组a,b,请你计算出有多少个区间[l,r],满足\(a_{l}\oplusa_{l+1}\oplusa_{l+2}\oplus\ldots\oplusa_{r}=b_{l}\oplusb_{l+2}\oplusb_{l+2}\oplus\ldots\oplusb_{r}\)(\(\oplus\)表示按位异或)输入描述第一行输入一个整数n,表示数组长度。第二行输......
  • [Linux] shell编程之数组 [转载]
    1概述数组是Shell的一种特殊变量,是一组数据的集合,里面的每个数据被称为一个数组元素。当前Bash仅支持一维索引数组和关联数组,Bash对数组的大小没有限制。2定义数组2.1一维索引数组方法1#定义一个空数组array=()#为数组元素赋值array1[0]=aarray1[1]=barray......