当前位置: 首页 > news >正文

【C++】bitset位图的简单模拟实现及常见面试题

文章目录

  • 前言
  • 一、 bitset模拟实现
  • 二、 常见面试题
    • 1.给你一百亿个整数,找到只出现一次的数字
    • 2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?


前言

  1. 快速查找某个数据是否在一个集合中
  2. 排序 + 去重
  3. 求两个集合的交集、并集等
  4. 操作系统中磁盘块标记

数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为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.给你一百亿个整数&#xff0c;找到只出现一次的数字2. 给两个文件&#xff0c;分别有100亿个整数&#xff0c;我们只有1G内存&#xff0c;如何找到两个文件交集&#xff1f; 前言 快速查找某个数据是否在一个集合中排序 去重…...

十六、MySql的MVCC机制CONNECT(收官!)

文章目录 一、数据库并发的场景有三种&#xff1a;二、读-写&#xff08;一&#xff09;3个记录隐藏列字段&#xff08;二&#xff09;undo 日志&#xff08;三&#xff09;模拟 MVCC&#xff08;四&#xff09;一些思考&#xff08;五&#xff09;Read View 一、数据库并发的场…...

194、SpringBoot -- 下载和安装 Erlang 、 RabbitMQ

本节要点&#xff1a; 一些命令&#xff1a; 小黑窗输入&#xff1a; rabbitmq-plugins enable rabbitmq_management 启动控制台插件 rabbitmq-server 启动rabbitMQ服务器 管理员启动小黑窗&#xff1a; rabbitmq-service install 添加rabbitMQ为本地服务 启动浏览器访问 ht…...

Linux0.11——第二回 从0x7c00到0x90000

上一讲&#xff0c;讲了CPU执行操作系统的最开始的两行代码&#xff1a; mov ax, 0x07c0 mov ds, ax这两行代码将数据段寄存器 ds 的值变成了 0x07c0&#xff0c;方便之后访问内存时&#xff0c;利用这个段基址进行寻址。 接下来的代码&#xff1a; mov ax,0x9000 mov es,ax…...

封装了一个中间放大效果的iOS轮播视图

效果图 计算逻辑 设定在中间展示的size&#xff0c;即正常size&#xff0c;然后设置水平和竖直方向上的margin, 在view的origin和scrollView的contentoffset相等的时候&#xff0c;即 视图处在正中间的时候&#xff0c;最大&#xff0c;然后通过计算其他视图的origin和scrollV…...

趣解设计模式之《小王的糖果售卖机》

〇、小故事 小王最近一直在寻找商机&#xff0c;他发现商场儿童乐园或者中小学校周围&#xff0c;会有很多小朋友喜欢吃糖果&#xff0c;那么他想设计一款糖果售卖机&#xff0c;让后将这些糖果售卖机布置到商场和学校旁边&#xff0c;这样就能获得源源不断的收益了。 想到这里…...

Redis 哨兵模式模式搭建教程

一、介绍 本文实战搭建一主两从三哨兵&#xff0c;通过使用哨兵模式&#xff0c;可以有效避免某台服务器的 Redis 挂掉出现的不可用问题&#xff0c;保障系统的高可用。 本文通过虚拟机搭建的三台 Centos7 服务器进行测试&#xff0c;使用的 Redis 版本为 6.25。 二、准备环…...

41. Linux系统配置FTP服务器并在QT中使用QFtp实现文件上传

1. 说明 这篇博客主要记录一些在Linux系统中搭建FTP服务器时踩过的一些坑,以及在使用QFtp上传文件时需要注意的问题。 2. FTP环境搭建 在linux系统中,需要安装vsftpd,可以在终端中输入下面的命令进行安装: sudo apt-get install vsftpd使用上述命令安装后,系统中会有一…...

【新版】系统架构设计师 - 案例分析 - 架构设计<架构风格和质量属性>

个人总结&#xff0c;仅供参考&#xff0c;欢迎加好友一起讨论 文章目录 架构 - 案例分析 - 架构设计&#xff1c;架构风格和质量属性&#xff1e;例题1例题2例题3例题4例题5例题6 架构 - 案例分析 - 架构设计&#xff1c;架构风格和质量属性&#xff1e; 例题1 某软件公司为…...

C++ - 红黑树 介绍 和 实现

前言 前面 学习了 AVL树&#xff0c;AVL树虽然在 查找方面始终拥有 O(log N &#xff09;的极高效率&#xff0c;但是&#xff0c;AVL 树在插入 ,删除等等 修改的操作当中非常的麻烦&#xff0c;尤其是 删除操作&#xff0c;在实现当中细节非常多&#xff0c;在实现上非常难掌控…...

【蓝桥杯选拔赛真题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 集成了多种服务器&#xff0c;默认使用了Tomcat 服务器。在高并发情况下&#xff0c;合理地配置 Tomcat 服务器参数对于控制请求量和提高系统的稳定性至关重要。本文将解释 Spring Boot 中涉及 Tomcat 服务器的一些…...

Python 运行代码

一、Python运行代码 可以使用三种方式运行Python&#xff0c;如下&#xff1a; 1、交互式 通过命令行窗口进入 Python 并开始在交互式解释器中开始编写 Python 代码 2、命令行脚本 可以把代码放到文件中&#xff0c;通过python 文件名.py命令执行代码&#xff0c;如下&#xff…...

【ROS入门】使用 ROS 话题(Topic)机制实现消息发布与订阅及launch文件的封装

文章结构 任务要求话题模型实现步骤创建工作空间并初始化创建功能包并添加依赖创建发布者代码&#xff08;C&#xff09;创建订阅方代码&#xff08;C&#xff09;配置CMakeLists.txt执行启动roscore编译启动发布和订阅节点 launch封装执行 任务要求 使用 ROS 话题(Topic)机制…...

【企业级SpringBoot单体项目模板 】——Mybatis-plus自动代码生成

&#x1f61c;作 者&#xff1a;是江迪呀✒️本文关键词&#xff1a;SpringBoot项目模版、企业级、模版☀️每日 一言&#xff1a;我们之所以这样认为&#xff0c;是因为他们这样说。他们之所以那样说&#xff0c;是因为他们想让我们那样认为。所以实践才是检验真理…...

怒刷LeetCode的第14天(Java版)

目录 第一题 题目来源 题目内容 解决方法 方法一&#xff1a;动态规划 方法二&#xff1a;栈 方法三&#xff1a;双指针 第二题 题目来源 题目内容 解决方法 方法一&#xff1a;二分查找 方法二&#xff1a;线性扫描 方法三&#xff1a;递归 第三题 题目来源 …...

c语言 static

1、静态局部变量在程序加载时初始化&#xff0c;静态局部变量的初始值写入到了data段&#xff1a; 如下代码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

输入一个班学生的成绩&#xff0c;先显示所有及格的成绩&#xff0c;再显示所有不及格的成绩&#xff0c;最后显示及格人数和不及格人数 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…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...