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;}

程序執行結果：