@TOC

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

输入： s = “We are happy.”
输出： “We%20are%20happy.”

限制：

$0 <= s 的长度 <= 10000$

解法一：暴力解

使用StringBuilder，遇到字符就直接append到sb,遇到空格就append "%20"。

class Solution {
    public String replaceSpace(String s) {
        //返回空串，返回null提交失败，因为题目没有指明，故无伤大雅
        if(s == null || s.length() == 0) return ""; 
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == ' '){
                sb.append("%20");//StringBuilder的append方法的参数可以是字符，也可以是字符串
            }else{
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

解法二：从后往前填充思想

这种从后往前填充的思想，很多题中都有用到，应该好好掌握，灵活运用。

① 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），所以当遍历到一个空格时，需要在尾部填充两个任意字符。

② 令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。

③ 当 P2 遇到 P1 时（P2 <= P1），或者遍历结束（P1 < 0），退出。

class Solution {
    public String replaceSpace(String s) {
        //返回空串，返回null提交失败，题目没有指明，故无伤大雅
         if(s == null || s.length() == 0) return ""; 
         StringBuilder sb = new StringBuilder(s);
         for(int i = 0; i < s.length(); i++){
             if(s.charAt(i) == ' '){
                 sb.append("  ");//在尾部添加两个空格
             }
         }

         int p1 = s.length() - 1;
         int p2 = sb.length() - 1;
         while(p2 > p1 && p1 >= 0){
             char c = sb.charAt(p1--);
             if(c == ' '){
                 sb.setCharAt(p2--,'0');
                 sb.setCharAt(p2--,'2');
                 sb.setCharAt(p2--,'%');
             }else{
                 sb.setCharAt(p2--,c);
             }
         }
         return sb.toString();
    }
}

第五题的扩展题：合并两个有序数组 LeetCode 88

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入： nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出： [1,2,2,3,5,6]

示例 2：

输入： nums1 = [1], m = 1, nums2 = [], n = 0
输出： [1]

提示：

$nums1.length == m + n$
$nums2.length == n$
$0 <= m, n <= 200$
$1 <= m + n <= 200$
$-10^9 <= nums1[i], nums2[i] <= 10^9$

解法一：暴力解

暴力解法，将nums2的所有元素添加到nums1中，然后用快速排序即可。时间复杂度为$O((m+n)log(m+n))$。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i = m,j = 0;i<nums1.length && j<n;i++,j++){
            nums1[i] = nums2[j];
        }
        Arrays.sort(nums1);
    }
}

解法二：从后往前填充思想

用从后往前的双指针方法，类似上面第五题的解法。从尾到头比较两个数组中的数字，并将较大的数字复制到nums1中的合适位置。时间复杂度为遍历一次数组$O(m+n)$

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //由于两个数组是有序的，故我们可以从后往前的慢慢补全nums1，时间O(n),空间O(1)
        int p1 = m-1;//nums1的尾位置
        int p2 = n-1;//nums2的尾位置
        int p = m+n-1;//拼接后的尾位置
        while(p1>=0 && p2>=0){//有至少一个数组遍历完时退出循环
            nums1[p--] = nums1[p1] < nums2[p2] ? nums2[p2--] :nums1[p1--];
        }
        //不管是p1<0了(nums2中有剩余），还是p2<0了（nums1中有剩余），都可用下式
        System.arraycopy(nums2,0,nums1,0,p2+1);
    }
}

举一反三

在合并两个数组 （包括字符串）时，如果从前往后复制每个数字（或字符）则需要移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率，且算法代码看着更清晰易懂。