程序员面试金典 - 面试题 01.03. URL化

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例 1:

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

示例 2:

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

提示：

字符串长度在[0, 500000]范围内。

题目思考

1. 如何做到原地修改？

解决方案

思路

• 不难想到利用各种语言的 replace 或 split/join 来实现；或者新建一个字符串，遇到空格就追加%20。但这些做法都没有利用题目中的真实长度和字符数组，不是原地操作
• 题目中说明了字符数组有足够空间存放新字符，所以我们可以先计算得出新字符串的总长度，然后维护一个当前下标，从右向左遍历，这样就保证了是原地操作，且不会覆盖到之前存在且尚未处理的字符

复杂度

• 时间复杂度 O(N): 需要遍历字符串一遍
• 空间复杂度 O(1): 除了字符数组外只使用了几个变量

代码

class Solution:
    def replaceSpaces(self, S: str, length: int) -> str:
        # 不使用内置函数, 模拟C语言的字符数组处理
        # 注意length是原来字符串的有效长度
        # 计算空格数目, 分配好新数组长度
        newlen = length
        blank = 0
        for c in S[:length]:
            if c == ' ':
                blank += 1
        newlen += blank * 2
        # res是模拟的字符数组
        res = [''] * newlen
        i = newlen - 1
        # 从右向左遍历
        for c in S[:length][::-1]:
            if c == ' ':
                res[i] = '0'
                res[i - 1] = '2'
                res[i - 2] = '%'
                i -= 3
            else:
                res[i] = c
                i -= 1
        return ''.join(res)

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊