资讯专栏INFORMATION COLUMN

atoi函数模拟实现和解决单身狗问题(C语言实现)

harryhappy / 2694人阅读

摘要:文章目录函数模拟实现单身狗问题方法暴力解决方法排序解决方法异或解决函数这是个非常有趣的函数,它的功能是把字符串中的数字转化为一个整数。相当于把两个单身狗放在不同的数组中进行异或。

atoi函数

这是个非常有趣的函数,它的功能是把字符串中的数字转化为一个整数。
但是其中的坑是有不少的,我们往下面分析分析。

先来使用体会体会:

#define _CRT_SECURE_NO_WARNINGS 1#include #include int main(){	char arr[] = " -123 45+  ";	char arr2[] = "+34896  ";	char arr3[] = "abc235";	char arr4[] = "+2335+11";	char arr5[] = "++567  ";	printf("%d/n", atoi(arr));	printf("%d/n", atoi(arr2));	printf("%d/n", atoi(arr3));	printf("%d/n", atoi(arr4));	printf("%d/n", atoi(arr5));	return 0;}

atoi函数执行结果:

模拟实现

刚开始的时候觉得模拟实现atoi函数很简单,转化一下数字嘛,但是在上面使用过后就感受到复杂了。它的要求有以下几点要注意:
1、不能传空指针过来
2、转化有范围限制,超出范围就返回0
3、能转化的字符只有:正负号、空格、数字,其它字符都不能转化
4、转化过数字,就不能再转化其它字符
5、转化过正负号,后面就不能再转化正负号

模拟实现如下:

#define _CRT_SECURE_NO_WARNINGS 1#include #include #include int my_atoi(const char* p){	if (p == NULL) //传过来空指针就直接返回	{		return 0;	}	int flag = 1;   //检测+-符号,正号为1,负号就为-1	int tmp = 1;    //检测转化过数字和正负号没有,转化过就置为0	int ret = 0;    //接收数字	while (*p != "/0")	{		if (*p <= "9" && *p >= "0")		{		     ret = 10 * ret + flag * (*p - "0");			 if (ret< INT_MIN || ret> INT_MAX) //验证整数在有效范围			 {				 return 0;			 }			 tmp = 0;  //转化过数字,置为0			 p++;		}		//检测第一次遇到正负号,而已经转化过到这里就不符合条件		else if (*p == "+" && tmp != 0)		{			p++;			flag = 1;			tmp = 0;		}		else if (*p == "-" && tmp != 0)		{			p++;			flag = -1;			tmp = 0;		}		//检测没转化过数字和正负号之前遇到空格,而已经转化过到这里就不符合条件		else if (*p == " "&& tmp != 0)		{			p++;		}		else		{			//跳到这里分为以下几种情况:			//1.不是数字			//2.已经转化过数字再遇到正负号			//3.已经转化过数字再遇到空格			//以上都不符合条件,结束检测字符串			break;		}	}	return ret;}int main(){	char arr[] = " -123 45+  ";	char arr2[] = "+34896  ";	char arr3[] = "abc235";	char arr4[] = "+2335+11";	char arr5[] = "++567  ";	printf("库函数atoi实现结果:/n");	printf("%d/n", atoi(arr));	printf("%d/n", atoi(arr2));	printf("%d/n", atoi(arr3));	printf("%d/n", atoi(arr4));	printf("%d/n/n", atoi(arr5));	printf("模拟atoi实现结果:/n");	printf("%d/n", my_atoi(arr));	printf("%d/n", my_atoi(arr2));	printf("%d/n", my_atoi(arr3));	printf("%d/n", my_atoi(arr4));	printf("%d/n", my_atoi(arr5));	return 0;}

程序执行结果对比如下:

单身狗问题

题目内容:
一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。找出这两个只出现一次的数字。

方法1:暴力解决

最简单粗暴的方法就是每一位数字都与数组中除了自己之外的元素遍历一遍,如果没有找到相同的就说明就是单身狗。
代码如下:

#define _CRT_SECURE_NO_WARNINGS 1#include void Find(int* p, int sz){	int i = 0, j = 0;	for (i = 0; i < sz; i++)	{		//每一位数字都与数组中除了自己之外的元素遍历一遍		for (j = 0; j < sz; j++)		{			//找到相同的数字就跳出第二层循环			//j肯定不等于sz			if (p[i] == p[j] && i != j)			{				break;			}		}		//如果不是break跳到这里,则没有找到相同数字		//j肯定等于sz,p[i]就是单身狗		if (j == sz)		{			printf("%d ", p[i]);		}	}}int main(){	int arr[] = { 5,5,9,4,6,2,4,6,1,2 };	int sz = sizeof(arr) / sizeof(arr[0]);	Find(arr, sz);}

程序执行结果:

方法2:排序解决

一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。这句话给了我们不少信息,说明如果数组从小到大排序好的话,那么两个相邻元素不相等的话,前者肯定是单身狗。
解决思路: 第一步我们先用冒泡排序把数组元素从小到大排序好,然后我们在逐一验证两个相邻元素是否相等,如果相等那就下标就自增2,如果不相等说明前者是单身狗,并且下标自增1,直到找完数组中元素。
代码如下:

#define _CRT_SECURE_NO_WARNINGS 1#include //冒泡排序把数组排成有序void BubbleSort(int* p, int sz) {	int i = 0, j = 0;	for (i = 0; i < sz - 1; i++)	{		int flag = 1;		for (j = 0; j < sz - 1 - i; j++)		{			if (p[j] > p[j + 1])			{				flag = 0;				int tmp = p[j];				p[j] = p[j + 1];				p[j + 1] = tmp;			}		}		if (flag == 1)		{			return;		}	}}//在有序数组中找单身狗void Search(int* p, int sz){	int i = 0;	while (i < sz)	{		//相邻元素相等下标自增2		if (p[i] == p[i+1])		{			i+=2;		}		//相邻元素不相等下标自增1		//并且前者是单身狗		else		{			printf("%d ", p[i]);			i++;		}	}}int main(){	int arr[] = { 5,5,9,4,6,2,4,6,1,2 };	int sz = sizeof(arr) / sizeof(arr[0]);	BubbleSort(arr, sz);	Search(arr, sz);}

程序执行结果:

方法3:异或解决

这个方法不易想到,构思非常巧妙,是今天的重点菜。
我们知道两个相同的元素异或是什么结果?不错就是为0。那么根据题目内容:
一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。所以定义一个变量tmp,把数组中的元素从第一位异或到最后一位保存到变量tmp中会出现什么结果呢?
结果就是变量tmp是两个单身狗数字异或的内容。

可问题来了,我们求的是两个单身狗,而不是要异或的内容呀!不急不急,接着分析,
当我们知道两个单身狗异或的内容后,结果转化为二进制后,里面肯定至少有一位不同,因为每一位都相同的话就不是两个不同的数字了。

而至少有一位不同,那变量tmp中肯定有一位为1,其中单身狗不同的一位是0,另外一个单身狗不同的一位是1。
所以我们在tmp中从右边往左边找到1的下标num,异或结果中第一个1的下标就找到了。
而在数组中相同的数字二进制位下标num也是0或者1,所以我们把数组中所有元素都与1左移num位 并 过一遍,大于或者等于1的就再异或一遍,最终得到一个单身狗,并的结果为0的也异或一遍,最终也到一个单身狗。相当于把两个单身狗放在不同的数组中进行异或。
代码如下:

#define _CRT_SECURE_NO_WARNINGS 1#include void Find(int* p, int sz){	int i = 0;	int tmp = 0; //把数组中异或的结果放在tmp中	for (i = 0; i < sz; i++)	{		tmp = tmp ^ p[i];	}	//在异或结果中找第一个为1的下标是多少	for (i = 0; i < 32; i++)	{		if (tmp & (1 << i))		{			break;		}	}	int num = i; //把下标保存到num中	int sum1 = 0;	int sum2 = 0;	for (i = 0; i < sz; i++)	{		//数组中元素并上 1左移num位的元素分不同结果 进行异或		//结果大于或者等于1为一组		if (p[i] & (1<<num))		{			sum1 = sum1 ^ p[i]; 		}		//结果为0是为一组		else		{			sum2 = sum2 ^ p[i];		}	}	//最终得到两个单身狗	printf("sum1=%d  sum2=%d/n", sum1, sum2);}int main(){	int arr[] = { 5,5,9,4,6,2,4,6,1,2 };	int sz = sizeof(arr) / sizeof(arr[0]);	Find(arr, sz);	return 0;}

程序执行结果:

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/121855.html

相关文章

  • 【剑指offer系列刷题】第一篇——寻找单身

    摘要:剑指系列刷题第一篇题目来源数组中数字出现的次数大家可以去测试一下自己的代码博主码云链接文章目录前言题目描述解题思路解题代码前言这是剑指系列刷题第一篇文章,大家可以互相学习一下。其中的两个单身狗是和。 ...

    xavier 评论0 收藏0
  • Pygame实战:慎点|虐单身的最高境界是…【附源码】

    摘要:导语各位戏精大家好我是木木子,这个中秋已经结束了,你们都带着对象回家了码中秋那几天朋友圈简直是大型秀恩爱现场。 导语 各位戏精大家好!我是木木子,这个中秋已经结束了,你们都带着对象回家了码? 中秋那几天朋友圈简直是大型秀恩爱现场。 又是一年中秋夜,依旧凭实力单身!呼吁大家记得保护下单身狗啊喂...

    DDreach 评论0 收藏0
  • c语言中常见的字符串操作函数,内存操作函数及其他函数详解

    strlen函数 1.函数原型 size_t strlen(const char *string ); 我们也可以打开MSDN查看他的原型  2.函数功能:求一个字符串指定string字符串的长度 3.strlen函数的实现: 实现的思想是这样的我们只要让一个指针指向字符串的起始位置,让他一直往后走直到遇到/0就停止在上述过程中用计数器count统计str走了多少步,count...

    reclay 评论0 收藏0
  • javascript知识点

    摘要:模块化是随着前端技术的发展,前端代码爆炸式增长后,工程化所采取的必然措施。目前模块化的思想分为和。特别指出,事件不等同于异步,回调也不等同于异步。将会讨论安全的类型检测惰性载入函数冻结对象定时器等话题。 Vue.js 前后端同构方案之准备篇——代码优化 目前 Vue.js 的火爆不亚于当初的 React,本人对写代码有洁癖,代码也是艺术。此篇是准备篇,工欲善其事,必先利其器。我们先在代...

    Karrdy 评论0 收藏0

发表评论

0条评论

harryhappy

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<