C:每日一练:单身狗(2.0版本)

前言:

今天在刷题的时候突然看到一道题疑似一位故题。仔细一看,欸!这不是就是单身狗的升级版吗?我想那必须再安排一篇,不过由于本篇文章与上一篇单身狗文章所涉及的知识点基本相同,所以还请大家见谅!

我写的开心,大家也看个乐呵!不过还请单身的人不要介意,单纯觉得比较有意思,无意冒犯!毕竟连小编自己都是单身狗。

后续小编也会尽快更新完指针相关知识点!

一、题目:

在一场专为情侣们策划的盛宴中,竟然有两名单身者悄然混入。宴会的主人感到十分不悦,并寻求你的帮助,希望你能运用你敏锐的洞察力,协助她识破并找出这两名不合规矩的单身者。

(无意冒犯,只是提供一个题目的背景)

例如:

有数组的元素是:1,2,3,4,5,6,1,2,3,4,5,7

只有6和7只出现1次,要找出6和7.

二、代码展示(无注释的)

如果有想先自己思考的可以先看一看这个代码,后面也会有解析

#include <stdio.h>
int find(int num) {int index = 0;while ((num & 1) == 0 && index < 32) {num >>= 1;index++;}return index;
}
void single(int arr[], int sz, int* n1, int* n2) {int Re = 0;for (int i = 0; i < sz; i++) {Re ^= arr[i];}int index = find(Re);*n1 = *n2 = 0;for (int i = 0; i < sz; i++) {if (((arr[i] >> index) & 1) == 1) *n1 ^= arr[i];    else *n2 ^= arr[i];}
int main() {int arr[] = {1,2,3,4,5,6,1,2,3,4,5,7};int n1, n2;int sz = sizeof(arr) / sizeof(arr[0]);single(arr, sz, &n1, &n2);printf("两只单身狗分别是:%d 和 %d\n", n1, n2);return 0;
}

三、题解思路:

1.关于算法,我们依然使用的是异或运算,因为异或运算相同为0,所以将数组中所有的数字进行异或操作,最终得到的结果就是那两个只出现一次的数字的异或值。

例如:

举个例子: int arr[ ] = {1,1,2}

初始re = 0;

re = re ^ 1 = 1;此时re = 1;

re = re ^ 1 = 1 ^ 1 = 0;此时re = 0;

re = re ^ 2 = 0 ^ 2 = 2;此时re = 2;所以只出现一次的数字是2

2.找到这个异或结果中为 1 的某一位。根据异或运算不同为1,这一位为 1 说明在这一位上,那两个只出现一次的数字是不同的。

例如:数组{1,1,2}
异或运算:1^1^2 = 2;
0010   2的二进制
 异或的结果是0010,从右向左找1的位置
0000   0的二进制
0010   2的二进制
0000^0010 = 0010 (异或运算相同为0,不同为1)
我们可以发现0在这一位上的数字是0,2在这一位上的数字是2,说明结果为1的这一位,两个只出现一次的数字是不同的。

3.根据这一位将数组中的数字分为两组。一组是这一位为 1 的数字,另一组是这一位为 0 的数字。

再对这两组数字分别进行异或操作,就可以得到那两个只出现一次的数字。

例如,数组为{1,2,3,1,2,4}

第一步,将所有数字异或:1 ^ 2 ^ 3 ^ 1 ^ 2 ^ 4=6 (二进制为0110 )

第二步,找到异或结果中为 1 的一位,从右往左数第二位为 1 

第三步,根据这一位将数字分组:

  • 这一位为 1 的数字:{3,4}
  • 这一位为 0 的数字:{1,2,1,2}

四、函数介绍

1.main函数

int main() 
{int arr[] = {1,2,3,4,5,6,1,2,3,4,5,7};int n1, n2;int sz = sizeof(arr) / sizeof(arr[0]);single(arr, sz, &n1, &n2);printf("两只单身狗分别是:%d 和 %d\n", n1, n2);return 0;
}
  •  数组的输入:int arr[] = {1,2,3,4,5,6,1,2,3,4,5,7};
  • 数组元素个数计算: int sz = sizeof(arr) / sizeof(arr[0]);
  • 调用函数: single(arr, sz, &n1, &n2);

2.single函数

void single(int arr[], int sz, int* n1, int* n2) {int Re = 0;for (int i = 0; i < sz; i++) {Re ^= arr[i];}int index = find(Re);*n1 = *n2 = 0;for (int i = 0; i < sz; i++) {if (((arr[i] >> index) & 1) == 1) {*n1 ^= arr[i];}else {*n2 ^= arr[i];}}
}

single函数作用:找出数组中两个只出现一次的数字

第一个for循环实现数组中所有元素的异或运算

第二个for循环用于根据索引值,将数组分为两组并分别进行异或运算

 int index = find(Re);将索引值传给find函数

3.find函数

int find(int num) {int index = 0;while ((num & 1) == 0 && index < 32) {num >>= 1;index++;}return index;
}

 find函数用于找到一个数的二进制表示中从右往左第一个为 1 的位的索引

五:代码展示(含注释)

#include <stdio.h>
int find(int num)int index = 0;while ((num & 1) == 0 && index < 32)  // 当前二进制位为 0 并且索引小于 32{num >>= 1;//实现二进制中每位检查index++;}return index;// 返回第一个结果为 1 的位的索引
}
void single(int arr[], int sz, int* n1, int* n2) int Re = 0;// 对数组中所有数字进行异或操作,得到两个只出现一次数字的异或结果for (int i = 0; i < sz; i++) {Re ^= arr[i];}int index = find(Re);// 找到上述异或结果中第一个为 1 的位的索引*n1 = *n2 = 0;// 根据找到的索引位,将数组数字分为两组并分别异或for (int i = 0; i < sz; i++) {if (((arr[i] >> index) & 1) == 1) // 判断当前数字在指定索引位是否为 1*n1 ^= arr[i];   else *n2 ^= arr[i];  }
}
int main() 
{int arr[] = { 1, 2, 3, 2, 1, 4 };int n1, n2;int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素single(arr, sz, &n1, &n2);//函数调用printf("两只单身狗分别是:%d 和 %d\n", n1, n2);return 0;
}

 

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

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

相关文章

政企单位如何选择适合规模的即时通讯软件?

政企单位在不同规模的组织结构中都面临着沟通和协作的挑战。为了提高工作效率和团队协作能力&#xff0c;选择适合规模的即时通讯软件至关重要。本文将为政企单位在选择适合规模的即时通讯软件时提供一些关键要素和指导&#xff0c;同时重点介绍WorkPlus作为一个可以迎合政企单…

谷歌的高级指令有哪些

今天会分享一些组合用法&#xff0c;这样就能节省许多时间可以放在跟进客户上面&#xff08;本文只介绍谷歌的搜索指令&#xff0c;并无推广&#xff09; part one 谷歌常用的搜索引擎指令&#xff1a; 1、Inurl&#xff0c;在网址中 2、Intext&#xff0c;在网页内容中 3、…

tcpdump入门——抓取三次握手数据包

1. 使用docker启动一个tcp应用 参考&#xff1a;https://blog.csdn.net/LONG_Yi_1994/article/details/141175526 2. 获取容器id docker ps |grep gochat 3. 获取容器的 PID 首先&#xff0c;你需要获得容器的进程 ID&#xff08;PID&#xff09;。可以使用 docker inspect…

遥感之常用各种指数总结大全

目前在遥感领域基本各种研究领域都会用到各种各样的指数&#xff0c;如水体指数&#xff0c;植被指数&#xff0c;农业长势指数&#xff0c;盐分指数&#xff0c;云指数&#xff0c;阴影指数&#xff0c;建筑物指数&#xff0c;水质指数&#xff0c;干旱指数等等众多。 本文对上…

【Web】巅峰极客2024 部分题解

目录 EncirclingGame GoldenHornKing php_online admin_Test EncirclingGame 玩赢游戏就行 GoldenHornKing 利用点在传入的app 可以打python内存马 /calc?calc_reqconfig.__init__.__globals__[__builtins__][exec](app.add_api_route("/flag",lambda:__i…

STM32通过I2C硬件读写MPU6050

目录 STM32通过I2C硬件读写MPU6050 1. STM32的I2C外设简介 2. STM32的I2C基本框图 3. STIM32硬件I2C主机发送流程 10位地址与7位地址的区别 7位主机发送的时序流程 7位主机接收的时序流程 4. STM32硬件与软件的波形对比 5. STM32配置硬件I2C外设流程 6. STM32的I2C.h…

Java Web|day6.MyBatis-Plus

MyBatisPlus 定义 mybatis-plus是一款Mybatis增强工具&#xff0c;用于简化开发&#xff0c;提高效率。 核心功能 注解 TableName 注解在类上&#xff0c;指定类和数据库表的映射关系。实体类的类名&#xff08;转成小写后&#xff09;和数据库表名相同时&#xff0c;可以不…

网络协议九 应用层 HTTPS

一 什么是 HTTPS 前面我们看到HTTP 有很多安全问题&#xff0c;因此引出了 对称加密 和 不对称加密。 那么这个对称加密和不对称加密&#xff0c;我们怎么和HTTP结合起来呢&#xff1f;HTTPS 就是弄好的 HTTP 和 加密结合的协议。 通过HTTP加密后的数据&#xff0c;整个传输过…

Fly Catcher:通过监测恶意信号来检测飞机欺骗

Fly Catcher 的开发者 Angelina Tsuboi 是一名飞行员、网络安全研究员和发明家。 她决定着手一个将这三个不同兴趣结合起来的项目&#xff0c;以解决航空雷达系统的一个重大问题。 ADS-B 系统最初用于基本的飞机定位和跟踪&#xff0c;Tsuboi 对该系统的网络安全方面进行了深…

Java语言程序设计——篇十四(1)

&#x1f33f;&#x1f33f;&#x1f33f;跟随博主脚步&#xff0c;从这里开始→博主主页&#x1f33f;&#x1f33f;&#x1f33f; 欢迎大家&#xff1a;这里是我的学习笔记、总结知识的地方&#xff0c;喜欢的话请三连&#xff0c;有问题可以私信&#x1f333;&#x1f333;&…

日撸Java三百行(day25:栈实现二叉树深度遍历之中序遍历)

目录 一、栈实现二叉树遍历的可行性 二、由递归推出栈如何实现中序遍历 1.左子树入栈 2.根结点出栈 3.右子树入栈 4.实例说明 三、代码实现 总结 一、栈实现二叉树遍历的可行性 在日撸Java三百行&#xff08;day16&#xff1a;递归&#xff09;中&#xff0c;我们讲过…

【C++11】入门基础

&#x1f525; 个人主页&#xff1a;大耳朵土土垚 &#x1f525; 所属专栏&#xff1a;C从入门至进阶 这里将会不定期更新有关C/C的内容&#xff0c;欢迎大家点赞&#xff0c;收藏&#xff0c;评论&#x1f973;&#x1f973;&#x1f389;&#x1f389;&#x1f389; 文章目录…

minikube 实践练习4 - 滚动更新

1. 应用版本更新 #查看image kubectl describe pods#设置应用的image为新版本 v1 -> v2 kubectl set image deployments/kubernetes-bootcamp kubernetes-bootcampdocker.io/jocatalin/kubernetes-bootcamp:v2#验证更新结果 export NODE_PORT"$(kubectl get services/…

糟糕界面集锦-控件篇11

GUI 的一个设计基本准则是&#xff1a;如果控件被禁用&#xff0c;那么就应该表现出来。这样不管是菜单项、命令按钮、列表框、下拉列表&#xff0c;我们只要一瞥就可以知道是否可用。奇怪的是为什么微软在按钮被禁用时不把它显示出来&#xff1f;这幅图片来自Office95 系列中的…

Redis操作--RedisTemplate(二)StringRedisTemplate

一、介绍 1、简介 由于存储在 Redis 中的 key 和 value 通常是很常见的 String 类型&#xff0c;Redis模块提供了 RedisConnection 和 RedisTemplate 的扩展&#xff0c;分是 StringRedisConnection 和 StringRedisTemplate&#xff0c;作为字符串操作的解决方案。 通过源码…

【区块链+金融服务】第一创业证券开发银行间报价 Dapp | FISCO BCOS应用案例

在银行间市场现券交易的过程中&#xff0c;通过银保监会发牌的代理机构进行报价交易&#xff0c;已解决无代理阶段存在的许多问题。 但是由于业务需要&#xff0c;使用以前模式进行报价交易的仍占有一定比例。 针对这一现状&#xff0c;第一创业证券基于 FISCO BCOS 区块链底层…

多种办公功能的WORD VBA程序

word的VBA办公助手 源代码 Option Explicit 需要引用 excel 16.0 库 所有内容仅供个人学习使用&#xff0c;严禁传播。1-公共变量-表格属性------------------------------------------------------------------------- Dim Hg% hg:行高 Const K1 0.1 Dim Flg_bh As Boolean …

专业技能——Redis常用命令和持久化策略,内存回收策略+主从模式,哨兵模式,集群模式+缓存穿透击穿雪崩

Redis 是一个开源&#xff08;BSD许可&#xff09;的&#xff0c;内存中的数据结构存储系统&#xff0c;它可以用作数据库、缓存和消息中间件。 它支持多种类型的数据结构&#xff0c;如 字符串&#xff08;strings&#xff09;&#xff0c;散列&#xff08;hashes&#xff09;…

Kali Linux-设置系统24小时时间制

文章目录 设置系统24小时时间制 设置系统24小时时间制 在Kali Linux中&#xff0c;如果系统时间不是以24小时制显示&#xff0c;你可以通过修改系统时间格式配置文件来调整为24小时制。以下是具体的操作步骤&#xff1a; 1.编辑/etc/locale.conf配置文件。 vim /etc/locale.c…

微信云开发云存储 下载全部文件

一、安装 首先按照这个按照好依赖&#xff0c;打开cmd 安装 | 云开发 CloudBase - 一站式后端云服务 npm i -g cloudbase/cli 安装可能遇到的问题 ‘tcb‘ 不是内部或外部命令&#xff0c;也不是可运行的程序或批处理文件。-CSDN博客 二、登录 在cmd输入 tcb login 三、…