题目
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”
限制：
0 <= s 的长度 <= 10000
分析
本题唯一难点就是如何将一个字符替换为三个，这样就会加长字符串。
暴力解法
直接双层循环，时间复杂度O（n^2） 空间复杂度为O(1)
C
#include<stdio.h> #include<string.h> void ReplaceBlank(char string[], int length) { int i = 0; int count = 0;//计算多少个空格 for(i = 0; string[i] != '\0'; i++)//从前向后遍历 { if (string[i] == ' ')//找到空格 { count++; for (int j = length - 1 + count * 2; j > i + 2; j--)//找临界条件 { string[j] = string[j - 2]; } string[i++] = '%'; string[i++] = '2'; string[i++] = '0'; } } string[i] = '\0'; } int main() { char s[30] = "We are happy."; ReplaceBlank(s, 13); printf("%s\n", s); return 0; }
遍历添加
稍微分析以下代码，我们可以一次遍历找到总的空格数，然后一次全部替换。时间复杂度为O(n),空间复杂度为O(1)
C
void ReplaceBlank(char string[], int length) { int count = 0; for (int i = 0; i < length; i++)//计算空格数量 { if (string[i] == ' ') { count++; } } //从\0开始省去了最后添加\0 int end = length + count * 2; int start = length; while (start > 0 || start != end) { if (string[start] == ' ') { string[end--] = '0'; string[end--] = '2'; string[end--] = '%'; start--; } else { string[end--] = string[start--]; } } } int main() { char s[30] = "We are happy."; ReplaceBlank(s, 13); printf("%s\n", s); return 0; }
原地修改
在C++中，string字符串时可变的。
见链接 http://www.cplusplus.com/reference/string/string/resize/
翻译：
调整字符串大小
将字符串的大小调整为n个字符的长度。 如果n小于当前字符串长度，则当前值将缩短为它的前n个字符，并删除第n个字符之外的字符。 如果n大于当前字符串的长度，则通过在结尾处插入任意数量的字符来扩展当前内容，以达到n的大小。如果指定了c，则新元素被初始化为c的副本，否则，它们是值初始化的字符（空字符）。
那么就好办多了 ，代码如下，思想和上面类型。时间复杂度O(n),空间复杂度O(1)。
C++
#include<iostream> using namespace std; class Solution { public: string ReplaceBlank(string str) { int count = 0; int len = str.size(); for (char c : str) // 统计空格数量 { if (c == ' ') { count++; } } str.resize(len + 2 * count);//重置字符串长度 //遍历修改 int end = str.size() - 1; int start = len - 1; while(start < end && start >= 0) { if (str[start] == ' ') { str[end--] = '0'; str[end--] = '2'; str[end--] = '%'; start--; } else { str[end--] = str[start--]; } } return str; } }; int main() { Solution s; string str = "We are happy."; string ret = s.ReplaceBlank(str); cout << ret << endl; return 0; }
相关题目
有俩个排序的数组A1和A2，内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数，把A2中的所有数字插入A1中，并且所有的数字是排序的。
思想
我们首先想到的是从前往后，那么就会出现多次移动同一个数字的情况。所以，我们从后向前插。这样就能减少移动的次数，从而提高效率。
#include<stdio.h> void MergeArray(int arr1[], int arr2[], int len1, int len2) { int end = len1 + len2 - 1; //尾插的指针 int i = len1 - 1; //记录arr1数组的位置 int j = len2 - 1; //记录arr2数组的位置 while (i >=0 && j >= 0 && end >= 0) { if (arr1[i] > arr2[j]) //arr1大 { arr1[end--] = arr1[i--]; } else //arr2大 { arr1[end--] = arr2[j--]; } } while(i >= 0) //arr2提前完了 { arr1[end--] = arr1[i--]; } while (j >= 0) //arr1提前完了 { arr1[end--] = arr2[j--]; } } void print(int arr[], int len) { for (int i = 0; i < len && arr[i] != 0; i++) { printf("%d ", arr[i]); } } int main() { int arr1[20] = { 1,3,7,9,11 }; int arr2[5] = { 2,4,6,8,10 }; int len1 = 5; int len2 = 5; MergeArray(arr1, arr2, len1, len2); print(arr1, len1 + len2); return 0; }
本章完
