刷题训练之位运算

embedded/2024/9/21 13:23:30/

> 作者:დ旧言~
> 座右铭:松树千年终是朽,槿花一日自为荣。

> 目标:熟练掌握位运算算法

> 毒鸡汤:学习,学习,再学习 ! 学,然后知不足。

> 专栏选自:刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕 

🌟前言分析

        最早博主续写了牛客网130道题,这块的刷题是让同学们快速进入C语言,而我们学习c++已经有一段时间了,知识储备已经足够了但缺少了实战,面对这块短板博主续写刷题训练,针对性学习,把相似的题目归类,系统的刷题,而我们刷题的官网可以参考:​​​​​​

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,求职就业一站解决_牛客网

⭐知识讲解

这里我们不用文字讲述了,我们直接看看下面的图解,让我们了解什么是位运算算法

 🌙topic-->1

题目链接:1.位运算

 

题目分析:

实现一个算法,确定一个字符串 s 的所有字符是否全都不同,全部不同返回 true ,相同返回 false

算法原理:

  • 解法一:(哈希表)

每个字母都映射在 hash[26] 中 ,再判断hash是否有重复的字母。

  1. 时间复杂度为:O(n)
  2. 空间复杂度:O(n)
  • 解法二:

采用位图的算法原理(这里不是直接创建一个位图,而是用位运算构建一个位图)

图解:

细节(优化):

采用鸽巢原理(抽屉原理),来优化。

代码演示:

class Solution 
{
public:bool isUnique(string astr) {// 使用鸽巢原理来做优化if(astr.size() > 26) return false;int bitMap = 0;// 循环for(auto ch : astr){int i = ch - 'a';// 先判断字符是否已经出现过if( ( (bitMap >> i) & 1) == 1)return false;// 把当前字符加入到位图中bitMap |= (1 << i);}return true;}
};

 🌙topic-->2

题目链接:2.位运算

 

题目分析:

给一个包含  [  0 ,  n ] 中 n 个数的数组 nums,找出[  0 ,  n ]缺失的数字,

  • 如果[3,0,1]:缺失2
  • 如果[0,1]:缺失1

算法原理:

  • 解法一:(哈希表)

每个字母都映射在 hash[26] 中 ,再判断hash是否有重复的字母。

  1. 时间复杂度为:O(n)
  2. 空间复杂度:O(n)
  • 解法二:(高斯求和)

这个公式就是高中的求和公式(等差公式求前 N 项)。

  • 解法三:位图(我们讲解这个)

采用位图的算法原理(这里不是直接创建一个位图,而是用位运算构建一个位图)

图解:

代码演示:

class Solution 
{
public:int missingNumber(vector<int>& nums) // 消消乐{int ret = 0; for(auto x : nums)ret ^= x;for(int i = 0;i <= nums.size();i++)ret ^= i;// 返回return ret;}
};

 🌙topic-->3

题目链接:3.位运算

 

题目分析:

给两个数子字,求两个整数和(我们不能用 + -来计算)

这到题可以偷鸡直接返回  return a+b

算法原理:

  • 解法:位运算

图解:

代码演示:

class Solution 
{
public:int getSum(int a, int b) {while(b != 0){int x = a ^ b;unsigned int carry = (unsigned int)(a & b) << 1;// 算出进位a = x;b = carry;}return a;}
};

  🌙topic-->4

题目链接:4.位图运算

 

题目分析:

在一个数组中只有两类数字,一种是出现3次,另一种是出现1次,找出出现一次的数字。

算法原理:

  • 解法:位图(我们讲解这个)

采用位图的算法原理(这里不是直接创建一个位图,而是用位运算构建一个位图)

图解:

代码演示:


class Solution {
public:int singleNumber(vector<int>& nums){int ret = 0;// 依次去修改 ret 中的每一位for (int i = 0; i < 32; i++){int sum = 0;for (int x : nums) // 计算nums中所以的数的第 i 位的和if (((x >> i) & 1) == 1)sum++;sum %= 3;// 判断if (sum == 1)ret |= 1 << i;}return ret;}
};

 🌙topic-->5

题目链接:5.位运算

 

题目分析:

给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?

以任意顺序返回这两个数字均可。

算法原理:

  • 解法:位图(我们讲解这个)

采用位图的算法原理(这里不是直接创建一个位图,而是用位运算构建一个位图)

图解:

代码演示:

class Solution
{
public:vector<int> missingTwo(vector<int>& nums){// 1. 将所有的数异或在⼀起int tmp = 0;for (auto x : nums) tmp ^= x;for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;// 2. 找出 a,b 中⽐特位不同的那⼀位int diff = 0;while (1){if (((tmp >> diff) & 1) == 1) break;else diff++;}// 3. 根据 diff 位的不同,将所有的数划分为两类来异或int a = 0, b = 0;for (int x : nums)if (((x >> diff) & 1) == 1) b ^= x;else a ^= x;for (int i = 1; i <= nums.size() + 2; i++)if (((i >> diff) & 1) == 1) b ^= i;else a ^= i;return { a, b };}
};

🌟结束语

       今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。


http://www.ppmy.cn/embedded/25869.html

相关文章

设计模式-命令模式(Command Pattern)结构|原理|优缺点|场景|示例

设计模式&#xff08;分类&#xff09; 设计模式&#xff08;六大原则&#xff09; 创建型&#xff08;5种&#xff09; 工厂方法 抽象工厂模式 单例模式 建造者模式 原型模式 结构型&#xff08;7种&#xff09; 适配器…

百度地图与特斯拉合作,高级辅助驾驶地图获批

4月30日讯&#xff0c;记者从自然资源部网站上获悉&#xff0c;百度地图近期有多个《高级辅助驾驶地图》获得自然资源部批准。这些地图不仅用于车机导航服务&#xff0c;其中由百度智图科技有限公司提交的GS&#xff08;2023&#xff09;4634号高级辅助驾驶地图被指出是与特斯拉…

java的容器简介

容器的概念 容器指的是用于容纳收藏某种物体并进行一定程度管理的器具&#xff0c;这种东西在我们的日常生活中是非常常见的&#xff0c;比如我们吃饭时用到的锅碗瓢盆这些都是容器的范畴&#xff0c;可见容器是一个非常宽泛的概念。 在java中我们将容器的概念抽象出来&#xf…

Python语言第五章之字符串

字符串 字符串就是一串字符, 是编程语言中表示文本的数据类型 1. 字符串表示 单引号 双引号 多引号 多行字符串, 有空格默认一个空格, 占一个位置 str1 "hello world" str3 666你好 str2 """ what where who """ 2. 获取字符…

Windows Server 2019/2022 开启

我的环境是Windows Serve 2022 Datacenter, 21H2, 需要使用Hyper-V 与 VMWare Workstation共存&#xff0c;但是在服务器管理器中找不到Windows Hypervisor Platform安装选项。在Win10中是启动关闭Windows功能中&#xff0c;而server中找不到。 解决方法&#xff1a; 以管理员…

CTFHub-Web-SQL注入

CTFHub-SQL注入-WP 1.整数型注入 1.题目说输入1&#xff0c;先将1输入查看结果 2.接着输入4-1&#xff0c;发现输出的结果为4-1&#xff0c;判定存在整数型注入 3.查询字段数&#xff0c;出现了回显&#xff0c;判断这里的字段数为2 1 order by 24.判断注入点在2的位置&…

Microsoft Threat Modeling Tool 使用(二)

主界面 翻译 详细描述 选择了 “SDL TM Knowledge Base (Core)” 模板并打开了一个新的威胁模型。这个界面主要用于绘制数据流图&#xff08;Data Flow Diagram, DFD&#xff09;&#xff0c;它帮助您可视化系统的组成部分和它们之间的交互。以下是界面中各个部分的功能介绍&a…

通过swagger在线地址生成前端接口调用

下载模块 npm install fs npm install path-browserify npm install http 新建autoGen.js文件 const fs require(fs); const path require(path-browserify); let apiData {} // 访问swagger.json的数据 const http require(http);const apiUrl http://localhost:8001/sw…