程序员面试金典【3 】-- URL化

• 💻   剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution
• 文档地址：https://damaer.github.io/CodeSolution/
• 仓库介绍：刷题仓库：CodeSolution
  
• 📒   编程知识库：https://github.com/Damaer/Coding
• 文档地址：https://damaer.github.io/Coding/#/

1题目

URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

示例 1：

输入："Mr John Smith    ", 13
输出："Mr%20John%20Smith"

示例 2：

输入："               ", 5
输出："%20%20%20%20%20"

2思路与解答

其实这道题，貌似做过，但是有点不太一样，这里多了一个字符串的真实的长度，所谓真实的长度，就是我们用到的真正长度，后面可能是多出来的空格，只是为了保证我们转成为数组之后，替换掉里面空格，也是有足够的空间放得下，比如：Mr John Smith
的有效的字符串其实是Mr John Smith
,后面有几个空格是为了把中间的两个空格替换成为 20%
的时候，能够放得下。

那么思路其实就是原来的字符串转成字符数组之后，空间就足够装得下:

从最后一个字符开始：

遇到空格的时候替换成三个字符：

中间重复过程省略，最后变成：

如果字符数组前面还有多余的空位，那直接截取掉就可以了，Java
代码如下：

public class Solution3 {
    public static void main(String[] args) {
        System.out.println(replaceSpaces("Mr John Smith    ", 13));
    }

    public static String replaceSpaces(String S, int length) {
        // 字符串的长度
        int size = S.length();
        char[] arrays = new char[size];
        // 这个其实是字符串有效长度最后的一个位置的索引
        int strIndex = length - 1;
        // 从数组后面开始往前面放
        int arraysIndex = size - 1;
        while (strIndex >= 0 && arraysIndex >= 0) {
            // 从有效的长度的最后一个字符开始
            char c = S.charAt(strIndex--);
            // 如果为空格，则替换成%20
            if (c == ' ') {
                arrays[arraysIndex--] = '0';
                arrays[arraysIndex--] = '2';
                arrays[arraysIndex--] = '%';
            } else {
                // 否则保持原字符串
                arrays[arraysIndex--] = c;
            }
        }
        // 结束的时候，可能前面还剩下空位置，截取掉
        return new String(arrays).substring(arraysIndex + 1);
    }
}

空间复杂度和时间复杂度均为 O(n)
。