【算法】位运算合集

8e19eee2be5648b78d93fbff2488137b.png

阿华代码，不是逆风，就是我疯

你们的点赞收藏是我前进最大的动力！！

希望本文内容能够帮助到你！！

目录

零：位运算基础公式

零：五道基础题

1：位1的个数

2：比特位计数

3：汉明距离

4：只出现一次的数字|

5：只出现一次的数字|||

一：判定字符是否唯一

1：位图思想总结

2：位图思想和hash表两种方法

二：丢失的数字

三：两整数之和

四：只出现一次的数字||

五：消失的两个数字

 

零：位运算基础公式

69f072b1f40c4f8da1bc5715ce208e54.png

f2ebc62df8b746e4b68259683f3e697d.png

零：五道基础题

1：位1的个数

191. 位1的个数

a57c502ead044c26879b9cb92254cc77.png

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            n &= (n-1);  //干掉n最右侧的1
            count++;
        }        
        return count;
    }
}

2：比特位计数

338. 比特位计数

022fe6e95f9c4175a40c026ef8ea5492.png

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n+1];
        for(int i = 0 ; i <= n ; i++ ){
            int count = 0 , tem = i;
            while(tem != 0){
                tem &= (tem-1);//干掉最右侧的1
                count++;
            }
            ans[i] = count;
        }
        return ans;
        
    }
}

3：汉明距离

461. 汉明距离

f416f02d674e4ea1a386b3b221539b80.png

class Solution {
    public int hammingDistance(int x, int y) {
        int tem = x ^ y;
        int count = 0;
        while(tem != 0){
            tem &= (tem-1);
            count++;
        }
        return count;

    }
}

4：只出现一次的数字|

136. 只出现一次的数字

b14cfd3025944200b422eef05074b9d3.png

class Solution {
    public int singleNumber(int[] nums) {
        int ret = nums[0];
        for(int i = 1 ; i < nums.length ; i++){
            ret ^= nums[i];    
        }
        return ret;

    }
}

5：只出现一次的数字|||

260. 只出现一次的数字 III

用位上数字不同进行分组

7ff400c936654a1988e560da5ba2cfd9.png

class Solution {
    public int[] singleNumber(int[] nums) {
        int ret = 0;
        for(int x : nums){
            ret ^= x; 
        }

        int sign = ret & (-ret);
        int firNum = 0;
        int secNum = 0;
        for(int x : nums){
            if((sign & x) == 0){
                firNum ^= x;
            }else{
                secNum ^= x;
            }
        }
        int[] result = new int[2];
        result[0] = firNum;
        result[1] = secNum;
        return result;

    }
}

 

一：判定字符是否唯一

面试题 01.01. 判定字符是否唯一

1：位图思想总结

9510a6965e064df199f612dcdb349959.png

c217580a605d4f00820c4a085f303bc8.png

2：位图思想和hash表两种方法

709f1da6ac0146a89799edf98757f667.png

class Solution {
    public boolean isUnique(String astr) {
        //鸽巢原理优化
        if(astr.length() > 26){
            return false;
        }
         //位图原理
         char[] str = astr.toCharArray();
         int bitMap = 0;
         for(int x : str){
            int move = x - 'a';
            if((bitMap & (1 << move)) == 0){
                //bitMap&0001000只有非0或者0两个结果 
                //说明当前bitMap位是0，那就添加进去
                bitMap |= (1 << move);
            }else{
                return false;
            }
         }
         return true;
    }
}

//1:把字符串转化为字符数组
        // char[] str = astr.toCharArray();
        // //2:把字符扔到hash表中
        // Map<Character,Integer> hash = new HashMap<>();
        // for(char x : str){
        //     //获取hash表中x的value值
        //     int num = hash.getOrDefault(x,0);
        //     if(num == 0){
        //         hash.put(x,hash.getOrDefault(x,0)+1);
        //     }else{
        //         return false;
        //     }
        // }
        // return true;

二：丢失的数字

268. 丢失的数字

02e3fb40948d445b8a6f0ac6e8eb22a3.png

class Solution {
    public int missingNumber(int[] nums) {
       //高斯求和
       int len = nums.length;
       int sum1 = 0;
       for(int i = 0 ; i < len ; i++){
            sum1 += nums[i];
       }
       int sum2 = (0+len)*(len+1)/2;
       int ret = sum2 - sum1;
       return ret;
    }
}

        // hash数组
        // int len = nums.length;
        // int[] hash = new int[len+1];
        // for(int i = 0 ; i < len ; i++){
        //     hash[nums[i]] = 1;
        // }
        // int ret = 0;
        // for(int i = 0 ; i < len+1 ; i++){
        //     if(hash[i] == 0){
        //         ret = i;
        //     }else{

        //     }
        // }
        // return ret;




        // 异或运算方法
        // int len = nums.length;
        // int[] arr = new int[2*len+1];
        // for(int i = 0 ; i < len ; i++){
        //     arr[i] = nums[i];
        // }
        // int count = 0;        
        // for(int i = len ; i < (2*len+1) ; i++){//i作为添加元素的下标
        //     arr[i] = count;
        //     count++;
        // }
        // int ret = 0;
        // for(int x : arr){
        //     ret ^= x;
        // }
        // return ret;

三：两整数之和

371. 两整数之和

耍赖：直接return；正规军：异或运算无进位相加

2fa4ca506d5f4ffc8f7d101d67af4ae0.png

class Solution {
    public int getSum(int a, int b) {
        while(b != 0){
            int ret = a ^ b;//结果
            int x = (a & b)<<1;
            a = ret;
            b = x;
        }
        return a;
    }
}

        // return a + b;

四：只出现一次的数字||

137. 只出现一次的数字 II - 力扣（LeetCode）

2f60314acc204151886f1e4953ee1ae0.png

65f151292718402c96b5c78c540f0de5.png

class Solution {
    public int singleNumber(int[] nums) {
        //这一层for循环i作为比特位
        int ret = 0;
        for(int j = 0 ; j < 32 ; j++){
            //所有元素的该bit位相加
            int sum = 0;
            for(int i = 0 ; i < nums.length ; i++){
                sum += (nums[i]>>j)&1;
            }
            int tem = sum % 3;
            if(tem == 1){
                ret |= (1<<j);
            }else{
                ret &= ~(1<<j);
            }
        }
        return ret;

    }
}

五：消失的两个数字

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

b730107c48e64e1590f8c7fc36fac49d.png

class Solution {
    public int[] missingTwo(int[] nums) {
        //创建tem数组用来存放nums数组中的元素和1~N数字
        int len = nums.length;
        int n = len + 2;
        int[] tem = new int[2*len+2];
        //处理nums数组
        int ret = 0;
        for(int i = 0 ; i < nums.length ; i++){
            ret ^= nums[i];
            tem[i] = nums[i];
        }
        //处理1~N
        for(int i = 1 ; i <= n ; i++){
            ret ^= i;
            tem[len-1+i] = i;
        }
        int sign = 0;
        while(ret != 0){
            if( ((ret >> sign) & 1) == 1){
                break;
            }else{
                sign++;
            }
        }
        
        //基于sign把数组分成两组
        int[] result = new int[2];
        for(int x : tem){
            if(((x >> sign) & 1) == 1){
                result[0] ^= x;
            }else{
                result[1] ^= x;
            }
        }

        return result;


    
    }
}
class Solution {
    //穷举法
    public int[] missingTwo(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int[] ret = new int[2];
        int j = 0;
        for(int i = 0 ; i < nums.length-1 ; i++){
            int tem = nums[i+1] - nums[i];
            if(tem == 2){
                ret[j++] = nums[i]+1;
            }else if(tem == 3){
                ret[j++] = nums[i]+1;
                ret[j] = nums[i]+2;
            }
        }
        
        if(nums[0] != 1){
            if(ret[0] == 0){
            ret[0] = 1;
                if(len == 1){
                    if(nums[0]-1 > 1){
                        ret[1] = 2;
                    }else{
                        ret[1] = 3;
                    }
                }else{
                    ret[1] = nums[len-1]+1;
                }
            
            }else{
                if(ret[1] == 0){
                ret[1] = 1;
                }else{

                }
            }
        }else{
            if(ret[0] == 0){
                ret[0] = nums[len-1]+1;
                ret[1] = nums[len-1]+2;
            }else{
                if(ret[1] == 0){
                    ret[1] = nums[len-1]+1; 
                }else{

                }
            }
        }
        return ret;

    }
}

 

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Android 硬件抽象层（HAL）全解析：智能设备硬件协同揭秘

Android 硬件抽象层（HAL）全解析：智能设备硬件协同揭秘

在Android硬件抽象层&#xff08;HAL&#xff09;开发中&#xff0c;需要掌握许多底层技术&#xff0c;并熟悉如何将硬件驱动与Android系统的上层应用接口相集成。以下是HAL开发中需要掌握的核心技术和一些示例代码&#xff0c;以帮助理解其实现原理&#xff1a; 1. C/C编程和…
阅读更多...
Linux如何将文件或目录打成rpm包？-- rpmbuild打包详解

Linux如何将文件或目录打成rpm包？-- rpmbuild打包详解

&#x1f468;‍&#x1f393;博主简介 &#x1f3c5;CSDN博客专家   &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01…
阅读更多...
推荐学习笔记：矩阵补充和矩阵分解

推荐学习笔记：矩阵补充和矩阵分解

参考&#xff1a; 召回 fun-rec/docs/ch02/ch2.1/ch2.1.1/mf.md at master datawhalechina/fun-rec GitHub 业务 隐语义模型与矩阵分解 协同过滤算法的特点&#xff1a; 协同过滤算法的特点就是完全没有利用到物品本身或者是用户自身的属性&#xff0c; 仅仅利用了用户与…
阅读更多...
java引用第三方jar包，打包全流程

java引用第三方jar包，打包全流程

前言&#xff1a; 本文是使用maven引入第三方jar包&#xff0c;通过mvn命令打包。 以下为引入第三方jar包&#xff0c;打包进项目jar中的全流程步骤。 1、引入第三方jar包 1、放置路径 一般来说&#xff0c;放到项目(子项目)的resources的lib目录下。 2、pom引入 如图所示…
阅读更多...
【webApp之h5端实战】首页评分组件的原生实现

【webApp之h5端实战】首页评分组件的原生实现

关于评分组件，我们经常在现代前端框架中用到，UI美观效果丰富，使用体验是非常不错的。现在自己动手使用原生js封装下评分组件，可以用在自己的项目中。 组件实现原理 点击的❤左侧包括自己都是高亮的样式，右侧都是灰色的样式，这样就能把组件的状态区分开了。右边再加上辅…
阅读更多...
基于Java Springboot旅游攻略APP且微信小程序

基于Java Springboot旅游攻略APP且微信小程序

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 微信…
阅读更多...
ScratchLLMStepByStep：一步一步构建大语言模型教程

ScratchLLMStepByStep：一步一步构建大语言模型教程

前言 在学习大语言模型的时候&#xff0c;总会遇到各种各样的名词&#xff0c;像自注意力、多头、因果、自回归、掩码、残差连接、归一化等等。这些名词会让学习者听的云里雾里&#xff0c;觉得门槛太高而放弃。 本教程将会带你从零开始&#xff0c;一步一步的去构建每一个组…
阅读更多...
[MacOS] [kubernetes] MacOS玩转虚拟化最佳实践

[MacOS] [kubernetes] MacOS玩转虚拟化最佳实践

❓ 为什么不在MacOS本机安装呢&#xff1f;因为M系列芯片是Arm架构&#xff0c;与生产环境或者在本地调试时候&#xff0c;安装虚拟镜像和X86不同&#xff0c;造成不必要的切换环境的额外成本&#xff0c;所以在虚拟化的x86调试 步骤 & 详情 一: 安装OrbStack & 并配置…
阅读更多...
MySQL的用户管理和密码管理

MySQL的用户管理和密码管理

用户的密码管理 给用户改密码 初始化mysql后设置初始密码 mysqladmin -uroot password wzy666 改变已有密码 mysqladmin -uroot -pwzy666 password wzy999 SQL语句改&#xff0c;前提是已经进入数据库 alter user rootlocalhost identified by 123456; # 利用数据库服务…
阅读更多...
SQLite：DDL（数据定义语言）的基本用法

SQLite：DDL（数据定义语言）的基本用法

SQLite&#xff1a;DDL&#xff08;数据定义语言&#xff09;的基本用法 1 主要内容说明2 相关内容说明2.1 创建表格&#xff08;create table&#xff09;2.1.1 SQLite常见的数据类型2.1.1.1 integer&#xff08;整型&#xff09;2.1.1.2 text&#xff08;文本型&#xff09;2…
阅读更多...
STM32--基于STM32的智能家居设计与实现

STM32--基于STM32的智能家居设计与实现

本文详细介绍基于STM32F103C8T6的智能家居设计与实现&#xff0c;详细设计资料见文末链接 一、功能模块介绍 智能家居系统系统图如下所示&#xff0c;主要包括温湿度传感器、OLED液晶显示&#xff0c;WIFI物联网模块、人体红外预警模块、烟雾传感器模块、蜂鸣器模块 &#…
阅读更多...
基于Java Springboot校园导航微信小程序

基于Java Springboot校园导航微信小程序

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse微信开发…
阅读更多...
在 uniapp 项目中使用 Iconify 字体图标库

在 uniapp 项目中使用 Iconify 字体图标库

本文示例在 uniapp 项目中对 Iconify 字体图标库的安装和使用&#xff08;Iconify 字体图标库是一个免费开源的图标库&#xff0c;它拥有超过20万个开源矢量图标。&#xff09; 注&#xff1a;本文示例使用的是其 vue3 版本 安装 npm install --save-dev iconify/vue 注&am…
阅读更多...
WPF+LibVLC开发播放器-LibVLC播放控制

WPF+LibVLC开发播放器-LibVLC播放控制

接上一篇&#xff1a; LibVLC在C#中的使用 实现LibVLC播放器播放控制 界面 界面上添加一个Button按钮用于控制播放 <ButtonGrid.Row"1"Width"88"Height"24"Margin"10,0,0,0"HorizontalAlignment"Left"VerticalAlignme…
阅读更多...
ffmpeg安装及配置简单教程

ffmpeg安装及配置简单教程

这是ffmpeg官方网站&#xff1a;https://ffmpeg.org/ 这是ffmpeg提供了其他版本的网站&#xff1a;Builds - CODEX FFMPEG gyan.dev 这是ffmpeg提供了提前编译好的可执行文件的github托管网站&#xff1a; https://github.com/BtbN/FFmpeg-Builds/releases 一般windows版本…
阅读更多...
Qt-界面优化QSS

Qt-界面优化QSS

QSS介绍 先说下CSS&#xff1a; 在⽹⻚前端开发领域中, CSS 是⼀个⾄关重要的部分. 描述了⼀个⽹⻚的 "样式". 从⽽起到对⽹⻚美化的作⽤。 Qt 仿照 CSS 的模式, 引⼊了 QSS, 来对 Qt 中的控件做出样式上的设定 。 CSS的功能很强大&#xff0c;QSS要逊色一些&#…
阅读更多...
后端-一对一的数据封装的两种写法对比

后端-一对一的数据封装的两种写法对比

方式一特点&#xff1a;上面的普通封装可以删掉&#xff0c;也可以留着。 注意⚠️&#xff1a;下面的特殊封装的property的值是属性.字段。&#xff08;category.id...) column是sql重命名之后的字段&#xff0c;如果没有重命名是数据库中的值。 方式二特点&#xff1a;上面的…
阅读更多...
CTF之密码学（密码特征分析）

CTF之密码学（密码特征分析）

一.MD5,sha1,HMAC,NTLM 1.MD5&#xff1a;MD5一般由32/16位的数字(0-9)和字母(a-f)组成的字符串 2.sha1&#xff1a;这种加密的密文特征跟MD5差不多&#xff0c;只不过位数是40&#xff08;sha256&#xff1a;64位&#xff1b;sha512:128位&#xff09; 3.HMAC&#xff1a;这…
阅读更多...
网络安全框架及模型-PPDR模型

网络安全框架及模型-PPDR模型

网络安全框架及模型-PPDR模型 概述： 为了有效应对不断变化的网络安全环境，人们意识到需要一种综合性的方法来管理和保护网络安全。因此，PPDR模型应运而生。它将策略、防护、检测和响应四个要素结合起来，提供了一个全面的框架来处理网络安全问题。 工作原理： PPDR模型的…
阅读更多...
QT6学习第八天 QFrame 类

QT6学习第八天 QFrame 类

QT6学习第八天 QFrame 类族QLabel 标签部件按钮部件QLineEdit 行编辑器部件QAbstractSpinBoxQAbstractSlider 今天来学一学 QFrame 类。 QFrame 类族 QFrame 类是带有边框的部件的基类。它的子类包括常用的标签部件 QLabel、以及 QLCDNumber、QSplitter、QStackedWidget、QToo…
阅读更多...
最新文章

Copyright @ 2022~2023