leetcode【剑指 Offer 05. 替换空格—简单】541.替换空格

2021/10/22 6:11:23

编程Tag： 字符串替换空格指针 right LeetCode 05 chars

本文主要是介绍leetcode【剑指 Offer 05. 替换空格—简单】541.替换空格，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

前言
题目
题解
- NO1：双指针（最优解，O(n)）
参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为字符串专题。

题目

题目来源leetcode

leetcode地址：剑指 Offer 05. 替换空格，难度：简单。

题目描述(摘自leetcode)：

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

示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
 
限制：
0 <= s 的长度 <= 10000

本地调试代码：

class Solution {

    public String replaceSpace(String s) {
        ...
    }

    public static void main(String[] args) {
        System.out.println(new Solution().replaceSpace("We are happy."));
    }

}

题解

NO1：双指针（最优解，O(n)）

思路：对于字符串中空格=>"%20"，由一个字符填充为3个字符，普通解法就是遍历一遍的过程中遇到空白字符串先将后面的统一移动两个接着进行填充，该思路时间复杂度为O(n²)；

所以这里我们使用双指针的方案，首先遍历一遍字符串确定其中有多少个空格对原始字符串进行扩容，紧接着来定义两个指针，一个指针指向原始字符串最后一个位置，另一个指针指向扩展之后最后一个位置，每次移动两个指针同时向前移动，若是左指针碰到空格，右指针进行%、0、2向前以前填充前进两步；若不是空格，右指针指向的值改为左指针当前指向的值，根据此规则不断重复即可！时间复杂度为O(n)。这里我直接引用代码随想录—题目：剑指Offer 05.替换空格中的思路图，十分推荐该博主的算法指南，十分清晰

代码：

public String replaceSpace(String s) {
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}