C++之位算法

位算法

在这里插入图片描述

常见位运算总结

在这里插入图片描述
在这里插入图片描述

位1的个数

给定一个正整数 n,编写一个函数,获取一个正整数的二进制形式并返回其二进制表达式中

设置位

的个数(也被称为汉明重量)。

示例 1:

输入:n = 11
输出:3
解释:输入的二进制串 1011 中,共有 3 个设置位。

示例 2:

输入:n = 128
输出:1
解释:输入的二进制串 10000000 中,共有 1 个设置位。

示例 3:

输入:n = 2147483645
输出:30
解释:输入的二进制串 1111111111111111111111111111101 中,共有 30 个设置位。

提示:

  • 1 <= n <= 231 - 1

代码如下:

class Solution {
public:int hammingWeight(uint32_t n) {int ret=0;for(int i=0;i<32;i++){if(n&(1<<i)){ret++;}}return ret;}
};

比特位计数

给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1:

输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10

示例 2:

输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示:

  • 0 <= n <= 105

代码如下:

class Solution {
public:
int countOnes(int x)
{int ones=0;while(x>0){x&=(x-1);ones++;}return ones;
}vector<int> countBits(int n) {vector<int>bits(n+1);for(int i=0;i<=n;i++){bits[i]=countOnes(i);}return bits;}
};

汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 xy,计算并返回它们之间的汉明距离。

示例 1:

输入:x = 1, y = 4
输出:2
解释:
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2:

输入:x = 3, y = 1
输出:1

提示:

  • 0 <= x, y <= 231 - 1

代码如下:

class Solution {
public:int hammingDistance(int x, int y) {int s=x^y,ret=0;while(s){ret+=s&1;s>>=1;}return ret;}
};

只出现一次的数字

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

示例 1 :

输入:nums = [2,2,1]
输出:1

示例 2 :

输入:nums = [4,1,2,1,2]
输出:4

示例 3 :

输入:nums = [1]
输出:1

提示:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外,其余每个元素均出现两次。

代码如下:

class Solution {
public:int singleNumber(vector<int>& nums) {int value=0;for(auto e:nums){value ^=e;}return value;}
};

只出现一次的数字3

给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1:

输入:nums = [1,2,1,3,2,5]
输出:[3,5]
解释:[5, 3] 也是有效的答案。

示例 2:

输入:nums = [-1,0]
输出:[-1,0]

示例 3:

输入:nums = [0,1]
输出:[1,0]

提示:

  • 2 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • 除两个只出现一次的整数外,nums 中的其他数字都出现两次

代码如下:

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {unordered_map<int,int> freq;for(int num:nums){++freq[num];}vector<int> ans;for(const auto& [num,occ]:freq){if(occ==1)ans.push_back(num);}return ans;}
};

判断字符是否唯一

实现一个算法,确定一个字符串 s 的所有字符是否全都不同。

示例 1:

输入: s = "leetcode"
输出: false 

示例 2:

输入: s = "abc"
输出: true

限制:

  • 0 <= len(s) <= 100
  • s[i]仅包含小写字母
  • 如果你不使用额外的数据结构,会很加分。

在这里插入图片描述

解法(位图的思想)

算法思路

利⽤「位图」的思想,每⼀个「⽐特位」代表⼀个「字符,⼀个 int 类型的变量的 32 位⾜够 表⽰所有的⼩写字⺟。⽐特位⾥⾯如果是 0 ,表⽰这个字符没有出现过。⽐特位⾥⾯的值是 1 , 表⽰该字符出现过。

那么我们就可以⽤⼀个「整数」来充当「哈希表」。

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;}
};

丢失的数字

给定一个包含 [0, n]n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1:

输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 2:

输入:nums = [0,1]
输出:2
解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 3:

输入:nums = [9,6,4,2,3,5,7,0,1]
输出:8
解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。

示例 4:

输入:nums = [0]
输出:1
解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。

提示:

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

解法(位运算):

算法思路:

设数组大小为n,那么缺失之前的数据就是[0,n],数组中是在 [0, n] 中缺失⼀个数形成的序列.

如果我们把数组中的所有数,以及 [0, n] ,数组中是在 [0, n] 中缺失⼀个数形成 [0, 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;}
};

两整数之和

给你两个整数 ab不使用 运算符 +- ,计算并返回两整数之和。

示例 1:

输入:a = 1, b = 2
输出:3

示例 2:

输入:a = 2, b = 3
输出:5

提示:

  • -1000 <= a, b <= 1000

解法(位运算):

算法思路:

◦ 异或 ^ 运算本质是「⽆进位加法」;

◦ 按位与 & 操作能够得到「进位」;

◦ 然后⼀直循环进⾏,直到「进位」变成 0 为⽌

在这里插入图片描述

代码如下:

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

只出现一次的数字2

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1:

输入:nums = [2,2,3,2]
输出:3

示例 2:

输入:nums = [0,1,0,1,0,1,99]
输出:99

提示:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • nums 中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次

解法(⽐特位计数):

算法思路:

设要找的数位 ret 。

由于整个数组中,需要找的元素只出现了「⼀次」,其余的数都出现的「三次」,因此我们可以根 据所有数的「某⼀个⽐特位」的总和 %3 的结果,快速定位到 0 还是 1 。

这样,我们通过ret 的每⼀个⽐特位上的值,就可以将ret给还原出来

在这里插入图片描述

代码如下:

class Solution {
public:int singleNumber(vector<int>& nums) {int ret=0;for(int i=0;i<32;i++)// 依次去修改 ret 中的每⼀位{int sum=0;for(int x:nums)// 计算nums中所有的数的第 i 位的和if(((x>>i)&1)==1)//确定一个数的第X为是0还是1sum++;sum%=3;if(sum==1) ret|=1<<i;//将一个数的二进位数第X位修改成1}return ret;}
};

消失的两个数字

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

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

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示:

  • nums.length <= 30000

先将数组中的数和 [1, n + 2] 区间内的所有数「异或」在⼀起,问题就变成了:有两个数出 现了「⼀次」,其余所有的数出现了「两次」

在这里插入图片描述

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.rhkb.cn/news/462500.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JAVA利用方法实现四道题

目录 1.给定一个字符串 s &#xff0c;找到 它的第一个不重复的字符&#xff0c;并返回它的索引 。如果不存在&#xff0c;则返回-1 2.计算字符串最后一个单词的长度&#xff0c;单词以空格隔开。&#xff08;注&#xff1a;字符串末尾不以空格为结尾&#xff09; 3.如果在将所…

【教程】Git 标准工作流

前言 Git 是日常开发中常用的版本控制工具&#xff0c;配合代码托管仓库&#xff08;如&#xff0c;Github&#xff0c;GitLab&#xff0c;Gitee 等&#xff09;用来实现多人多版本的协作开发。 但是 Git 的命令纷繁复杂&#xff0c;多如累卵&#xff0c;不可能也不需要全部搞…

基于AI深度学习的中医针灸实训室腹针穴位智能辅助定位系统开发

在中医针灸的传统治疗中&#xff0c;穴位取穴的精确度对于治疗效果至关重要。然而&#xff0c;传统的定位方法&#xff0c;如体表标志法、骨度折量法和指寸法&#xff0c;由于观察角度、个体差异&#xff08;如人体姿态和皮肤纹理&#xff09;以及环境因素的干扰&#xff0c;往…

金融标准体系

目录 基本原则 标准体系结构图 标准明细表 金融标准体系下载地址 基本原则 需求引领、顶层设计。 坚持目标导向、问题导向、结果 导向有机统一&#xff0c;构建支撑适用、体系完善、科学合理的金融 标准体系。 全面系统、重点突出。 以金融业运用有效、保护有力、 管理高…

.NET 8 Web API 中的身份验证和授权

本次介绍分为3篇文章&#xff1a; 1&#xff1a;.Net 8 Web API CRUD 操作.Net 8 Web API CRUD 操作-CSDN博客 2&#xff1a;在 .Net 8 API 中实现 Entity Framework 的 Code First 方法https://blog.csdn.net/hefeng_aspnet/article/details/143229912 3&#xff1a;.NET …

Spring Boot 与 Vue 共铸卓越采购管理新平台

作者介绍&#xff1a;✌️大厂全栈码农|毕设实战开发&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 &#x1f345;获取源码联系方式请查看文末&#x1f345; 推荐订阅精彩专栏 &#x1f447;&#x1f3fb; 避免错过下次更新 Springboot项目精选实战案例 更多项目…

字符串统计(Python)

接收键盘任意录入&#xff0c;分别统计大小写字母、数字及其它字符数量&#xff0c;打印输出。 (笔记模板由python脚本于2024年11月02日 08:23:31创建&#xff0c;本篇笔记适合熟悉python字符串并懂得基本编程技法的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xf…

qt QScrollArea详解

1、概述 QScrollArea是Qt框架中的一个控件&#xff0c;它提供了一个可滚动的视图区域&#xff0c;用于显示超出视图大小的内容。这个控件非常有用&#xff0c;尤其是在处理大型表格、文本区域、图像集合或任何需要滚动浏览的内容时。QScrollArea本身不直接显示内容&#xff0c…

HTML 基础标签——元数据标签 <meta>

文章目录 1. `<meta>` 标签概述2. 属性详解2.1 `charset` 属性2.2 `name` 属性2.3 `content` 属性2.4 `http-equiv` 属性3. 其他常见属性小结在 HTML 文档中,元数据标签 <meta> 是一种重要的标签,用于提供关于文档的信息,这些信息不直接显示在网页内容中,但对于…

InnoDB: corruption in the InnoDB tablespace

磁盘空间满和断电都可能导致mysql无法启动&#xff0c;报错如下&#xff1a; InnoDB: corruption in the InnoDB tablespace. Please refer to InnoDB: http://dev.mysql.com/doc/refman/8.0/en/forcing-innodb-recovery.html InnoDB: about forcing recovery. 20241031 10:54:…

Java网络通信

前言 1. 基本知识 通俗一点就是CS就是要下载应用来访问的&#xff0c;BS是在浏览器上面访问的&#xff0c;不用下载 1.1 IP IP地址就是你电脑的主机号&#xff0c;一台设备都有唯一的IP&#xff0c;端口就是程序的唯一标识 这上面就是我们的ip地址了&#xff0c;有IPv4和…

iptables面试题

1、详述iptales工作流程以及规则过滤顺序&#xff1f; iptables过滤的规则顺序是由上至下&#xff0c;若出现相同的匹配规则则遵循由上至下的顺序 2、iptables的几个表以及每个表对应链的作用&#xff1f; Iptables有四表五链 Filter表 : Filter表是iptables中使用的默认表…

【论文笔记】Attention Prompting on Image for Large Vision-Language Models

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: Attention Prompting on I…

【spring】Cookie和Session的设置与获取(@CookieValue()和@SessionAttribute())

&#x1f490;个人主页&#xff1a;初晴~ &#x1f4da;相关专栏&#xff1a;程序猿的春天 获取Cookie 使用 Servlet 获取Cookie&#xff1a; Spring MVC 是基于 Servlet API 构建的原始 Web 框架&#xff0c;也是在 Servlet 的基础上实现的 RestController RequestMapping…

Android启动流程_Init阶段

前言 本文将会介绍 Android 启动流程&#xff0c;将基于 Android 10 代码逻辑介绍原生启动过程。 bootloader 上电 -> 加载 recovery 镜像或者 boot 镜像 -> linux kernel 启动 -> 加载 init 进程 -> 加载 zygote 进程 -> systemserver 进程 -> 系统启动 …

MySQL数据库之存储过程的创建与应用

存储过程 procedure 一.存储过程 作用&#xff1a;将经常使用的功能写成存储过程&#xff0c;方便后续重复使用。 二.创建存储过程 三.调用存储过程 call在计算机中是调用的意思 案例1&#xff1a;查看MySQL用户数 如上图所示&#xff0c;这是查看MySQL数据库中的user个数…

7.使用Redis进行秒杀优化

目录 1. 优化思路 总结之前实现的秒杀过程 下单流程 2. 使用Redis完成秒杀资格判断和库存 0. Redis中数据类型的选用 1.将优惠券信息保存到Redis中 2.基于Lua脚本&#xff0c;判断秒杀库存、一人一单&#xff0c;决定用户是否抢购成功 3. 开启新协程&#xff0c;处理数…

终于把DETR搞懂了!Detection Transformer架构详解及使用方法说明

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

Calling short variants with GATK4

计算生物学实验5: Calling short variants with GATK4 1. 实验目的 本实验目的是利用 GATK4 工具准确高效地检测出基因组中的短变异。通过该工具对样本基因组进行分析&#xff0c;旨在发现单核苷酸变异&#xff08;SNV&#xff09;和小的插入缺失&#xff08;Indel&#xff0…

S32K324 DTCM/DTCM Backdoor使用及测试

文章目录 前言S32K324的Memory mapDTCM的原理DTCM的使用DTCM/DTCM backdoor测试总结 前言 S32K324的Ram在选型手册上给的是512K&#xff0c;但实际上sram只有320k,项目中对ram的需求更大&#xff0c;所以需要拓展一下ram的使用。本文分析DTCM的使用方案及测试结果 S32K324的M…