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

相关文章

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

C++操作符重载实例(独立函数)

C++操作符重载实例,我们把坐标值CVector的加法进行重载,计算c3=c1+c2时,也就是计算x3=x1+x2,y3=y1+y2,今天我们以独立函数的方式重载操作符+(加号),以下是C++代码: c1802.cpp源代码: D:\YcjWork\CppTour>vim c1802.cpp #include <iostream>using namespace std;/*** 以独立函数

沁恒CH32在MounRiver Studio上环境配置以及使用详细教程

目录 1.  RISC-V简介 2.  CPU架构现状 3.  MounRiver Studio软件下载 4.  MounRiver Studio软件安装 5.  MounRiver Studio软件介绍 6.  创建工程 7.  编译代码 1.  RISC-V简介         RISC就是精简指令集计算机(Reduced Instruction SetCom

arduino ide安装详细步骤

​ 大家好,我是程序员小羊! 前言: Arduino IDE 是一个专为编程 Arduino 微控制器设计的集成开发环境,使用起来非常方便。下面将介绍如何在不同平台上安装 Arduino IDE 的详细步骤,包括 Windows、Mac 和 Linux 系统。 一、在 Windows 上安装 Arduino IDE 1. 下载 Arduino IDE 打开 Arduino 官网

GPT系列之:GPT-1,GPT-2,GPT-3详细解读

一、GPT1 论文:Improving Language Understanding by Generative Pre-Training 链接:https://cdn.openai.com/research-covers/languageunsupervised/language_understanding_paper.pdf 启发点:生成loss和微调loss同时作用,让下游任务来适应预训

多路转接之select(fd_set介绍,参数详细介绍),实现非阻塞式网络通信

目录 多路转接之select 引入 介绍 fd_set 函数原型 nfds readfds / writefds / exceptfds readfds  总结  fd_set操作接口  timeout timevalue 结构体 传入值 返回值 代码 注意点 -- 调用函数 select的参数填充  获取新连接 注意点 -- 通信时的调用函数 添加新fd到

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

【详细介绍一下GEE】

GEE(Google Earth Engine)是一个强大的云计算平台,它允许用户处理和分析大规模的地球科学数据集,如卫星图像、气候模型输出等。以下是对GEE用法的详细介绍: 一、平台访问与账户设置 访问GEE平台: 用户可以通过访问Google Earth Engine的官方网站来开始使用GEE。 创建账户: 用户需要注册并登录Google账户,然后申请访问GEE平台。申请过程可能需要提

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

ispunct函数讲解 <ctype.h>头文件函数

目录 1.头文件函数 2.ispunct函数使用  小心!VS2022不可直接接触,否则..!没有这个必要,方源一把抓住VS2022,顷刻 炼化! 1.头文件函数 以上函数都需要包括头文件<ctype.h> ,其中包括 ispunct 函数 #include<ctype.h> 2.ispunct函数使用 简述: ispunct函数一种判断字符是否为标点符号的函