面试题 5：替换空格.md

试题链接：16. 替换空格 - AcWing题库

方法一：非原地替换

• 思路：创建一个新的字符串，遍历原字符串，遇到空格则向新字符串中添加字符串 %20 ，不是空格则复制。一个优化是可以预先得出空格的数量，以此来计算最终字符串的大小，进行内存预分配，可以节省动态扩容的开销。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    string replaceSpaces(string &str) {
        int n = str.size();
        int space_cnt = 0;
        for (char ch : str) {
            if (isspace(ch)) space_cnt++;
        }
        
        string ans;
        ans.reserve(n + 2 * space_cnt);
        
        for (char ch : str) {
            if (!isspace(ch)) ans.push_back(ch);
            else {
                ans.push_back('%');
                ans.push_back('2');
                ans.push_back('0');
            }
        }
        
        return ans;
    }
};

方法二：双指针（原地算法）

• 思路：预计算需要增加的长度，扩容原数组后，从后往前遍历原字符串，一个指向原字符串中最后一个字符，一个指向扩容后的最后一个位置，遇到空格就倒序添加字符串 %20
• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
public:
    string replaceSpaces(string &str) {
        int n = str.size();
        int space_cnt = 0;
        for (char ch : str) {
            if (isspace(ch)) space_cnt++;
        }
        
        str.resize(n + 2 * space_cnt);
        
        int i = n - 1, j = str.size() - 1;
        
        while (i >= 0) {
            if (isspace(str[i])) {
                str[j--] = '0';
                str[j--] = '2';
                str[j--] = '%';
            } else {
                str[j--] = str[i];
            }
            i--;
        }
        
        return str;
    }
};

举一反三：合并两个有序数组

试题链接：https://leetcode.cn/problems/merge-sorted-array/description/

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, k = n + m - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        while (i >= 0) nums1[k--] = nums1[i--];
        while (j >= 0) nums1[k--] = nums2[j--];
    }
};