位运算专题——常见位运算位图的使用力扣实战应用

2024-09-03 11:36

本文主要是介绍位运算专题——常见位运算位图的使用力扣实战应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1、常见位运算

2、算法应用【leetcode】

2.1 判断字符是否唯一【面试题 】

 2.1.1 算法思想【位图】

 2.1.2 算法代码

2.2 只出现一次的数字 III

2.2.1 算法思想

2.2.2 算法代码

2.3 丢失的数字

2.3.1 算法思想

2.3.2 算法代码

2.4 两整数之和

2.4.1 算法思想

2.4.2 算法代码

2.5 只出现一次的数字 II

2.5.1 算法思想

2.5.2 算法代码

2.6 消失的两个数字【面试题】(leetcode难度:困难)

2.6.1 算法思想

2.6.2 算法代码


1、常见位运算

想要灵活使用位运算,基础的位运算操作是我们必须掌握的,常见位运算操作如下:

  1. 基础位运算操作符
  2. 判断某一数二进制表示中第x位是0还是1
  3. 如何将某一数其二进制表示中第x位修改为1
  4. 如何将某一数其二进制表示中第x位修改为0
  5. 掌握位图思想
  6. 提取某一数二进制表示中最右侧的1
  7. 干掉某一数二进制表示中最右侧的1(将右侧的1修改为0)
  8. 位运算符的优先级
  9. 异或(^)的使用

大家可以先思考,尽可能的多想,答案总结我放在下图中。 


2、算法应用【leetcode】

2.1 判断字符是否唯一【面试题 】

. - 力扣(LeetCode)

 2.1.1 算法思想【位图】

本题解法具有多种,可以使用哈希表,也可以使用位图,这里给出最优的位图解法(节省空间消耗)。

因为字符均为小写字母,共有26个不同字符,而位图最多有32个bit位,故可使用位图。

  1. 每个字符占一个bit位
  2. 遍历字符串,将出现的字符其位图中的位置设置为1
  3. 设置前先查看位图,若为0,则设置为1;若为1,则说明该字符已经出现过了,为重复字符,返回false。

 2.1.2 算法代码

class Solution {public boolean isUnique(String astr) {//鸽巢原理if(astr.length() > 26) return false;//位图int bitMap = 0;for(int i = 0; i < astr.length(); i++) {//确定该字符在位图中的位置int bit = astr.charAt(i) - 'a';//该字符已经出现过了if((bitMap & (1 << bit)) != 0) return false;//该字符没有出现过,设置为1else bitMap |= (1 << bit);}return true;}
}

2.2 只出现一次的数字 III

. - 力扣(LeetCode)

2.2.1 算法思想

  1. 因为数组中恰好有两个元素只出现一次,其余所有元素均出现两次,故我们可以利用异或(^)运算符“消消乐”的特性,将全部元素异或,得到的结果就是这两个不同的元素相异或的结果x
  2. 因为这两个元素不同,故x一定不为0,其二进制表示中一定有某一bit位为1,而我们可以使用"x & (-x)"提取出最右侧的1
  3. 而这两个不同的元素中的这一bit位一定是不相同的,根据这个特性,将数组中的元素分为两组,一组为元素二进制的这一位为0,一组为元素二进制的这一位为1,将不同组中的元素相异或,(重复元素再次消去)就得到这两个单独出现的元素

2.2.2 算法代码

class Solution {public int[] singleNumber(int[] nums) {int x = 0;for (int num : nums) {x ^= num;}int last1 = x & -x;int[] ret = new int[2]; for(int num : nums) {ret[(num & last1) == 0 ? 0 : 1] ^= num;}/**for (int num : nums) {int val = num & last1;if (val == 0) {ret[0] ^= num;} else {ret[1] ^= num;}} */return  ret;}
}

2.3 丢失的数字

. - 力扣(LeetCode)

2.3.1 算法思想

解题思想很简单,只需将数组中的数据和原应出现的数据相异或,得到的就是确实的数据。

注意:不需额外创建数组来表示[0,n]中原应出现的数据,只需在遍历原数组的同时,异或上下标i即可。

2.3.2 算法代码

class Solution {public int missingNumber(int[] nums) {//异或位运算int x = 0;int len = nums.length;for(int i = 0; i < len; i++) {x ^= (nums[i] ^ i);}return x ^ len;}
}

2.4 两整数之和

. - 力扣(LeetCode)

2.4.1 算法思想

解决本题,我们需要充分的了解异或运算符(^)的特性——无进位相加。

  1. 我们可以通过异或得到两数无进位相加的结果res
  2. 接着使用 & 得到两数相加的进位结果,因为是进位的结果,所以还要左移一位,得到carry
  3. 将carry和res相加就得到最终结果(因为不能使用+,所以要循环以上过程,直至进位为0)

2.4.2 算法代码

class Solution {public int getSum(int a, int b) {//无进位相加(异或)int res = a ^ b;//得到进位int carry = (a & b) << 1;while(carry != 0) {a = res;b = carry;res = a ^ b;carry = (a & b) << 1;}return res;}
}

2.5 只出现一次的数字 II

. - 力扣(LeetCode)

2.5.1 算法思想

  1.  因为每一个重复出现的元素的次数都是相等的(n),所以每个相同元素的某一bit位之和也是n的倍数。
  2. 所以我们可以进行取模运算(%)得到单独出现的那个元素的bit位数值。
  3. 循环32次,便能得到该元素的准确数值

2.5.2 算法代码

class Solution {public int singleNumber(int[] nums) {int ret = 0;for(int x = 0; x <32; x++) {int bitSum = 0;for(int n : nums) {bitSum += (n >> x) & 1;}//得到单独出现元素的比特位数值//bit %= n;bitSum %= 3;ret |= (bitSum << x);}return ret;}
}

2.6 消失的两个数字【面试题】(leetcode难度:困难)

2.6.1 算法思想

虽然力扣为本题标注的难度为困难级别,实际上也并不困难。

本题解法非常简单,其实就是上文 丢失的数字+只出现一次的数字III 两题思想的结合,如果你跟着本文一步一步的学习下来,那解决本题就是分分钟钟的事,非常的简单。

  1. 将应出现的完整数据和数组数据进行整体异或,得到缺失的两个数字的异或结果。
  2. 提取最右侧的1,并将应出现的完整数据和数组数据进行分组异或,就得到所消失的两个数字。

2.6.2 算法代码

class Solution {public int[] missingTwo(int[] nums) {//丢失的数字 + 只出现一次的数字IIIint n = nums.length;int[] ret = new int[2];int x = 0;//得到两数异或结果for(int i = 1; i <= n + 2; i++) x ^= i;for(int i = 0; i < n; i++) x ^= nums[i];//提取最右侧1int check = x & (-x);//分组异或 --> 得到结果for(int num : nums) ret[(num & check) == 0 ? 0 : 1] ^= num;for(int i = 1; i <= n + 2; i++) ret[(i & check) == 0 ? 0 : 1] ^= i;return ret;}
}

END

这篇关于位运算专题——常见位运算位图的使用力扣实战应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

C#中Guid类使用小结

《C#中Guid类使用小结》本文主要介绍了C#中Guid类用于生成和操作128位的唯一标识符,用于数据库主键及分布式系统,支持通过NewGuid、Parse等方法生成,感兴趣的可以了解一下... 目录前言一、什么是 Guid二、生成 Guid1. 使用 Guid.NewGuid() 方法2. 从字符串创建

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法