k_eckel：http://www./blog/k_eckel & http://k-eckel.cnblogs.com
這是網(wǎng)絡(luò)流傳的Microsoft的面試題目之一：“編寫反轉(zhuǎn)字符串的程序，要求優(yōu)化速度、優(yōu)化空間”。因?yàn)樽罱恢焙芏嚓P(guān)注算法方面的實(shí)踐和研究，因此對(duì)這個(gè)問題進(jìn)行了一些思考，給出了5種實(shí)現(xiàn)方法（有兩種解法相關(guān)性比較大）。
解法一：第一次看到這題目，想到最簡(jiǎn)單、最直覺的解法就是：遍歷字符串，將第一個(gè)字符和最后一個(gè)交換，第二個(gè)和倒數(shù)第二個(gè)交換，依次循環(huán)，即可，于是有了第一個(gè)解法：
|
char* strrev1(const char* str) { int len = strlen(str); char* tmp = new char[len + 1]; strcpy(tmp,str); for (int i = 0; i < len/2; ++i) { char c = tmp[i]; tmp[i] = tmp[len – i - 1]; tmp[len – i - 1] = c; } return tmp; } |
這里是通過數(shù)組的下標(biāo)方式訪問字符串的字符，實(shí)際上用指針直接操作即可。解法二正是基于此，實(shí)現(xiàn)代碼為：
|
char* strrev2(const char* str) { char* tmp = new char[strlen(str) + 1]; strcpy(tmp,str); char* ret = tmp; char* p = tmp + strlen(str) - 1; while (p > tmp) { char t = *tmp; *tmp = *p; *p = t; --p; ++tmp; } return ret; } |
顯然上面的兩個(gè)解法中沒有考慮時(shí)間和空間的優(yōu)化，一個(gè)典型的優(yōu)化策略就是兩個(gè)字符交換的算法優(yōu)化，我們可以完全不使用任何外部變量即完成兩個(gè)字符（或者整數(shù)）的交換，這也是一個(gè)很經(jīng)典的面試題目。特別是一些嵌入式硬件相關(guān)編程中經(jīng)常要考慮寄存器的使用，因此經(jīng)常有不使用任何第三個(gè)寄存器即完成兩個(gè)寄存器數(shù)據(jù)的交換的題目。一般有兩個(gè)解法，對(duì)應(yīng)這里的解法三和解法四。
解法三的實(shí)現(xiàn)代碼為：
|
char* strrev3(const char* str) { char* tmp = new char[strlen(str) + 1]; strcpy(tmp,str); char* ret = tmp; char* p = tmp + strlen(str) - 1; while (p > tmp) { *p ^= *tmp; *tmp ^= *p; *p ^= *tmp; --p; ++tmp; } return ret; } |
解法四的實(shí)現(xiàn)代碼為：
|
char* strrev4(const char* str) { char* tmp = new char[strlen(str) + 1]; strcpy(tmp,str); char* ret = tmp; char* p = tmp + strlen(str) - 1; while (p > tmp) { *p = *p + *tmp; *tmp = *p - *tmp; *p = *p - *tmp; --p; ++tmp; } return ret; } |
實(shí)際上我們還可以通過遞歸的思想來解決這個(gè)問題，思想很簡(jiǎn)單：每次交換首尾兩個(gè)字符，中間部分則又變?yōu)楹驮瓉碜址瑯拥膯栴}，因此可以通過遞歸的思想來解決這個(gè)問題，對(duì)應(yīng)解法五的實(shí)現(xiàn)代碼為：
|
char* strrev5(/*const */char* str,int len) { if (len <= 1) return str; char t = *str; *str = *(str + len -1); *(str + len -1) = t; return (strrev5(str + 1,len - 2) - 1); } |
以下給出一個(gè)測(cè)試程序：
|
int main(int argc,char* argv[]) { char* str = "hello"; P(str); char* str2 = strrev1(str); P(str2); char* str3 = strrev2(str2); P(str3); char* str4 = strrev3(str3); P(str4); char* str5 = strrev4(str4); P(str5); char* str6 = strrev5(str5,strlen(str5)); P(str6);
return 0; } |
你就可以看到字符串"hello"和"olleh"交替輸出了。
說明：1）這里解法中沒有認(rèn)真考慮輸入字符串的合法性和特殊長(zhǎng)度（如NULL、一個(gè)字符等）字符串的處理；2）前4個(gè)算法不改變輸入字符串的值，解法五修改了輸入字符串。
