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

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

相关文章

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

MySQL中比较运算符的具体使用

《MySQL中比较运算符的具体使用》本文介绍了SQL中常用的符号类型和非符号类型运算符,符号类型运算符包括等于(=)、安全等于(=)、不等于(/!=)、大小比较(,=,,=)等,感兴趣的可以了解一下... 目录符号类型运算符1. 等于运算符=2. 安全等于运算符<=>3. 不等于运算符<>或!=4. 小于运

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

使用Python构建一个高效的日志处理系统

《使用Python构建一个高效的日志处理系统》这篇文章主要为大家详细讲解了如何使用Python开发一个专业的日志分析工具,能够自动化处理、分析和可视化各类日志文件,大幅提升运维效率,需要的可以了解下... 目录环境准备工具功能概述完整代码实现代码深度解析1. 类设计与初始化2. 日志解析核心逻辑3. 文件处

Java docx4j高效处理Word文档的实战指南

《Javadocx4j高效处理Word文档的实战指南》对于需要在Java应用程序中生成、修改或处理Word文档的开发者来说,docx4j是一个强大而专业的选择,下面我们就来看看docx4j的具体使用... 目录引言一、环境准备与基础配置1.1 Maven依赖配置1.2 初始化测试类二、增强版文档操作示例2.

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)