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

devtools/2024/11/15 0:54:03/

前言:

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

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

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

一、题目:

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

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

例如:

有数组的元素是: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.ppmy.cn/devtools/96374.html

相关文章

【SpringBoot】SpringBoot框架的整体环境搭建和使用(整合Mybatis,Druid,Junit4,PageHelper,logback等)

目录 1.介绍 1.1 配置文件 1.2 目录结构 2.基于SpringBoot的SpringMVC 4.整合Mybatis 5.整合Druid连接池 6.整合Junit4 7.整合Logback 8.整合PageHelper 9.SpringBoot整合Thymeleaf ​编辑 【附录】springboot的pom.xml 1.介绍 Spring框架的优点是方便解耦、简化开…

Spring IoCDI(中)--IoC的进步

通过上文的讲解和学习, 我们已经知道了Spring IoC 和DI的基本操作, 接下来我们来系统的学习Spring IoC和DI 的操作. 前⾯我们提到IoC控制反转&#xff0c;就是将对象的控制权交给Spring的IOC容器&#xff0c;由IOC容器创建及管理对 象&#xff0c;也就是bean的存储。 1. Bean的…

【python小脚本】摄像头rtsp流转hls m3u8 格式web端播放

写在前面 工作需要&#xff0c;简单整理实际上这种方式延迟太高了&#xff0c;后来前端直接接的海康的本地解码插件&#xff0c;走的 websockt博文内容为 摄像头 rtsp 实时流转 hls m3u8 的一个 Python 脚本理解不足小伙伴帮忙指正 &#x1f603;,生活加油 99%的焦虑都来自于虚…

如果从mysql导出百万数据级的excel

如果从mysql导出百万数据级的excel&#xff0c;可能遇到的问题&#xff1f; 同步导数据&#xff0c;接口很容易超时。 如果把所有数据一次性装载到内存&#xff0c;很容易引起OOM。 数据量太大sql语句慢。 如果走异步&#xff0c;如何通知用户导出结果 如果excel文件太大&#…

XSS--DOM破坏案例与靶场

靶场连接https://xss.pwnfunction.com/challenges/ 目录 Ma SPaghet! Jeff Ugandan Knuckles Ricardo Milos Ah Thats Hawt Ligma Mafia Ok,Boomer Ma SPaghet! <!-- Challenge --> <h2 id"spaghet"></h2> <script>spaghet.innerHT…

wpf IDataErrorInfo 验证

我可以给你一个简单的例子来说明如何在WPF中使用IDataErrorInfo接口来显示错误信息&#xff0c;并通过样式&#xff08;Style&#xff09;和触发器&#xff08;Trigger&#xff09;来在UI上反映这些错误。 首先&#xff0c;你需要一个实现了IDataErrorInfo接口的模型类。这个接…

【人工智能】TensorFlow lite介绍、应用场景以及项目实践:使用TensorFlow Lite进行数字分类

一、TensorFlow Lite 介绍 TensorFlow Lite&#xff08;简称TFLite&#xff09;是谷歌开发的一种轻量级的深度学习框架&#xff0c;专为移动设备和嵌入式设备设计。它是TensorFlow的移动和嵌入式设备版本&#xff0c;旨在帮助开发者在资源受限的设备上执行机器学习模型。Tenso…

通过相机来获取图片

文章目录 1. 概念介绍2. 方法与细节2.1 实现方法2.2 具体细节 3. 示例代码4. 内容总结 我们在上一章回中介绍了"如何混合选择多个图片和视频文件"相关的内容&#xff0c;本章回中将介绍如何通过相机获取图片文件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. …