// # -*- coding:utf-8 -*- // # @Author: Mr.chen(ai-chen2050@qq.com) // # @Date: 2018-08-18 21:06:30 // 注：此為第四彈，主要講解字符串、數(shù)值類(lèi)、或其他常見(jiàn)相關(guān)面試筆試題，要求手寫(xiě)。/* 1、替換字符串中的空格。題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy 思路:法一：從頭到尾遍歷字符串做替換，時(shí)間復(fù)雜度為O(n2)，效率低法二：從尾到頭遍歷字符串做替換，時(shí)間復(fù)雜度為O(n)，效率高，下面用它實(shí)現(xiàn) */// 指向字符數(shù)組的字符指針str，字符數(shù)組長(zhǎng)度length void replaceSpace(char *str,int length) {// 邊界檢查1：判斷字符數(shù)組是否為空if(str==NULL)return ;// 遍歷字符串，統(tǒng)計(jì)空格個(gè)數(shù)、替換前字符個(gè)數(shù)、替換后字符個(gè)數(shù)int CountOfBlanks=0; // 空格個(gè)數(shù)int Originallength=0;// 替換前字符個(gè)數(shù)int len=0; // 替換后字符個(gè)數(shù)for(int i=0;str[i]!='\0';++i){Originallength++;if(str[i]==' ')++CountOfBlanks;}len =Originallength+2*CountOfBlanks;// 邊界檢查2：判斷字符數(shù)組是否越界if(len+1>length)return ;// 替換空格char*pStr1=str+Originallength;// 字符指針指向原始字符串的末尾char*pStr2=str+len; // 字符指針指向替換后字符串的末尾while(pStr1 != pStr2) // 替換結(jié)束的條件{if(*pStr1==' '){*pStr2-- ='0';*pStr2-- ='2';*pStr2-- ='%';}else{*pStr2--=*pStr1;}--pStr1;} }/* 2、位運(yùn)算：二進(jìn)制中 1 的個(gè)數(shù)。輸入一個(gè)整數(shù)，輸出該二進(jìn)制中有多少個(gè) 1。經(jīng)過(guò)分析（略）,我們發(fā)現(xiàn)把一個(gè)整數(shù)減去1，并且與原數(shù)進(jìn)行與運(yùn)算會(huì)把該整數(shù)最右邊的一個(gè) 1 變成 0,那么一個(gè)整數(shù)的二進(jìn)制表示中會(huì)有多個(gè) 1,就可以進(jìn)行多少次這樣的操作。基于這種思想,我們可以寫(xiě)出以下代碼。 */ int numberOf1(int n) {int count = 0;while(n){++ count;n = (n -1) & n;}return count; } // 此題最為重要就是發(fā)現(xiàn)規(guī)律，在 Coding/* 3、數(shù)值的整數(shù)次方。實(shí)現(xiàn)函數(shù) double Power(double base,int exponent)求 base 的 exponent 次方，不使用庫(kù)函數(shù)，不考慮大樹(shù)問(wèn)題。思路：注意邊界情況，如果指數(shù)是 0或者負(fù)數(shù)，如果是負(fù)數(shù)，可以取絕對(duì)值，然后求倒數(shù),求倒數(shù)時(shí)注意，分母不能為 0,此外,我們可以采用如下這個(gè)方法(如下圖)求取指數(shù)，已經(jīng)求過(guò)的沒(méi)有必要再次計(jì)算。并且，該公式很容易使用遞歸來(lái)實(shí)現(xiàn)。 */

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

double powerWithUnsignedExponent(double base,unsigned int exponent) {if(exponent == 0)return 1;if(exponent ==1)return base;double result = powerWithUnsignedExponent(base,exponent >> 1);result *= result;//判斷是否是奇數(shù)if((exponent & 0x1) == 1)result *= base;return result; }// 在上面用 >> 右移運(yùn)算符代替了除 2,用位與運(yùn)算符代替了求余 %,判斷是否是奇數(shù)/* 4、調(diào)整數(shù)組順序使奇數(shù)在前面，偶數(shù)在后面。暴力遍歷循環(huán)，時(shí)間效率O(N2),一般方法使用兩個(gè)指針?lè)謩e指向頭和尾，如果有偶數(shù)在奇數(shù)的前面則交換他們。如果第一個(gè)指向偶數(shù),第二個(gè)指向奇數(shù)，則交換他們。如果，面試官還要我們注意擴(kuò)展性(通用屬性)，提高代碼的可重復(fù)性，則可以有如下代碼： */ void ReOrder(int *pData,unsigned int length,bool (*func)(int)) {if(pData == NULL || length == 0)return;int* pBegin = pData;int* pEnd = pData + length -1;while(pBegin < pEnd){while(pBegin < pEnd && !func(*pBegin))++ pBegin;while(pBegin < pEnd && func(*pEnd))-- pEnd;if(pBegin < pEnd){int temp = *pBegin;*pBegin = *pEnd;*pEnd = temp;}} }// 解耦和 bool isEven(int n) {return (n & 1) == 0; }// 調(diào)用時(shí) void ReOrderOddEven(int* pData,unsigned int length) {ReOrder(pData,length, isEven); }/* 5、字符串的排列: 輸入一個(gè)字符串,打印該字符串中的字符的所有的排列，如例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。思路：對(duì)于該問(wèn)題,一般不容易一下想出解決方案。于是,我們應(yīng)該嘗試把復(fù)雜的問(wèn)題分解成小的問(wèn)題，如:我們把一個(gè)字符串看成是兩部分組成：第一部分是它的第一個(gè)字符,第二個(gè)部分是后面所有的字符,如下圖，我們使用兩種不同的顏色背景來(lái)來(lái)區(qū)分字符串的兩部分。我們求整個(gè)字符串的排列,也可以看成兩部分。首先求所有可能出現(xiàn)在第一個(gè)位置的字符,即把第一個(gè)字符和后面的所有字符交換,然后固定第一個(gè)字符,然后求后面所有字符的排列。這個(gè)時(shí)候，仍把后面的字符分成兩個(gè)部分,后面字符的第一個(gè)字符，和這個(gè)字符之后所有的字符,讓這個(gè)字符和它后面的字符依次交換。如下所示：我們可以看出這是很典型的遞歸的思想。本題很明顯需要使用回溯算法解決的問(wèn)題，解決一個(gè)回溯問(wèn)題，實(shí)際上就是一個(gè)決策樹(shù)的遍歷過(guò)程。（探索與回溯法）是一種選優(yōu)搜索法，又稱(chēng)為試探法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。 但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿(mǎn)足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱(chēng)為"回溯點(diǎn)"。具體代碼如下所示： */

? ? ? ? ? ? ? ? ??

void permutation(char* pStr) {if(NULL == pStr)return;permutation(pStr,pStr); }// pStr 指向整個(gè)字符串的第一個(gè)字符, pBegin 指向當(dāng)前我們做排列操作的第一個(gè)字符。 // 在每一次遞歸的時(shí)候,我們從 pBegin 向后掃描一個(gè)字符，在交換完 pBegin 和 pChar // 之后,我們對(duì) pBegin 后面的字符串做遞歸的操作。 void permutation(char* pStr,char* pBegin) {if(*pBegin == '\0')printf("%s\n",pStr);else {for(char* pChar = pBegin; *pChar != '\0'; ++pChar){// 交換char pTemp = *pChar;*pChar = *pBegin;*pBegin = pTemp;// 遞歸permutation(pStr,pBegin+1);// 回退pTemp = *pChar;*pChar = *pBegin;*pBegin = pTemp;}} }/* 6、數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字。題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。例如,輸入一個(gè)長(zhǎng)度為 9 的數(shù)組 { 1,2,3,2,2,2,5,4,2 },由于數(shù)字 2在數(shù)組中出現(xiàn) 5 次,超過(guò)數(shù)組的一半,因此輸出 2。法一：先排序，再取中間數(shù)字，時(shí)間復(fù)雜度 O(nlogn),不是最好的。法二：可借鑒快排的 partition 的思想，時(shí)間復(fù)雜度O(n)。法三：下面代碼使用的方法，充分利用數(shù)組的特點(diǎn)，進(jìn)行降維，取最重要的特征，次數(shù)最大。思路如下：由于該數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組的一半,也就是它出現(xiàn)的次數(shù)比起其他所有的數(shù)字出現(xiàn)次數(shù)還要多。因此，我們可以考慮在遍歷數(shù)組的時(shí)候,保存兩個(gè)值,一個(gè)是數(shù)組中的一個(gè)值,一個(gè)是該數(shù)字出現(xiàn)的次數(shù)。當(dāng)我們遍歷下一個(gè)數(shù)字的時(shí)候，如果下一個(gè)數(shù)字與之前保存的數(shù)字相同，則次數(shù)加 1,如果不同,則次數(shù)減去 1。如果次數(shù)為 0,我們需要保存下一個(gè)數(shù)字,并且把次數(shù)置為 1。由于要找的數(shù)字比起其他數(shù)字出現(xiàn)次數(shù)總和還多。故它一定是最后一次把次數(shù)置為 1,的數(shù)字。此外，還應(yīng)該檢查一些異常輸入，比如，輸入數(shù)組是否為NULL (checkInvalidArray),以及輸入數(shù)組中，最高頻率的數(shù)字出現(xiàn)次數(shù),是否超過(guò)一半以上(checkMoreThanHalf)等,代碼如下： */ int moreThanHalfNumber(int* numbers,int length) {if(checkInvalidArray(numbers,length))return 0;int result = numbers[0];int times = 1;for(int i=1; i< length;++i){if(times == 0){result = numbers[i];times = 1;}if(numbers[i] == result)++ times;else -- times;}if (!checkMoreThanHalf(numbers,length,result))return 0;return result; }// 檢查異常輸入 bool g_inputInvalid = false;bool checkInvalidArray(int* numbers,int length) {g_inputInvalid = false;if(numbers == NULL || length <= 0)g_inputInvalid = true;return g_inputInvalid; }bool checkMoreThanHalf(int* numbers,int length,int number) {int times = 0;for(int i=0; i < length; i++){if(numbers[i] == number)++ times;}bool isMoreThanHalf = true;if( times * 2 <= length){g_inputInvalid = true;isMoreThanHalf = false;} return isMoreThanHalf; }/* 7、連續(xù)字?jǐn)?shù)組的最大和，題目：輸入一個(gè)整形數(shù)組，數(shù)組里面既有正數(shù)也有負(fù)數(shù)。數(shù)組中的一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)字?jǐn)?shù)組,求所有字?jǐn)?shù)組的和的最大值，要求時(shí)間復(fù)雜度為O(n)。例如輸入：{1,-2,3,10,-4,7,2,-5}, 的和最大字?jǐn)?shù)組為{3,10,-4,7,2,-5},該字?jǐn)?shù)組的和為 18。如果列舉它所有的字?jǐn)?shù)組,共有 n(n+1) /2 個(gè)字?jǐn)?shù)組。計(jì)算出所有的字?jǐn)?shù)組的和，也需要O(n2)的時(shí)間。法一：我們可以嘗試著分析數(shù)組的規(guī)律,當(dāng)開(kāi)始累加到出現(xiàn)負(fù)數(shù),則說(shuō)明該拋棄前面所累加的和了,但是我們還需要存儲(chǔ)上一次最大的和,如果下一次添加,比累加的大，則需要更新最大和，下圖是分析過(guò)程。此外,我們還需要考慮無(wú)效輸入,比如輸入的數(shù)組參數(shù)為空指針,數(shù)組長(zhǎng)度小于等于 0 等情況。此時(shí),我們讓函數(shù)返回什么數(shù)字,如果返回0,怎么區(qū)分是最大和為0,還是無(wú)效輸入,為此我們定義了一個(gè)全局變量來(lái)標(biāo)記是否無(wú)效。代碼如下： */

? ??

bool g_InvalidInput = false;int FindGreatestSumOfSubArray(int* pData,int length) {if(NULL == pData || length <= 0){ // 區(qū)分輸出是無(wú)效輸入還是最大總和為 0 g_InvalidInput = true;return 0;}g_InvalidInput = false;int nCurSum = 0;int nGreatestSum = 0x80000000;for(int i=0; i<length; i++){if(nCurSum <= 0)nCurSum = pData[i];else nCurSum += pData[i];// 更新最大值if(nCurSum > nGreatestSum)nGreatestSum = nCurSum;}return nGreatestSum; }/* 8、把數(shù)組排成最小的數(shù)：輸入一個(gè)正整數(shù)數(shù)組,把數(shù)組中所有的數(shù)字拼成一個(gè)數(shù)，打印能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組 [3,32,321] 能打印出這 3 個(gè)數(shù)字能拼成的最小的數(shù)字為 321323。思路：法一：全排列求出數(shù)組中所有數(shù)字的全排列，然后把每個(gè)全排列拼起來(lái)，求出拼出來(lái)的數(shù)字的最小值。有 n！個(gè)組合,接下來(lái)看一種時(shí)間復(fù)雜度為O(nlogn)的算法。法二： 定義新的排序規(guī)則,* 如果兩個(gè)數(shù)字m,n拼接成mn和nm，如果 mn<nm，那么m應(yīng)該排在n的前面，我們定義此時(shí)m小于n，如果mn=nm，我們定義m等于n。* 可以考慮將數(shù)字轉(zhuǎn)成字符串，一來(lái)防止數(shù)字拼接時(shí)的溢出，二來(lái)字符串的拼接和比較容易實(shí)現(xiàn)。* 由于把數(shù)字 m和n 拼接起來(lái)得到mn和nm，它們的位數(shù)一定是相同的，因此比較它們的大小只需按照字符串大小的比較規(guī)則即可。* 代碼如下： */ const int g_maxNumberLength = 10;char* g_strCombine1 = new char[g_maxNumberLength *2 +1]; char* g_strCombine2 = new char[g_maxNumberLength *2 +1];void printMinNumber(int* numbers,int length) {if(NULL == numbers || length <= 0)return;// 先將數(shù)組里面的數(shù)字變成字符串char** strNumbers = (char**)(new int[length]);for(int i=0; i<length; ++i){strNumbers[i] = new char[g_maxNumberLength +1];sprintf(strNumbers[i],"%d",numbers[i]);}qsort(strNumbers,length,sizeof(char*),compare);// 打印出來(lái)for(int i=0; i<length; ++i) printf("%s",strNumbers[i]);printf("\n");// 釋放內(nèi)存for(int i=0; i<length; ++i)delete strNumbers[i];delete strNumbers; }// 重載 qsort 的 compare 方法 int compare(const void* strNumber1,const void* strNumber2) {strcpy(g_strCombine1,*(const char**)strNumber1);strcat(g_strCombine1,*(const char**)strNumber2);strcpy(g_strCombine2,*(const char**)strNumber2);strcat(g_strCombine2,*(const char**)strNumber1);return strcmp(g_strCombine1,g_strCombine2); } /* 9、數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。題目：統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。例如輸入排序數(shù)組,{1,2,3,3,3,3,4,5} 和數(shù)字 3,由于 3 在這個(gè)數(shù)組中出現(xiàn)了 4 次,因此輸出 4。方法一：暴力遍歷,時(shí)間復(fù)雜度為 O(n),法二：由于已經(jīng)排好序了，故相同的數(shù)必定在一起，分別找到該數(shù)第一次出現(xiàn)的地方和最后一次出現(xiàn)的地方。分別使用二分查找算法，則總的時(shí)間復(fù)雜度,任然是 O(logn),我們先來(lái)分析如何找到第一個(gè) K,二分查找總是先拿數(shù)組的中間數(shù)字和 k 做比較,如果中間數(shù)字比 K 大,則 k 只能出現(xiàn)在前半段,只需要去前半段查找即可,反之,去后半段查找。如果中間數(shù)字與 k 相等呢。我們先來(lái)判斷這個(gè)數(shù)字是不是第一個(gè) k,如果位于中間位置前一個(gè)不是K,則中間位置就是第一個(gè)k,如果中間位置的前一個(gè)位置也是k,則說(shuō)明第一個(gè)k,在數(shù)組的前半段,下一輪我們?nèi)匀恍枰跀?shù)組的前半段查找，同理，查找最后一個(gè)k,最后就可以確定 k 的個(gè)數(shù)了。代碼如下： */ // 找數(shù)組中的第一個(gè) K int GetFirstK(int* data,int length,int k,int start,int end) {if(start > end)return -1;int MiddleIndex = (start + end) / 2;int MiddleData = data[MiddleIndex];if(MiddleData == k){if((MiddleIndex > 0 && data[MiddleIndex - 1] !=k) || MiddleIndex == 0)return MinddleIndex;else end = MiddleIndex - 1;}else if (MiddleData > k)end = MiddleIndex - 1;elsestart = MinddleIndex + 1;return GetFirstK(data,length,k,start,end); }// 找數(shù)組中的最后一個(gè) K int GetLastK(int* data,int length,int k,int start,int end) {if(start > end)return -1;int MiddleIndex = (start + end) / 2;int MiddleData = data[MiddleIndex];if(MiddleData == k){if((MiddleIndex < length -1 && data[MiddleIndex + 1] !=k) || MiddleIndex == length -1)return MinddleIndex;else start = MiddleIndex + 1;}else if (MiddleData < k)start = MinddleIndex + 1;else end = MiddleIndex - 1;return GetLastK(data,length,k,start,end); }// 得出 k 出現(xiàn)的次數(shù) int GetNumberOfK(int* data,int length,int k) {int number = 0;if(data != NULL && length >0){int first = GetFirstK(data,length,k,0,length-1);int last = GetLastK(data,length,k,0,length-1);if(first > -1 && last > -1)number = last - first + 1;}return number; }/* 10、數(shù)組中值出現(xiàn)一次的數(shù)字,題目：一個(gè)整數(shù)數(shù)組中除了兩個(gè)數(shù)字外，其他數(shù)字均出現(xiàn)了兩次，寫(xiě)出程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是O(n),空間復(fù)雜度為O(1)，如果是出現(xiàn)一次的數(shù)字只有一個(gè)，則我們可以用異或去解決，如下,所示,如果有兩個(gè),我們可以選擇將原數(shù)組分成兩個(gè)數(shù)組,讓出現(xiàn)一次的兩個(gè)數(shù)分別在兩個(gè)數(shù)組之中,然后就可以使用異或分別去解決了。 */ // 次數(shù)出現(xiàn)一次的只有一個(gè)數(shù) int FindAppearOnce(int arr[], int len) {int i = 0;int ret = 0;for(i = 0; i<len; i++){ret = arr[i]^ret;}return ret; }// 次數(shù)出現(xiàn)一次的數(shù)字有兩個(gè) void FindAppearOnce(int arr[], int len, int* pn1, int* pn2) {int num = 0;//記錄整組異或的結(jié)果，即兩個(gè)一次出現(xiàn)的數(shù)異或的結(jié)果int i = 0;int indexOf1 = 0; // indexOf! 即從右邊起第一個(gè)為 1 的 bit 位的位置for(i = 0; i<len; i++) //得出整組異或的結(jié)果，即兩個(gè)一次出現(xiàn)的數(shù)異或的結(jié)果{num = num^arr[i];} //找出異或結(jié)果中從右邊起第一個(gè)為1的bit位while(((num&1)!= 1) &&(indexOf1< 8 * sizeof(int))) {num = num>>1;++ indexOf1;}*pn1 = *pn2 = 0;for(i = 0; i<len ; i++)//將原數(shù)組分為兩組，分別求出每組中出現(xiàn)一次的數(shù)字{int k_bit = (arr[i]>>indexOf1) & 1; //arr[i]第k位的值if(k_bit == 1){*pn1 ^= arr[i]; // 異或}else{*pn2 ^= arr[i]; // 異或}} }/* 11、不用加減乘除做加法。題目：寫(xiě)一個(gè)函數(shù)，求兩個(gè)整數(shù)之和,要求在函數(shù)體中不能使用 加減乘除 四則運(yùn)算符。首先看十進(jìn)制是如何做的： 5+7=12，三步走 第一步：相加各位的值，不算進(jìn)位，得到2。 第二步：計(jì)算進(jìn)位值，得到10. 如果這一步的進(jìn)位值為0，那么第一步得到的值就是最終結(jié)果。 第三步：重復(fù)上述兩步，只是相加的值變成上述兩步的得到的結(jié)果2和10，得到12。同樣我們可以用三步走的方式計(jì)算二進(jìn)制值相加： 5-101，7-111 第一步：相加各位的值，不算進(jìn)位，得到010，二進(jìn)制每位相加就相當(dāng)于各位做異或操作，101^111。 第二步：計(jì)算進(jìn)位值，得到1010，相當(dāng)于各位做與操作得到101，再向左移一位得到1010，(101&111)<<1。 第三步重復(fù)上述兩步， 各位相加 010^1010=1000，進(jìn)位值為100=(010&1010)<<1。 繼續(xù)重復(fù)上述兩步： 1000^100 = 1100，進(jìn)位值為0，跳出循環(huán)，1100為最終結(jié)果。 */int Add(int num1, int num2) {while(num2!=0){int temp=num1^num2; // 各位相加的值num2=(num1&num2)<<1; // 進(jìn)位值num1=temp;}return num1; }/* 12、在字符串中找出第一個(gè)只出現(xiàn)一次的字符。如輸入 “abaccdeff", 則輸出 ‘b’.如果采用從頭掃描在和后面的字符對(duì)比查看是否有相同的字符，則時(shí)間復(fù)雜度為 O(n^2)。對(duì)于此類(lèi)問(wèn)題我們 可以采用借助哈希表的方式先遍歷統(tǒng)計(jì)，在查看統(tǒng)計(jì)數(shù)的方式，時(shí)間復(fù)雜度為 O(n). 方法如下所示： */char firstNotRepearChar(char *pStr) {if (NULL == pStr)return '\0';const int hashTableLen = 256;unsigned int hashtable[hashTableLen];for (unsigned int i = 0; i < hashTableLen; i++)hashtable[i] = 0;char *pHashKey = pStr;while (*pHashKey != '\0')hashtable[*pHashKey++] ++;pHashKey = pStr;while (*pHashKey != '\0'){if (hashtable[*pHashKey] == 1)return *pHashKey;++ pHashKey;}return '\0'; }

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的面试算法基础及编程 第四弹 （字符串、数值类、或其他常见相关）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。