OJ刷题:《剑指offer》之单身狗1、2 !(巧用位操作符,超详细讲解!)

2024-02-04 14:36

本文主要是介绍OJ刷题:《剑指offer》之单身狗1、2 !(巧用位操作符,超详细讲解!),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.单身狗1

1.1 题目描述

1.2排序寻找

1.3巧用位操作符

2.单身狗2

1.1 题目描述

1.2排序寻找

1.3巧用位操作符


                           不是每个人都能做自己想做的事,成为自己想成为的人。

                                                  克心守己,律己则安!

创作不易,宝子们!如果这篇文章对你们有帮助的话,别忘了给个免费的赞哟~ 

1.单身狗1

1.1 题目描述

在一个整型数组中,只有一个数字出现一次,其他数组都是成对出现的,请找出那个只出现一次的数字。

例如:

数组中有:1 2 3 4 5 1 2 3 4,只有5出现一次,其他数字都出现2次,出5

1.2排序寻找

1. 对于一个无序的数组,当我们将他们进行排序后,一切问题都会简单很多的~

冒泡排序的伪代码~

void sort(int arr[], int len)
{int i = 0;int j = 0;for (i = 0; i < len - 1; i++){int flag = 1;for (j = 0; j < len - 1; j++){if (arr[j] > arr[j + 1]){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 0;}}if (flag == 1)break;}//冒泡排序-》升序数组
}

2. 那我们要如何找到那个“单身狗”呢~

我们可以很容易的注意到相邻的2个元素是相同的,那我们是不是可以俩俩比较呢,若不同,则前面的那个元素一定就是“单身狗”啦~

下面是这部分的伪代码~

for (i = 0; i < len; i+=2)
{if (arr[i] != arr[i + 1]){printf("单身狗数字是:%d\n", arr[i]);break;}
}

3. 不过,我们还要考虑边界情况呢~

当我们将前面的元素都比较完后,还没有找到单身狗,而按照上面的算法逻辑的话,最后那个元素是无法俩俩比较的,那我们该怎么办呢~

我们不妨立个flag=1;若在上面的逻辑中找到单身狗,flag=0,若没有找到,flag还是=1,

那单身狗就是最后那个元素啦~

int flag = 1;
for (i = 0; i < len; i+=2)
{if (arr[i] != arr[i + 1]){printf("单身狗数字是:%d\n", arr[i]);flag = 0;break;}
}
if (flag == 1)printf("单身狗数字是:%d\n", arr[len-1]);

1.3巧用位操作符

1. 这个题目其实还有更为巧妙的方法呢~

这里先给俩个结论1.相同的俩个元素^(抑或)结果为零~

                                 2.零与其他元素抑或结果为那个元素本身~

那是为什么呢~(其实在我之前的博客也提到过,这里再说明一下)http://【有趣的移位操作符和位操作符(由浅入深轻松搞定!) - CSDN App】http://t.csdnimg.cn/q2ubr

2. 好了,知道了这些那这个题目就显得异常简单了啦~

我们将所有元素抑或起来是不是就找到了那个单身狗呢~

下面是这部分的伪代码~

int find_single_dog(int arr[], int sz)
{int ret = 0;int i = 0;for (i = 0; i < sz; i++){ret ^= arr[i];}return ret;
}//sz是数组的长度

2.单身狗2

1.1 题目描述

一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如:

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

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

1.2排序寻找

1.这个题目如果用排序来做的话,主要的算法部分其实和前面的是差不多的~

唯一不同的是我们要找的俩个“单身狗”后才能结束寻找~

我们可以用count来计数,当count==2时,就结束寻找~

代码如下~

for (i = 0; i < len-1; i+=2)
{if (arr[i] != arr[i + 1]){printf("单身狗是%d\n", arr[i]);count++;i--;}if (count == 2)break;
}

2. 当然我们还要考虑边界情况的~

我们可以很容易的知道上面的代码逻辑一定可以至少找到一个单身狗5

当循环结束后i是等于len-1的,所以优化后的代码如下~

	for (i = 0; i < len-1; i+=2){if (arr[i] != arr[i + 1]){printf("单身狗是%d\n", arr[i]);count++;i--;}if (count == 2)break;}if(i==len-1)printf("单身狗是%d\n", arr[i]);//考虑边界情况
}

1.3巧用位操作符

1. 上面的代码还是不够牛逼,让我们看看牛逼的代码~

当单身狗只有一个时,我们可以用位操作的方法快速找到,这里有俩个不同的元素,这时我们就不可以简单的将他们全部抑或起来了,那怎么办呢~

2. 我们可不可以想办法将这俩个单身狗分开来后再进行抑或呢~(举个栗子,数据不一定正确分配)

3. 我们先将所有元素抑或起来(还是以上面的元素为例~)

然后我们将结果放到临时变量tmp中,那tmp到底有什么用呢~

我们仔细思考一下就会惊奇的发现(找到tmp二进制中第一个1(相异为1)可以区分俩个不同的单身狗!)即:找到有分歧的一位。在这一位上,两个数一定是一个1一个0

找tmp二进制中的第一个1的代码如下~

//找到tmp二进制中第一个1(相异为1)区分俩个不同的元素
int count = 0;//用count来记录tmp二进制中的第一个1
while ((tmp & (1<<count))==0)
{count++;
}

4. 最后,我们要将数组中的所有元素右移count位后再与一按位与(此时一定可以将不同的单身狗区分开来,至于其他相同的元素不管他们那一位上是1还是0都会被分配到相同的部分

//数组中的元素右移count后&1
for (int i = 0; i < len; i++)
{if (((arr[i] >>= count) & 1) == 1)*tmp1^= arr[i];else*tmp2^= arr[i];
}

注:tmp1和tmp2一定要初始化为零呢~,还要注意运算符的优先级(一定要加括号按照我们的思路计算!)

附:完整的代码~

void Fun(int arr[], int*tmp1, int*tmp2, int len)
{int tmp = 0;//将所有元素抑或起来结果放到tmp中for (int i = 0; i < len; i++)tmp ^= arr[i];//找到tmp二进制中第一个1(相异为1)区分俩个不同的元素int count = 0;//用count来记录tmp二进制中的第一个1while ((tmp & (1<<count))==0){count++;}//数组中的元素右移count后&1for (int i = 0; i < len; i++){if (((arr[i] >>= count) & 1) == 1)*tmp1^= arr[i];else*tmp2^= arr[i];}
}

5.完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

 

这篇关于OJ刷题:《剑指offer》之单身狗1、2 !(巧用位操作符,超详细讲解!)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/677832

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

python连接本地SQL server详细图文教程

《python连接本地SQLserver详细图文教程》在数据分析领域,经常需要从数据库中获取数据进行分析和处理,下面:本文主要介绍python连接本地SQLserver的相关资料,文中通过代码... 目录一.设置本地账号1.新建用户2.开启双重验证3,开启TCP/IP本地服务二js.python连接实例1.