一道简简单单的字节跳动算法面试题

亦凉 2023-02-17 11:28 228阅读 0赞

点击上方“**图解面试算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 **面试题05. 替换空格**，据官方统计，近半年在字节跳动算法面试中出现过 5 次。

题目链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

### 一、题目描述 ###

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

**示例 1：**

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

**限制：**

*  0 <= s 的长度 <= 10000

### 二、题目解析 ###

这题还是挺简单的。

遍历字符串中的每个字符，如果不是空格，直接赋值过去数组中；否则，赋值 **%20** 过去数组中。

最后，从数组中的前 `size` 个字符创建新字符串，并返回新字符串。

### 三、动画描述 ###

### 四、图片描述 ###

![format_png 1][]

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

![format_png 17][]

![format_png 18][]

![format_png 19][]

### 五、参考代码 ###

//来源：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/solution/mian-shi-ti-05-ti-huan-kong-ge-by-leetcode-solutio/
    class Solution {
        public String replaceSpace(String s) {
            //获取字符串 s 的长度 length
            int length = s.length();
            //创建字符数组 array，其长度为 length * 3
            char[] array = new char[length * 3];
            //初始化 size 为 0，size 表示替换后的字符串的长度
            int size = 0;
            //从左到右遍历字符串 s
            for (int i = 0; i < length; i++) {
                //获得 s 的当前字符 c
                char c = s.charAt(i);
                //如果字符 c 是空格，则令 array[size] = '%'，array[size + 1] = '2'，array[size + 2] = '0'，并将 size 的值加 3
                if (c == ' ') {
                    array[size++] = '%';
                    array[size++] = '2';
                    array[size++] = '0';
                } else {
                    array[size++] = c;
                }
            }
            //遍历结束之后，size 的值等于替换后的字符串的长度，从 array 的前 size 个字符创建新字符串，并返回新字符串
            String newStr = new String(array, 0, size);
            return newStr;
        }
    }

### 六、复杂度分析 ###

#### 时间复杂度 ####

时间复杂度为 O(n)，遍历字符串 `s` 一遍。

#### 空间复杂度 ####

空间复杂度：O(n)，额外创建字符数组，长度为 `s` 的长度的 3 倍。

### 七、相关标签 ###

*  字符串
 *  数组

\---

由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
    接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，感兴趣的小伙伴可以关注一下哈！

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vdzZwcnpadVBJRU5iMG01aWF3dXRJZjkwTjJVYjNkY1B1UDJLWEhKdmFSMUZ2MkZuaWNUdU95M0tjSHVJRUpiZDlsVXlPaWJlWHFXOHRFaG9KR0w5OHFPdy82NDA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkc2JmNkZXZWZGd2x2NlhxM2ljWmxqUENqYW83WGlhVUh0clhGOTFDaWJyeTJIbDh0M3ExeXh2WGd3LzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkdUJkQXJsZWFaQjZ6UWpCUnFiYVRlNXY4M2dzR0N4SnFpYkhKbEQwSzkyaWNsVm9hNjUxbFByUUEvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkN1BIWmxYNWliZmFpYXg3YU1rNHoxT0thTlVpYmtTcjVRYWZNQjZOMU9iS1dHMEZnNExHUVIwcWx3LzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkRnIyanhoalc3WmljdGlhbktzbmt6emlhV3hPWmVxSWNpY0JkWEFZNDMxWDM2SU84U05WczhhTlJaUS82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkZ3ZaOVdRMG9PeGliQ3RaSWhLZkJpYWliNmdEQ09xbTltOEtFS1hUcEowTGFVbmlhcXNid0hQM2dudy82NDA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkQVV4dHd5cEo1Wm1Nd3BlN0FwV0w2ZmJBWmljaDBkZEoyMldnVlMzcFYyN0MwNUdpYjkyVWQ4SmcvNjQw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkRmY0WklMaWF2WUNIc3FDN3FJSFdQaWNiRzd5a1JPeHFQaHdWb3dQWG5QQndQejA0a3NZMTlVaWFRLzY0MA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkRzBIMHBtT0NrTlBraWI1MlVpYzYya1lkNWliQXhjRTVVV3JlbXk0dnRjYnFkdzNkdGlieDB0ZTFOUS82NDA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkb1VpYmFCTDg0aWJ5SkFlMEtpYVZCalVabmlhU0JpYkx2dXlleDkyeWNCOWFMVm9uUFpwQXFyaGdjQVEvNjQw?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkdElHbTNpYjhQN1NxZGx0aWJ6N1h2UmliTDFwMnhDNFp2M29XdFgxaWJTN0hGZ21XZzhSbWRHWDYxdy82NDA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkWGFPTVdJd3FIZnJia0xqRk45Tmg0Y1ViMnFRZXE0RzVTbnhnczNlcU9TVmoyaWJJRUFwaWNkdkEvNjQw?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkV3B3a3hFbXFXSDhzSmNtd1lOVTBDaWFtYWlhZEg2QUVXbVpPZFZFajhBWG8wc2hhRHRnS28zSUEvNjQw?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkdkxwYk5CNWRaaWNXVFVWaEo0YU9wS3VTd0o3c0RpYmN1UE0zN0pQeGpUY3ZpYjBZYmZ4TGNDQTR3LzY0MA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkbWFxU0lJUEpramdtNHlpY2ljNlFXSUc5cmhBZHpEYURNYTRDN2R5Mm5pYjlpYWVNRzdYSWV1b1h4Zy82NDA?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkd1pyRTJsWHJUZkZFV3VYZDU5U2lib1FiVFlkTlREWXp3eVlIZGZyTnF2TU1pYkVwc2g2bFNpY1JBLzY0MA?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdka042bHpxWGdoMk9LRDlkbU1hTXh1ZXRZS1BZWm9yUXlXM0VCbUFzVkVnNmpFbDlTVDdJNjFBLzY0MA?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkRFBZWGJ2c043MFpiTk1FVGU2bnZQOW1PenpsTlRQOU5qeTJqdGhkVWlidUpKWXVrV0gwMnBpYlEvNjQw?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkeG9Hc3g5T0c3U01kZWJ2aFFtMFJyRVdvQ1BkTUNQbUNGd1EyTm1aek5QRXFDM2d6NGVNQVFRLzY0MA?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzT1I2NXVYaWJMaWNiT2Y2ZnJDaWFGbGdkbnRKQUltaWJWOTdCeVNEQ2VCV0oxaWNERWVBMnlORkdpYmljWkFkTWdxMWI3MGhZMVlkaGdUbjNXUS82NDA?x-oss-process=image/format,png