面試題 4 ：替換空格

2019-11-06 06:02:44

字體：大中小

來源：轉載

供稿：網友

題目：請實現一個函數，把字符串中的每個空格替換成”%20”。例如：輸入”we are happy.”，則輸出”we%20are%20happy.”

思路分析：我們比較替換之前與替換之后的字符串長度，很明顯，字符串長度增加了4，所以，第一點，將”we are happy.”用一個字符指針指向肯定不可行，那么就應該將其放入一個數組中。其次我們就應該考慮如何輸出想要的結果。 1.題目沒有給出要求，那么有一種笨的辦法就是將字符串逐漸賦值到另外一個數組中，遇到空格就給新的數組插入”%20”，這樣也可以輸出結果。這樣的時間復雜度和空間復雜度都是O(N)。但是想一想，這是一道面試題啊，怎么可能如此簡單。 2.利用兩個數組的做法顯然被pass掉了，那只能在一個數組內操作了。既然數組長度擴大了，我們可以想成每個空格后邊的字符都向后移動了一定的位置，空出來的位置剛好夠插入”%20”。我們畫張圖來解釋一下：這里寫圖片描述

上邊這種方法的時間復雜度還不是讓人最滿意的，應該有一種最好的辦法既能讓時間復雜度降低還能達到預期目標。如果我們每次能將移動的字符一次性放好位置，那樣就比較方便了。因此我么需要提前知道增加長度后數組的大小，那么我們就能給出兩個下標，一個指向新字符串的末尾，一個指向舊字符串的末尾，從后向前遍歷一邊，就能實現每次都將字符一次性放好位置。這里寫圖片描述時間復雜度分析：由于從后往前只需要遍歷一次數組，其時間復雜度為O(N) 代碼：

#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <string.h>//時間復雜度：O(N)void Replace(char* str,int old) { char* start = str; int blacknum = 0; int newlen = 0; int PRev = 0; int last = 0; if ((str == NULL) || (old < 0)) { return ; } while (*start != '/0') { start++; if (*start == ' ') { blacknum++; //統計空格的個數 } } newlen = old+blacknum*2; //替換后新的字符串長度 prev = old; last = newlen; while (prev >= 0) { str[last--] = str[prev--]; if (str[prev] == ' ') { str[last--] = '0'; str[last--] = '2'; str[last--] = '%'; prev--; } }}

底下為測試代碼：

int main(){ char str[] = "we are happy"; int len = strlen(str); Replace(str,len); printf("%s/n",str); system("pause"); return 0;}

上一篇：第二次修改狀態機源碼

下一篇：CodeForces - 149D Coloring Brackets 詳細題解（遞歸區間DP+dfs染色，好題）