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

秦怀杂货店

发布于 2022-02-15 15:03:56

3790

文章被收录于专栏：技术杂货店技术杂货店

💻 剑指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)。

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，Redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-13，如有侵权请联系 cloudcommunity@tencent.com 删除

https