參考鏈接

• letcode官網題目地址

題目要求：

• 請實現一個函數，把字符串 s 中的每個空格替換成"%20"。

示例 1：

輸入：s = "We are happy."
輸出："We%20are%20happy."

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解決思路

時間復雜度為O(n^2)

• 如果在先前的字符串上進行替換，就很有可能會覆蓋修改該字符串后面的內存。如果創建新的字符串，并在新的字符串上進行替換，需要分配足夠多的內存，
• 時間復雜度為O(n^2)的解法，不足以拿到offer：最low的做法是從頭開始掃描字符串，遇到空格就進行替換，將1個空格替換成%20，那么會造成數據的多次移動，時間復雜度很高，但是占據的內存很小，在原有的字符串上進行更改。

時間復雜度是O(n)

• 每次替換空格，長度會增加2位，因此替換之后的長度等于先前的長度加上2*空格的數目
• 設置兩個指針，因為從0開始讀取字符串，old指針第一個指針指向先前舊的字符串的長度 - 1 的位置，第二個指針new指向新的字符串 的長度減一的位置。
• 如果old指針指向的位置是空格的話，new指針移動三次，添加”%20“，然后old移動一次
• 如果old指針指向的位置不是空格的話，new和old指針分別移動一次，實現數據的拷貝
• 相對于第一種方式，減少了對相同數據的拷貝次數

代碼

    std::string replaceSpace(std::string s) {int old_length = s.length();if (old_length == 0){return s;}int count = 0;for (int i = 0; i < old_length; ++i) {if (s[i] == ' '){count++;}}int new_length = old_length + 2*count - 1;int original_index = old_length - 1;int new_index = new_length;s += std::string(2*count,' ');while (original_index >= 0 && new_index > original_index){if (s[original_index] == ' '){s[new_index--] = '0';s[new_index--] = '2';s[new_index--] = '%';} else{s[new_index--] = s[original_index];}--original_index;}return s;}

?