【每日易题】七夕限定——单身狗问题以及进阶问题位运算法的深入探讨

在这里插入图片描述

君兮_的个人主页

勤时当勉励 岁月不待人

C/C++ 游戏开发

Hello,米娜桑们,这里是君兮_,在写这篇博客的前一天是七夕,也是中国传统的“情人节”,不知道各位脱单了吗?碰巧最近刷题时遇到了经典的单身狗问题想带大家深入探讨一下,如果没脱单的话不如继续学习吧,记住,如果你喜欢的人不喜欢你,就变得足够优秀让她/他喜欢上你吧!!

单身狗问题的位运算解法

  • 一.什么是单身狗问题?
    • 找出一个单身狗
    • 找两条单身狗
  • 二.LeetCode单身狗进阶题
  • 总结

一.什么是单身狗问题?

  • 单身狗往往是这样的,在别人都成双成对的时候,只有你一个人孤独寂寞冷(比如博主)。而单身狗问题往往是找出一系列数中落单的那个
  • 对于这种问题往往可以暴力求解,但这样显得不够“优雅”,毕竟我们是“单身贵族”嘛!所以我们这里就介绍一种时间复杂度和空间复杂度都比较低的方法——位运算法

找出一个单身狗

  • 先举出最简单的例子
  • 问题如下
//找出单身狗-版本1
//有一个数组只有一个数组出现一次,其余数字都是成对出现的
//请找出只出现一次的数字
//1 2 3 4 5 1 2 3 4
  • 5就是这里的单身狗`
  • 那我们怎样用位运算法求解呢?
  • 我们知道对于异或来说相同为0,相异为1
  • 而异或又有这样的特性
//a^a=0;
//a^0=a;
  • 同时,异或也满足交换律和结合律,我们就能写出以下代码
int find_single_dog1(int arr[], int sz)
{int i = 0;int ret = 0;for (i = 0; i < sz; i++){ret ^= arr[i];}return ret;
}int main()
{int arr[] = { 1,2,3,4,5,1,2,3,4 };int sz = sizeof(arr) / sizeof(arr[0]);int dog = find_single_dog1(arr, sz);printf("%d\n", dog);return 0;
}
  • 什么意思呢?
  • 我们通过一个函数把所有的元素都给异或在一起,我们知道相同元素异或在一起为0,而一个元素异或0等于它本身,这样,就可以得到这个“单身狗”了。
    在这里插入图片描述

找两条单身狗

  • 从上面这题我们又可以深入一点,如果此时有两个人,但是他们是同性或者是异性但是不适合呢?也就是说有两条单身狗我们又该如何解决呢?
//找出单身狗版本2
//一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。、
//编写一个函数找出这两个只出现一次的数字。
//例如:
//有数组的元素是:1,2,3,4,5,1,2,3,4,6
//只有5和6只出现1次,要找出5和6.
  • 此时的难点在于,我们也可以通过把所有的元素都异或起来的方法找到这两条单身狗异或的值,但是我们怎样通过他俩异或的值找到相应的两个元素呢?
  • 我们可以这样考虑,我们如果能把两条单身狗分到不同的组里,再找出每一个组中的单身狗不就和第一种情况一样了吗?
  • 此时我们分组的条件就应该是两者一定存在差异的地方,哪里能凸显两者的差异呢?
  • 先把代码放这,让大家自己想一下,下面会有详细的解释的
void find_single_dog2(int arr[], int sz, int* pd1, int* pd2)
{//1. 所有数字异或在一起int ret = 0;//5 ^ 6int i = 0;for (i = 0; i < sz; i++){ret ^= arr[i];}//2. 计算ret的第几位是1,从而找出不同进行分组int pos = 0;for (i = 0; i < 32; i++){if (((ret >> i) & 1) == 1){pos = i;break;}}//分组//计算数组中元素的第pos为1的异或 for (i = 0; i < sz; i++){if (((arr[i] >> pos) & 1) == 1){*pd1 ^= arr[i];}}//计算数组中元素的第pos为0的异或*pd2 = ret ^ *pd1;
}int main()
{int arr[] = { 1,2,3,4,5,1,2,3,4,6 };int dog1 = 0;int dog2 = 0;int sz = sizeof(arr) / sizeof(arr[0]);find_single_dog2(arr, sz, &dog1, &dog2);printf("%d %d", dog1, dog2);return 0;
}
  • 看懂了吗?我来解释一下
  • 我们这个ret是把所有数异或进来的,此时只剩下了两条单身狗异或的值,异或相异为1
    也就是说找到ret二进制位是1的位置是不是就找到两条单身狗的不同之处啦?接下来通过分组就可找出单身狗
  • 注意:相同的元素相应的二进制位一定相同,也就是非单身狗们一定会被分到同一组中,从而保证这组中异或后有且仅有一条单身狗。
  • 这里还有一个能偷懒的地方,我们知道了两条单身狗异或的值,又找出了一条单身狗,通过异或法是不是就能快速找出另一条单身狗了?
a^b^a=b

在这里插入图片描述


二.LeetCode单身狗进阶题

  • 题目的链接放在这里
    错误集合
    在这里插入图片描述
  • 说到底,这个题就是单身狗题目的变种,我们同样是通过异或先找出重复出现的值和丢失的值,然后再对它们进行分组,依次找出即可
int* findErrorNums(int* nums, int numsSize, int* returnSize){int ret=0;int*returnNums=(int*)malloc(sizeof(int)*2);*returnSize=2;int i=0;//通过把数组中元素和1到n中元素异或起来,找到多余元素以及缺少的元素 (找两条单身狗)for(i=0;i<numsSize;i++){ret^=(i+1);ret^=nums[i];}int pos=0;i=0;//异或后不同位二进制为1,找1分组while(i<32){if(((ret>>i)&1)==1){pos=i;break;}i++;}//找出不同位后分组,只用找一个就行int nums1=0;int nums2=0;for(i=1;i<=numsSize;i++){if(((i>>pos)&1)==1){nums2^=i;}}for(i=0;i<numsSize;i++){if(((nums[i]>>pos)&1)==1){nums1^=nums[i];}}nums1^=nums2;//分组后的元素异或1-n找相同元素消掉//多的或者少的那个元素,不确定,我们需要判断一下int flag=0;//标记for(i=0;i<numsSize;i++){if(nums[i]==nums1){flag=1;returnNums[0]=nums1;break;}}if(flag==1)//数组中找到了这个元素,为重复元素,另一个为缺少元素returnNums[1]=ret^nums1;else{returnNums[1]=nums1;returnNums[0]=nums1^ret;}return returnNums;}
  • 除了注释中提到的,我这里还想提两点需要注意的地方
  • 与找单身狗不同,这里我们没有成对的元素,因此我们在分组前后都通过异或1到n的数找相同元素从而消掉,剩下的就是我们的单身狗了(有些人可能不理解重复的元素咋消掉啊,重复的元素在ret里就因为相同而消掉了,因此照样能找到这条单身狗哦)
  • 与普通题不同的地方在于,我们这里找出两条单身狗后还有辨别一下哪个是重复元素,哪个是缺少元素,在区分时我们通过flag做了一个标记,flag的值被修改也就是数组存在这个数,说明它就是重复元素啦,另一个自然是缺少元素,反之未被修改就与这种情况相反。

总结

  • 今天的内容到这里就结束了,有关位运算的地方如果不太清楚最后自己画画逻辑图就能弄懂,而有关题目博主建议如果看懂了的话不妨自己动手试试哦!!

  • 好了,如果你有任何疑问欢迎在评论区或者私信我提出,大家下次再见啦!

新人博主创作不易,如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力!!!

**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/102819.html

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

相关文章

设计模式概述

文章目录 设计模式概述创建型模式&#xff1a;结构型模式&#xff1a;行为型模式&#xff1a; 设计模式概述 设计模式是什么&#xff1f; 设计模式的一般定义为&#xff1a; 设计模式&#xff08;Design Pattern&#xff09;是一套反复使用、多人知晓的&#xff0c;经过分类…

java电子病历源码 电子病历编辑器源码 病历在线制作、管理和使用

电子病历在线制作、管理和使用的一体化电子病历解决方案&#xff0c;通过一体化的设计&#xff0c;提供对住院病人的电子病历书写、保存、修改、打印等功能。电子病历系统将临床医护需要的诊疗资料以符合临床思维的方法展示。建立以病人为中心&#xff0c;以临床诊疗信息为主线…

echart 图表添加数据分析功能,(右上控制选择)

echart 图表添加数据分析功能,可区域选择数据,右上按钮,控制echart行为 chart.on(globalcursortaken, onGlobalcursortaken); //绑定事件chart.off("brushSelected");//解绑事件处理函数chart.on(brushSelected, renderBrushed);getBarDev2(eIndex, eTimeArr, eSerie…

mmdetection基于 PyTorch 的目标检测开源工具箱 入门教程

安装环境 MMDetection 支持在 Linux&#xff0c;Windows 和 macOS 上运行。它需要 Python 3.7 以上&#xff0c;CUDA 9.2 以上和 PyTorch 1.8 及其以上。 1、安装依赖 步骤 0. 从官方网站下载并安装 Miniconda。 步骤 1. 创建并激活一个 conda 环境。 conda create --name…

Java 中使用 ES 高级客户端库 RestHighLevelClient 清理百万级规模历史数据

&#x1f389;工作中遇到这样一个需求场景&#xff1a;由于ES数据库中历史数据过多&#xff0c;占用太多的磁盘空间&#xff0c;需要定期地进行清理&#xff0c;在一定程度上可以释放磁盘空间&#xff0c;减轻磁盘空间压力。 &#x1f388;在经过调研之后发现&#xff0c;某服务…

SpringCloud学习笔记(四)_ZooKeeper注册中心

基于Spring Cloud实现服务的发布与调用。而在18年7月份&#xff0c;Eureka2.0宣布停更了&#xff0c;将不再进行开发&#xff0c;所以对于公司技术选型来说&#xff0c;可能会换用其他方案做注册中心。本章学习便是使用ZooKeeper作为注册中心。 本章使用的zookeeper版本是 3.6…

vue中form和table标签过长

form标签过长 效果&#xff1a; 代码&#xff1a; <el-form-item v-for"(item,index) in ticketEditTable1" :label"item.fieldNameCn" :propitem.fieldName :key"item.fieldNameCn" overflow"":rules"form[item.fieldName…

【Unity】Text文本组件的一些操作

Unity的Text组件的几种常见的操作方法 Text组件是Unity中用于在UI界面上显示文本的组件。它包含了一些常见的属性和方法&#xff0c;可以用来控制文本的内容、外观和交互。以下是一些常见的Text组件的操作&#xff1a; 设置文本内容&#xff1a;通过直接在Unity编辑器中的Text…

【方案】基于AI边缘计算的智慧工地解决方案

一、方案背景 在工程项目管理中&#xff0c;工程施工现场涉及面广&#xff0c;多种元素交叉&#xff0c;状况较为复杂&#xff0c;如人员出入、机械运行、物料运输等。特别是传统的现场管理模式依赖于管理人员的现场巡查。当发现安全风险时&#xff0c;需要提前报告&#xff0…

C语言基础之——操作符(上)

本篇文章&#xff0c;我们将展开讲解C语言中的各种常用操作符&#xff0c;帮助大家更容易的解决一些运算类问题。 这里提醒一下小伙伴们&#xff0c;本章知识会大量涉及到二进制序列&#xff0c;不清楚二进制序列的小伙伴&#xff0c;可以去阅读我的另一篇文章《数据在内存中的…

行业追踪,2023-08-23

自动复盘 2023-08-23 凡所有相&#xff0c;皆是虚妄。若见诸相非相&#xff0c;即见如来。 k 线图是最好的老师&#xff0c;每天持续发布板块的rps排名&#xff0c;追踪板块&#xff0c;板块来开仓&#xff0c;板块去清仓&#xff0c;丢弃自以为是的想法&#xff0c;板块去留让…

养号自动化,指纹浏览器和RPA机器人解除烦恼

在这个充满科技魔力的时代&#xff0c;社交媒体已经成为人们生活的一部分&#xff0c;而Facebook更是我们分享欢乐、联络亲友的重要平台。然而&#xff0c;随之而来的是一个棘手的问题&#xff1a;如何保持账号的活跃度&#xff0c;而又不被沉重的养号工作压垮&#xff1f;别担…

江西抚州新能源汽车3d扫描零部件逆向抄数测量改装-CASAIM中科广电

汽车改装除了在外观方面越来越受到消费者的青睐&#xff0c;在性能和实用性提升上面的需求也是日趋增多&#xff0c;能快速有效地对客户指定汽车零部件进行一个改装&#xff0c;是每一个汽车改装企业和工程师的追求&#xff0c;也是未来消费者个性化差异化的要求。下面CASAIM中…

【Modbus通信实验三】数据切片问题

在做两个串口相互通信的实验中&#xff0c;当发送频率快一点时偶尔会遇到以下情景&#xff0c;即一次send中把原数据拆成两份发送&#xff0c;就会导致CRC校验错误。下图中6字节数据拆成42是把SetRThreshold()阈值设为2&#xff0c;当设为1的情况下则会拆成51。 一开始以为是缓…

有趣的数学 数学建模入门二 一些理论基础

一、什么是数学建模? 现实世界中混乱的问题可以用数学来解决&#xff0c;从而产生一系列可能的解决方案来帮助指导决策。大多数人对数学建模的概念感到不舒服&#xff0c;因为它是如此开放。如此多的未知信息似乎令人望而却步。哪些因素最相关&#xff1f;但正是现实世界问题的…

【网络】DNS | ICMP | NAT | 代理服务器

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《网络》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 前面几篇文章虽然讲介绍了整个网络通信的协议栈&#xff0c;我们也知道了完整的网络通信过程&#xff…

【Java 高阶】一文精通 Spring MVC - 数据验证(七)

&#x1f449;博主介绍&#xff1a; 博主从事应用安全和大数据领域&#xff0c;有8年研发经验&#xff0c;5年面试官经验&#xff0c;Java技术专家&#xff0c;WEB架构师&#xff0c;阿里云专家博主&#xff0c;华为云云享专家&#xff0c;51CTO 专家博主 ⛪️ 个人社区&#x…

数字化技术无限延伸,VR全景点亮智慧生活

随着互联网的发展&#xff0c;我们无时无刻不再享受着互联网给我们带来的便利&#xff0c;数字化生活正在无限延伸&#xff0c;各行各业也开始积极布局智能生活。要说智慧生活哪个方面应用的比较多&#xff0c;那应该就是VR全景了&#xff0c;目前VR全景已经被各个行业广泛应用…

android studio安装教程

1、android studio 下载 下载网址&#xff1a;Download Android Studio & App Tools - Android Developers 2、开始安装 因为不需要每次连接手机进行调试&#xff0c;android studio给我们提供了模拟器调试环境。 一般选择自定义安装&#xff0c;这样可选sdk以及下载路径…

Idea Maven 构建,运行Java程序,二次开发Jmeter

Idea Maven 构建 1. maven下载2. Idea 配置3. 配置Maven镜像4. 在Maven项目pom.xml中添加依赖5. 创建jar包&#xff0c;更新pom&#xff0c;执行代码 1. maven下载 【官网】https://maven.apache.org/download.cgi 【其他版本】https://dlcdn.apache.org/maven/maven-3/ 2. …