目录
- 一.找出单身狗
- 版本1
- 版本2
- 二.atoi函数
- 介绍atoi函数
- atoi函数的模拟实现
一.找出单身狗
版本1
题目：
一个数组中只有一个数字是出现一次，其他所有数字都出现了两次
找出这一个只出现一次的数字
一个数组比如是1、2、3、4、5、1、2、3、4
只有5出现一次，其他数字都是成对出现的，所以5就是单身狗。
思路：异或法
这里给大家回顾下异或：相同为0，相异为1
比如：
a ^ a = 0
a ^ 0 = a
异或是支持交换律的，用具体数字举例：3 ^ 5 ^ 3
3的二进制是011
5的二进制是101
异或的结果是110
再和3异或
得到的是101——数字5
3 ^ 3 ^ 5
3和3异或是0
0和5异或是5
所以回到前面举例的数组
1、2、3、4、5、1、2、3、4
也等价于：
1、1、2、2、3、3、4、4、5
前面成对出现的数字都异或为0（0异或0还是0），0与唯一出现的数字异或就是这个数字，也就是单身狗
代码：
int F_S_dog1(int arr[], int sz)
{int ret = 0;int i = 0;for (i = 0; i < sz; i++){ret ^= arr[i];}return ret;
}
int main()
{int arr[] = { 1,2,3,4,5,1,2,3,4 };int sz = sizeof(arr) / sizeof(arr[0]);int dog = F_S_dog1(arr, sz);printf("%d\n", dog);return 0;
}
版本2
题目：
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次
找出这两个只出现一次的数字
一个数组比如是1、2、3、4、5、6、1、2、3、4
只有5和6出现一次，其他数字都是成对出现的，所以5和6就是单身狗。
思路：
- 将数组进行分组处理，每组有一个单身狗，其他数字成对出现
- 成对的数字在同一组里，然后采用异或法找出单身狗
比如分组后为：
1、1、3、3、5
2、2、4、4、6
那么任何进行分组呢？
首先，用版本1的思路我们可以先对原数据进行异或处理，就可以找到那两个是单身狗的数字
1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 ^ 5 ^ 6 = 5 ^ 6
5和6异或的结果一定不为0
5的二进制是101
6的二进制是110
异或为011
也就是说5和6异或的结果的二进制后面两位是不同的
以最低位为例，5的最低位是1，6的最低位是0，那么分组就可以根据最低位来判断
1的最低位是1，2的最低位是0，
3的最低位是1，4的最低位是0，
分组后：
1、1、3、3、5
2、2、4、4、6
假如不是5和6，是6和8，最低位相同，那么可以用前面一位比较，方法同上
但不管怎么分，都可以把两个单身狗数字分到不同的组
第二步，找出两个数异或的结果第几位不同
还是前面的两个数字5和6，异或的结果为011，后面两位不同。为了方便起见，使用一个变量（pos）记录最低位不同是移动了几位，移动pos位按位与得到是1就说明两个数字二进制的这一位不同（也就是1，因为1按位与1得到的是1），然后跳出循环。
最后一步，正式开始分组，然后还是异或法找到单身狗
数组的每个元素移动pos位，把移动pos按位与相同的数字放在同一组，然后异或法找到单身狗
当然，只是找到其中一个单身狗，另一个单身狗就是两个单身狗异或的结果再异或前面已经找到的单身狗
代码：
void F_S_dog2(int arr[], int sz, int* pd1, int* pd2)
{int ret = 0;int i = 0;//找到两个唯一的数for (i = 0; i < sz; i++){ret ^= arr[i];}int pos = 0;//找到第几位不同for (i = 0; i < 32; i++){if ((ret >> i & 1) == 1){pos = i;break;}}//分组for (i = 0; i < sz; i++){if ((arr[i] >> pos & 1) == 1){*pd1 ^= arr[i];}}*pd2 = ret ^ *pd1;
}
int main()
{int arr[] = { 1,2,3,4,5,6,1,2,3,4 };int sz = sizeof(arr) / sizeof(arr[0]);int dog1 = 0;int dog2 = 0;F_S_dog2(arr, sz, &dog1, &dog2);printf("%d %d", dog1, dog2);return 0;
}
二.atoi函数
介绍atoi函数
atoi函数的作用是将字符串转换成整数
int atoi (const char * str);
该函数有以下几点要注意：
1.返回值为int 类型的整数，不能超出int 表示的范围
2.该函数首先根据需要丢弃尽可能多的空格字符(如 isspace) ，直到找到第一个非空格字符。然后，从这个字符开始，取一个可选的初始正负号，后跟尽可能多的十进制数字，并返回一个数值
3.字符串可以在构成整数的字符之后包含其他字符，这些字符将被忽略
4.如果 str 中的第一个非空格字符序列不是一个有效的整数，或者由于 str 为空或者它只包含空格字符而不存在这样的序列，则不执行转换并返回零
代码：
#include <stdio.h>
#include <stdlib.h>
int main()
{int ret = atoi("-456");printf("%d\n", ret);return 0;
}
atoi函数的模拟实现
首先要考虑几个问题：
1.传过来的字符串是否为空指针
2.是否为空字符串
3.有空格字符怎么办
4.遇到正负号
5.是否为数字字符
6.数值太大
接下来一个一个解决问题：
1.传过来的字符串是否为空指针
可以用assert进行断言，防止为空
assert(str);
2.是否为空字符串
加个判断条件，如果为’ \0 '，就返回0
if (*str == '\0'){return 0;}
3.有空格字符怎么办
使用isspace函数判断是否有空格字符，如果有，向后走一步
while (isspace(*str)){str++;}
4.遇到正负号
在此之前定义一个变量flag为1，如果遇到 ’ - '，flag=-1，向后走一步；遇到 ’ + ’ ，向后走一步。
if (*str == '-'){flag = -1;str++;}else if (*str == '+'){str++;}
5.是否为数字字符 && 6.数值太大
使用isdigit函数判断是否为数字字符，如果不是，也就是说刚开始就遇到其他字符或者在中途遇到其他字符，就直接返回前面的数字字符；如果是数字字符，每次循环的值等于上次的值乘以10再加上数字字符减去字符0，得到整数。
还要加上一个判断，如果要返回的值超过int 类型的范围，说明返回值为异常，直接返回0。
long long ret = 0;while (*str){if (isdigit(*str)){ret = ret * 10 + flag * (*str - '0');if (ret<INT_MIN || ret>INT_MAX){return 0;}}else{return (int)ret;}str++;}
最后的返回值处理
定义一个枚举，如果是VALID，标记为是正常的返回值，是INVALID，标记为异常的返回值。同时给个全局变量State，只有最后让State等于VALID，就说明返回的是正常的值，其他的则为异常。
enum State
{VALID,INVALID
}State = INVALID;//全局变量判断是否为异常的返回值
State = VALID;return (int)ret;
代码：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
enum State
{VALID,INVALID
}State = INVALID;//全局变量判断是否为异常的返回值
int my_atoi(const char* str)
{int flag = 1;//判断空指针assert(str);//判断空字符串if (*str == '\0'){return 0;}//判断空格字符while (isspace(*str)){str++;}//遇到正负号if (*str == '-'){flag = -1;str++;}else if (*str == '+'){str++;}//返回整数值，遇到其他字符直接返回long long ret = 0;while (*str){if (isdigit(*str)){ret = ret * 10 + flag * (*str - '0');if (ret<INT_MIN || ret>INT_MAX){return 0;}}else{return (int)ret;}str++;}//正常返回State = VALID;return (int)ret;
}
int main()
{int ret = my_atoi(" -456ab21");if (State == VALID){printf("%d\n", ret);}else{printf("异常返回：%d\n", ret);}return 0;
}
感谢观看~
