解题所需要的C语言基础知识

hello!从现在开始就进入本题解的正式内容了。首先给大家用图解的方式介绍3个C语言位运算的基本操作符 & | ^

这些知识对下面的解题都非常重要,一定要熟练掌握,不然等会会有一种“我在哪,我是谁我在干什么”的感觉。

只出现一次的数字I

题目描述

只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1] 输出: 1
示例 2:

输入: [4,1,2,1,2] 输出: 4

力扣本题链接

解题思路

首先,根据题意,“有不可以额外使用空间这个限定”,看到这里以后要本能的往位运算上面去靠,因为位运算可以不开辟额外空间解决很多问题,然后回看一下刚刚回顾的位运算知识,就知道我们要用到 ^这个操作符了,因为它可以非常简单的消除重复项,剩下只出现一次的数字。

说了这么多,接下来让我们来看看代码的实现

int singleNumber(int* nums, int numsSize){
int ret=0;//0异或任何数都不会印象他的实际值
for(int i=0;i<numsSize;i++)
{
 ret^=nums[i];//所有数异或,重复的消掉,剩下只出现一次的数字
}
return ret;//返回这个数字
}

这只是一个开胃菜,下面正式进入主菜

只出现一次的数字II

题目描述

只出现一次的数字 II 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,3,2] 输出: 3
``示例 2:

输入: [0,1,0,1,0,1,99] 输出: 99

力扣本题链接

解题思路

如图所示,考虑数字的二进制位形式,出现三次的数字,二进制位各位上的1都是三的倍数,所以求出各位上的1数目,再对3求余,则可求出只出现一次的数字

那么要怎样求取二进制位各位上1的数目呐,那就要用到&这个操作符了,来看代码实现吧

int singleNumber(int* nums, int numsSize){
 
 int ret=0;
for(int i=0;i<32;++i)//循环遍历二进制位每一位
{
long cnt=0;//不用long,力扣的编译器不通过,不让int类型左移31位,我也不知道
 for(int j=0;j<numsSize;++j) {//将nums数组中每一个数拿出来,二进制位向右移动i位,与1按位与,
 cnt+=(nums[j]>>i)&1;//则可求出二进制位第i位是否为1;
 }
 ret+=(cnt%3)<<i;//将cnt的值模3,求出只出现一次的那个数第i位为1还是为0,再向左移动i位还原,最后相加求出这个数
}
return ret;
}

好了,这个题目就圆满解决了。

只出现一次的数字III

这个题目就很有技巧了 题目描述
260. 只出现一次的数字 III 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶:你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

示例 1:

输入:nums = [1,2,1,3,2,5] 输出:[3,5] 解释:[5, 3] 也是有效的答案。
示例 2:

输入:nums = [-1,0] 输出:[-1,0]
示例 3:

输入:nums = [0,1] 输出:[1,0]

力扣本题链接

解题思路

根据第一题的思路,就知道要全部按位异或,消除重复项。但是两个只出现一次的数也异或在了一起,我们的难点就是怎么将这两个数分离。接下来就用图示法来告诉大家怎样分离两个数

接下来是代码的实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
int m = 0;
int ret = 0;
for (int i = 0; i < numsSize; i++)
{
	ret ^= nums[i];//将全部数异或
}
while (m < 32)
{
	if ((ret>>m)&1)//找出为1的第m位
		break;
	else
  ++m;
}
int x1 = 0, x2 = 0;//分组
int j=0;
while(j<numsSize)
{
	if ((nums[j]>>m)&1)
		x1 ^= nums[j];//异或出只出现一次的数字
	else
		x2 ^= nums[j];
  j++;
}
int* reRer = (int*)malloc(sizeof(int) * 2);
reRer[0] = x1;
reRer[1] = x2;
*returnSize=2;//根据题意返回长度
return reRer;//返回这两个数
}

小编总结

这是我第一次写题解,选了三个相对简单常见的题目,不难,但是也能反应出一种做题的思想。我希望大家不是简单的学会这3个题目,而是学会这种思想去解决更多的题目。同时大家有好的解题方案,也可以在评论区中留言哦,大家互相学习,一起进步。

到此这篇关于如何利用C语言位运算解决只出现一次数字的文章就介绍到这了,更多相关C语言位运算解决出现数字内容请搜索程序员的世界以前的文章或继续浏览下面的相关文章希望大家以后多多支持程序员的世界!

C语言位运算解决只出现一次的数字的更多相关文章

  1. C语言之漫谈指针(下)

    C语言之漫谈指针(下)在上节我们讲到了一些关于指针的基础知识:详见:C语言之漫谈指针(上)本节大纲:零.小tips一.字符指针二.指针数组与数组指针三.数组传参与指针传参四.函数指针及函数指针数组五.回调函数六.例题讲解 零.小tips在正式开始下节之前,我们先来穿插两个小tips:1.打印函数......

  2. C语言中的const如何保证变量不被修改

    这小段文章要理清楚的是,在C语言中,const是如何保证变量不被修改的?我们可以想到两种方式:第一种,由编译器来阻止修改const变量的语句,让这种程序不能通过编译;第二种,由操作系统来阻止,即把const 的内存地址访问权限标记为“只读”,一旦运行中的程序试图修改它,就会产生异常,终止进程。上面想......

  3. C语言递归之汉诺塔和青蛙跳台阶问题

    递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题、汉诺塔问题等,在研究递归问题时我们要注意三点:1.递归的结束条件2.递归在每次进行过程中,都得离条件越来越近3.相邻两次递归调用之间的关联关系汉诺塔问题:有三根杆子A, B, C。A杆上有N个(N >......

  4. C语言位运算解决只出现一次的数字

    解题所需要的C语言基础知识hello!从现在开始就进入本题解的正式内容了。首先给大家用图解的方式介绍3个C语言位运算的基本操作符 & | ^这些知识对下面的解题都非常重要,一定要熟练掌握,不然等会会有一种“我在哪,我是谁我在干什么”的感觉。只出现一次的数字I题目描述只出现一次的数字给定一个非......

  5. C语言的进制转换及算法实现教程

    1、其他进制转十进制1.1、二进制转十进制转换规程: 从最低位开始,将每个位上的数提取出来,乘以2的(位数-1)次方,然后求和,例如:二进制 1011 = 1*2^0 + 1*2^1 + 0*2^2 + 1*2^3 = 1 + 2 + 0 + 8 = 111.2、八制转十进制转换规则: 从最低位开始......

  6. 虚函数表-C++多态的实现原理解析

    参考:http://c.biancheng.net/view/267.html1、说明我们都知道多态指的是父类的指针在运行中指向子类,那么它的实现原理是什么呢?答案是虚函数表在 关于virtual 一文中,我们详细了解了C++多态的使用方式,我们知道没有 virtual 关键子就没法使用多态2、虚函......

  7. OpenCV 之 图象几何变换

    二维平面中,图像的几何变换有等距、相似、仿射、投影等,如下所示: 1 图象几何变换1.1 等距变换 等距变换 (Isometric Transformation),是一种二维的刚体变换,可理解为旋转和平移的组合 $\quad \beg......

  8. std::async的使用总结

    C++98标准中并没有线程库的存在,直到C++11中才终于提供了多线程的标准库,提供了管理线程、保护共享数据、线程间同步操作、原子操作等类。多线程库对应的头文件是#include ,类名为std::thread。然而线程毕竟是比较贴近系统的东西,使用起来仍然不是很方便,特别是线程同步及获取线程运行结......

  9. C语言中sprintf()函数的用法

    sprintf函数的用法1、该函数包含在stdio.h的头文件中。2、sprintf和平时我们常用的printf函数的功能很相似。sprintf函数打印到字符串中,而printf函数打印输出到屏幕上。sprintf函数在我们完成其他数据类型转换成字符串类型的操作中应用广泛。3、sprintf函数的格......

  10. 关于 C++ 中的强制转换 - 基础篇

    引言假设有基类 A,包含了虚函数 func1,以及有派生类 B,继承于类 A,派生类 B 中实现了函数 func1。此时可以用 A 类型的指针指向 B 类型的对象,并用 A 类型的指针调用 B 类型对象中的函数 func1。这时,就形成了多态。包含虚函数的类 A,我们也称为多态类。由于派生类 B 完......

随机推荐

  1. Perl时间处理函数用法介绍

    一. Perl时间的表示函数1. 表示日期的方式多种多样:"18Jan1973";"18/01/1973";"01/18/1973";"Jan181973";"18-01-73";"18-0......

  2. java DelayQueue的原理浅析

    在对DelayQueue延迟功能的使用上,很多人不能后完全理解延迟的一些功能使用,这里我们深入来挖掘一下DelayQueue的原理。下面将从构造方法、接口、继承体系三个方面进行分析,需要注意的是,相较于其它的阻塞队列,DelayQueue因为延迟的功能多了接口的使用,一起来看具体内容。1.构造方法p......

  3. MongoDB 用户相关操作

    在我们第一次启动MongoDB的时候,仅仅是制定了data数据目录和log日志目录,并没有指定--auth选项,也就是并不需要认证。[root@VM-0-14-centos mongo_27017]# mongoMongoDB shell version v4.0.6connecting to: m......

  4. java集合(List Set Map的使用

    ListList的元素以线性方式存储,可以存放重复对象,List主要有以下两个实现类:ArrayList : 长度可变的数组,可以对元素进行随机的访问,向ArrayList中插入与删除元素的速度慢。LinkedList: 采用链表数据结构,插入和删除速度快,但访问速度慢。SetSet中的......

  5. 理解C#中的 async await

    前言一个老掉牙的话题,园子里的相关优秀文章已经有很多了,我写这篇文章完全是想以自己的思维方式来谈一谈自己的理解。(PS:文中涉及到了大量反编译源码,需要静下心来细细品味)从简单开始为了更容易理解这个问题,我们举一个简单的例子:用异步的方式在控制台上分两步输出“Hello World!”,我这边使用的......

  6. IIS的web.config中跨域访问设置方法

    需求:页面要显示1个图片,但是因为各种原因,导致图片在服务器2上,但是要展示的程序在服务器1 的上面,这样就造成了在显示的时候出现了跨域的问题,本来的思路为直接写个程序进行后台获得图片的路径,然后把图片进行下载出来,然后返回服务器1的图片地址,但是,由于这个周期不确定性和现阶段项目的紧迫性,就放弃了......

  7. vue使用vue-quill-editor富文本编辑器且将图片上传到服务器的功能

    一、准备工作下载vue-quill-editornpm install vue-quill-editor --save 或者 yarn add vue-quill-editor二、定义全局组件quill-editor下载好vue-quill-editor后,我们需要定义一个全局组件,把这个组件名字命......

  8. C# StreamReader类实现读取文件的方法

    在 C# 语言中 StreamReader 类用于从流中读取字符串。它继承自 TextReader 类。StreamReader 类的构造方法有很多,这里介绍一些常用的构造方法,如下表所示。构造方法说明StreamReader(Stream stream)为指定的流创建 StreamReader 类......

  9. C语言递归之汉诺塔和青蛙跳台阶问题

    递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题、汉诺塔问题等,在研究递归问题时我们要注意三点:1.递归的结束条件2.递归在每次进行过程中,都得离条件越来越近3.相邻两次递归调用之间的关联关系汉诺塔问题:有三根杆子A, B, C。A杆上有N个(N >......

  10. JavaScript实现页面动态验证码的实现示例

    引言:现在很多在用户登陆或注册的时候为了防止程序攻击,加入了动态验证的技术,一般是让用户输入随即生成的验证码来实现。我自己写了一个没有跟后台交互的,就在前端验证,发出来给大家看看。效果图: 实现思路:把数字和字母放到一个数组中,通过随机的方式取得数组下标,总共取4个组成验证码;把验证码渲染出来(......