【C++】bitset位图的简单模拟实现及常见面试题
文章目录
- 前言
- 一、 bitset模拟实现
- 二、 常见面试题
- 1.给你一百亿个整数,找到只出现一次的数字
- 2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
前言
- 快速查找某个数据是否在一个集合中
- 排序 + 去重
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。比如:

一、 bitset模拟实现
namespace bit {template<size_t N>//非类型模板参数//N为我们要开的多少个比特位class bitset {public:bitset(){//我们用int类型来模拟,一个int一共32个比特_a.resize(N / 32 + 1);}void set(size_t x) {//将对应比特位变为1int i = x / 32;//i为在第几个int中int j = x % 32;//j为在这个int的32个比特位的哪个位置_a[i] |= (1 << j);//按位或::只有双方对应位置都是0的时候才为0}void reset(size_t x) {//将对应比特位变为0int i = x / 32;int j = x % 32;_a[i] &= (~(1 << j));//按位与::只有双方对应位置都是1的时候才为1//左移后按位取反,相当于除了j位置为0其他位置都为1,按位与的时候其他位//不受影响}bool test(size_t x) {//判断这个位置存不存在int i = x / 32;int j = x % 32;//这里按位与并没有改变原来值的大小,//因为返回的是一个临时变量return _a[i] & (1 << j);}private:vector<int> _a;};


二、 常见面试题
1.给你一百亿个整数,找到只出现一次的数字
我们可以使用两个位图,两个位图所组成的两位的二进制,用来表示出现次数,我们只需对两个表中的存在情况进行讨论就能确定他们出现此处,找出所有标记位01的数
00出现0次,01出现1次,10出现两次,11出现两次以上
template<size_t N>class twobitset{public:void set(size_t x){//00出现0次,01出现1次,10出现两次,11出现两次以上// 00 -> 01if (!_bs1.test(x) && !_bs2.test(x)){_bs2.set(x);} // 01 -> 10else if (!_bs1.test(x) && _bs2.test(x)){_bs1.set(x);_bs2.reset(x);}// 本身10代表出现2次及以上,就不变了}bool is_once(size_t x){return !_bs1.test(x) && _bs2.test(x);}private:bitset<N> _bs1;bitset<N> _bs2;};
2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
两个文件分别放到位图里面,然后判断两个位图的相同位置值是否相同。
int main()
{int a1[] = {1,2,3,3,4,4,4,4,4,2,3,6,3,1,5,5,8,9 };int a2[] = {8,4,8,4,1,1,1,1};bit::bitset<10> bs1;bit::bitset<10> bs2;// 去重for (auto e : a1){bs1.set(e);}// 去重for (auto e : a2){bs2.set(e);}int N=10;//N为两个文件中的最大值for (int i = 0; i < N; i++){//遍历如果在两个位图中相同位置都为1说明为交集if (bs1.test(i) && bs2.test(i)){cout << i << " ";}}cout << endl;
}
相关文章:
【C++】bitset位图的简单模拟实现及常见面试题
文章目录 前言一、 bitset模拟实现二、 常见面试题1.给你一百亿个整数,找到只出现一次的数字2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集? 前言 快速查找某个数据是否在一个集合中排序 去重…...
十六、MySql的MVCC机制CONNECT(收官!)
文章目录 一、数据库并发的场景有三种:二、读-写(一)3个记录隐藏列字段(二)undo 日志(三)模拟 MVCC(四)一些思考(五)Read View 一、数据库并发的场…...
194、SpringBoot -- 下载和安装 Erlang 、 RabbitMQ
本节要点: 一些命令: 小黑窗输入: rabbitmq-plugins enable rabbitmq_management 启动控制台插件 rabbitmq-server 启动rabbitMQ服务器 管理员启动小黑窗: rabbitmq-service install 添加rabbitMQ为本地服务 启动浏览器访问 ht…...
Linux0.11——第二回 从0x7c00到0x90000
上一讲,讲了CPU执行操作系统的最开始的两行代码: mov ax, 0x07c0 mov ds, ax这两行代码将数据段寄存器 ds 的值变成了 0x07c0,方便之后访问内存时,利用这个段基址进行寻址。 接下来的代码: mov ax,0x9000 mov es,ax…...
封装了一个中间放大效果的iOS轮播视图
效果图 计算逻辑 设定在中间展示的size,即正常size,然后设置水平和竖直方向上的margin, 在view的origin和scrollView的contentoffset相等的时候,即 视图处在正中间的时候,最大,然后通过计算其他视图的origin和scrollV…...
趣解设计模式之《小王的糖果售卖机》
〇、小故事 小王最近一直在寻找商机,他发现商场儿童乐园或者中小学校周围,会有很多小朋友喜欢吃糖果,那么他想设计一款糖果售卖机,让后将这些糖果售卖机布置到商场和学校旁边,这样就能获得源源不断的收益了。 想到这里…...
Redis 哨兵模式模式搭建教程
一、介绍 本文实战搭建一主两从三哨兵,通过使用哨兵模式,可以有效避免某台服务器的 Redis 挂掉出现的不可用问题,保障系统的高可用。 本文通过虚拟机搭建的三台 Centos7 服务器进行测试,使用的 Redis 版本为 6.25。 二、准备环…...
41. Linux系统配置FTP服务器并在QT中使用QFtp实现文件上传
1. 说明 这篇博客主要记录一些在Linux系统中搭建FTP服务器时踩过的一些坑,以及在使用QFtp上传文件时需要注意的问题。 2. FTP环境搭建 在linux系统中,需要安装vsftpd,可以在终端中输入下面的命令进行安装: sudo apt-get install vsftpd使用上述命令安装后,系统中会有一…...
【新版】系统架构设计师 - 案例分析 - 架构设计<架构风格和质量属性>
个人总结,仅供参考,欢迎加好友一起讨论 文章目录 架构 - 案例分析 - 架构设计<架构风格和质量属性>例题1例题2例题3例题4例题5例题6 架构 - 案例分析 - 架构设计<架构风格和质量属性> 例题1 某软件公司为…...
C++ - 红黑树 介绍 和 实现
前言 前面 学习了 AVL树,AVL树虽然在 查找方面始终拥有 O(log N )的极高效率,但是,AVL 树在插入 ,删除等等 修改的操作当中非常的麻烦,尤其是 删除操作,在实现当中细节非常多,在实现上非常难掌控…...
【蓝桥杯选拔赛真题62】Scratch判断小球 少儿编程scratch图形化编程 蓝桥杯选拔赛真题解析
目录 scratch判断小球 一、题目要求 编程实现 二、案例分析 1、角色分析...
Spring面试题15:Spring支持几种bean的作用域?singleton、prototype、request的区别是什么?
该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Spring支持几种bean的作用域? Spring支持以下几种Bean的作用域: Singleton(单例):这是Spring默认的作用域。使用@Scope(“singleton”)注解或…...
Spring Boot中Tomcat服务器参数解析及高并发控制
Spring Boot中Tomcat服务器参数解析及高并发控制 Spring Boot 集成了多种服务器,默认使用了Tomcat 服务器。在高并发情况下,合理地配置 Tomcat 服务器参数对于控制请求量和提高系统的稳定性至关重要。本文将解释 Spring Boot 中涉及 Tomcat 服务器的一些…...
Python 运行代码
一、Python运行代码 可以使用三种方式运行Python,如下: 1、交互式 通过命令行窗口进入 Python 并开始在交互式解释器中开始编写 Python 代码 2、命令行脚本 可以把代码放到文件中,通过python 文件名.py命令执行代码,如下ÿ…...
【ROS入门】使用 ROS 话题(Topic)机制实现消息发布与订阅及launch文件的封装
文章结构 任务要求话题模型实现步骤创建工作空间并初始化创建功能包并添加依赖创建发布者代码(C)创建订阅方代码(C)配置CMakeLists.txt执行启动roscore编译启动发布和订阅节点 launch封装执行 任务要求 使用 ROS 话题(Topic)机制…...
【企业级SpringBoot单体项目模板 】——Mybatis-plus自动代码生成
😜作 者:是江迪呀✒️本文关键词:SpringBoot项目模版、企业级、模版☀️每日 一言:我们之所以这样认为,是因为他们这样说。他们之所以那样说,是因为他们想让我们那样认为。所以实践才是检验真理…...
怒刷LeetCode的第14天(Java版)
目录 第一题 题目来源 题目内容 解决方法 方法一:动态规划 方法二:栈 方法三:双指针 第二题 题目来源 题目内容 解决方法 方法一:二分查找 方法二:线性扫描 方法三:递归 第三题 题目来源 …...
c语言 static
1、静态局部变量在程序加载时初始化,静态局部变量的初始值写入到了data段: 如下代码test_symbol.c int f() {static int x 0;return x; }int g() {static int x 9;return x; }使用命令gcc -c test_symbol.c -o test_symbol 编译 使用命令 readelf -a …...
java基础3
输入一个班学生的成绩,先显示所有及格的成绩,再显示所有不及格的成绩,最后显示及格人数和不及格人数 import java.util.Scanner; public class Hello{public static void main(String [] args) {int SIZE5;double grade[] new double[SIZE]…...
LeetCode 1194.锦标赛优胜者
数据准备 Create table If Not Exists Players (player_id int, group_id int); Create table If Not Exists Matches (match_id int, first_player int, second_player int, first_score int, second_score int); Truncate table Players; insert into Players (player_id, g…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...
小智AI+MCP
什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析:AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github:https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...
内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献
Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...
