前言

哈喽，大家好，我是一条。

糊涂算法，难得糊涂

坚持真的好难，但胜利的喜悦更加诱人！

Question

剑指 Offer 05. 替换空格

难度：简单

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

示例 1：

输入：s = “We are happy.”

输出：“We%20are%20happy.”

限制：

0 <= s 的长度 <= 10000

Solution

这道题还是比较简单的，但简单题就要高要求，如果想把这道题目做到极致，时间和空间上都要做到最优。

抛开正常的循环遍历，数组问题离不开双指针或者快慢指针。

一起回忆「有序数组合并」这道题。

首先减少空间，可以扩充数组到每个空格替换成"%20"之后的大小。

再考虑时间选择从后向前替换，避免每次添加元素都要将添加元素之后的所有元素向后移动。

Code

所有leetcode代码已同步至github

欢迎star

/**
 * @author yitiaoIT
 */
public static String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (" ".equals(String.valueOf(str.charAt(i)))){
                sb.append("%20");
            } else {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }

Result

复杂度分析

• 时间复杂度：O(N)

????寻宝

⭐今天是坚持刷题更文的第28/100天

⭐各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力

⭐更多算法题欢迎关注专栏《leetcode》

为了回馈各位粉丝，礼尚往来，给大家准备了一条多年积累下来的优质资源，包括 学习视频、面试资料、珍藏电子书等

大家可以先自己找一下获取方式，寻宝游戏现在开始。

如果实在找不到可以评论区留言或私信我领取，不过一定要先关注哦！不然无法发私信！