atoi函數(shù)

這是個非常有趣的函數(shù)，它的功能是把字符串中的數(shù)字轉(zhuǎn)化為一個整數(shù)。
但是其中的坑是有不少的，我們往下面分析分析。

先來使用體會體會：

#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函數(shù)執(zhí)行結(jié)果：

模擬實現(xiàn)

剛開始的時候覺得模擬實現(xiàn)atoi函數(shù)很簡單，轉(zhuǎn)化一下數(shù)字嘛，但是在上面使用過后就感受到復(fù)雜了。它的要求有以下幾點要注意：
1、不能傳空指針過來
2、轉(zhuǎn)化有范圍限制，超出范圍就返回0
3、能轉(zhuǎn)化的字符只有：正負(fù)號、空格、數(shù)字，其它字符都不能轉(zhuǎn)化
4、轉(zhuǎn)化過數(shù)字，就不能再轉(zhuǎn)化其它字符
5、轉(zhuǎn)化過正負(fù)號，后面就不能再轉(zhuǎn)化正負(fù)號

模擬實現(xiàn)如下：

#define _CRT_SECURE_NO_WARNINGS 1#include #include #include int my_atoi(const char* p){	if (p == NULL) //傳過來空指針就直接返回	{		return 0;	}	int flag = 1;   //檢測+-符號，正號為1，負(fù)號就為-1	int tmp = 1;    //檢測轉(zhuǎn)化過數(shù)字和正負(fù)號沒有，轉(zhuǎn)化過就置為0	int ret = 0;    //接收數(shù)字	while (*p != "/0")	{		if (*p <= "9" && *p >= "0")		{		     ret = 10 * ret + flag * (*p - "0");			 if (ret< INT_MIN || ret> INT_MAX) //驗證整數(shù)在有效范圍			 {				 return 0;			 }			 tmp = 0;  //轉(zhuǎn)化過數(shù)字，置為0			 p++;		}		//檢測第一次遇到正負(fù)號，而已經(jīng)轉(zhuǎn)化過到這里就不符合條件		else if (*p == "+" && tmp != 0)		{			p++;			flag = 1;			tmp = 0;		}		else if (*p == "-" && tmp != 0)		{			p++;			flag = -1;			tmp = 0;		}		//檢測沒轉(zhuǎn)化過數(shù)字和正負(fù)號之前遇到空格，而已經(jīng)轉(zhuǎn)化過到這里就不符合條件		else if (*p == " "&& tmp != 0)		{			p++;		}		else		{			//跳到這里分為以下幾種情況：			//1.不是數(shù)字			//2.已經(jīng)轉(zhuǎn)化過數(shù)字再遇到正負(fù)號			//3.已經(jīng)轉(zhuǎn)化過數(shù)字再遇到空格			//以上都不符合條件，結(jié)束檢測字符串			break;		}	}	return ret;}int main(){	char arr[] = " -123 45+  ";	char arr2[] = "+34896  ";	char arr3[] = "abc235";	char arr4[] = "+2335+11";	char arr5[] = "++567  ";	printf("庫函數(shù)atoi實現(xiàn)結(jié)果：/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實現(xiàn)結(jié)果：/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;}

程序執(zhí)行結(jié)果對比如下：

單身狗問題

題目內(nèi)容：
一個數(shù)組中只有兩個數(shù)字是出現(xiàn)一次，其他所有數(shù)字都出現(xiàn)了兩次。找出這兩個只出現(xiàn)一次的數(shù)字。

方法1：暴力解決

最簡單粗暴的方法就是每一位數(shù)字都與數(shù)組中除了自己之外的元素遍歷一遍，如果沒有找到相同的就說明就是單身狗。
代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1#include void Find(int* p, int sz){	int i = 0, j = 0;	for (i = 0; i < sz; i++)	{		//每一位數(shù)字都與數(shù)組中除了自己之外的元素遍歷一遍		for (j = 0; j < sz; j++)		{			//找到相同的數(shù)字就跳出第二層循環(huán)			//j肯定不等于sz			if (p[i] == p[j] && i != j)			{				break;			}		}		//如果不是break跳到這里，則沒有找到相同數(shù)字		//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);}

程序執(zhí)行結(jié)果：

方法2：排序解決

一個數(shù)組中只有兩個數(shù)字是出現(xiàn)一次，其他所有數(shù)字都出現(xiàn)了兩次。這句話給了我們不少信息，說明如果數(shù)組從小到大排序好的話，那么兩個相鄰元素不相等的話，前者肯定是單身狗。
解決思路： 第一步我們先用冒泡排序把數(shù)組元素從小到大排序好，然后我們在逐一驗證兩個相鄰元素是否相等，如果相等那就下標(biāo)就自增2，如果不相等說明前者是單身狗，并且下標(biāo)自增1，直到找完數(shù)組中元素。
代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1#include //冒泡排序把數(shù)組排成有序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;		}	}}//在有序數(shù)組中找單身狗void Search(int* p, int sz){	int i = 0;	while (i < sz)	{		//相鄰元素相等下標(biāo)自增2		if (p[i] == p[i+1])		{			i+=2;		}		//相鄰元素不相等下標(biāo)自增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);}

程序執(zhí)行結(jié)果：

方法3：異或解決

這個方法不易想到，構(gòu)思非常巧妙，是今天的重點菜。
我們知道兩個相同的元素異或是什么結(jié)果？不錯就是為0。那么根據(jù)題目內(nèi)容：
一個數(shù)組中只有兩個數(shù)字是出現(xiàn)一次，其他所有數(shù)字都出現(xiàn)了兩次。所以定義一個變量tmp，把數(shù)組中的元素從第一位異或到最后一位保存到變量tmp中會出現(xiàn)什么結(jié)果呢？
結(jié)果就是變量tmp是兩個單身狗數(shù)字異或的內(nèi)容。

可問題來了，我們求的是兩個單身狗，而不是要異或的內(nèi)容呀！不急不急，接著分析，
當(dāng)我們知道兩個單身狗異或的內(nèi)容后，結(jié)果轉(zhuǎn)化為二進(jìn)制后，里面肯定至少有一位不同，因為每一位都相同的話就不是兩個不同的數(shù)字了。

而至少有一位不同，那變量tmp中肯定有一位為1，其中單身狗不同的一位是0，另外一個單身狗不同的一位是1。
所以我們在tmp中從右邊往左邊找到1的下標(biāo)num，異或結(jié)果中第一個1的下標(biāo)就找到了。
而在數(shù)組中相同的數(shù)字二進(jìn)制位下標(biāo)num也是0或者1，所以我們把數(shù)組中所有元素都與1左移num位 并 過一遍，大于或者等于1的就再異或一遍，最終得到一個單身狗，并的結(jié)果為0的也異或一遍，最終也到一個單身狗。相當(dāng)于把兩個單身狗放在不同的數(shù)組中進(jìn)行異或。
代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1#include void Find(int* p, int sz){	int i = 0;	int tmp = 0; //把數(shù)組中異或的結(jié)果放在tmp中	for (i = 0; i < sz; i++)	{		tmp = tmp ^ p[i];	}	//在異或結(jié)果中找第一個為1的下標(biāo)是多少	for (i = 0; i < 32; i++)	{		if (tmp & (1 << i))		{			break;		}	}	int num = i; //把下標(biāo)保存到num中	int sum1 = 0;	int sum2 = 0;	for (i = 0; i < sz; i++)	{		//數(shù)組中元素并上 1左移num位的元素分不同結(jié)果 進(jìn)行異或		//結(jié)果大于或者等于1為一組		if (p[i] & (1<<num))		{			sum1 = sum1 ^ p[i]; 		}		//結(jié)果為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;}

程序執(zhí)行結(jié)果：