5.【剑指offer】替换空格

逃离我推掉我的手 2024-03-26 13:50 76阅读 0赞

[题目][Link 1]

### 思路一： ###

1.  先遍历字符串，每遍历到一个空格就在原字符串末尾增加2个空格；

1.  将扩容后的字符串转成char数组，然后对其内容进行重写；

1.  采用双指针，一个指针i的起始位置在未扩容前长度的末尾，另一个指针j则处于扩容后长度的末尾；

1.  结束条件为：指针j移动到char数组的头部；

1.  时间复杂度：O（N）

import java.util.*;
    
    
    public class Solution {
    
        public String replaceSpace (String s) {
            if(s.length() == 0) return "";
            //扩容
            StringBuilder sb = new StringBuilder(s);
            for(char ch : s.toCharArray()){
                if(ch == ' ') sb.append("  ");
            }
            //覆盖原字符
            char[] arr = sb.toString().toCharArray();
            for(int i = s.length() - 1, j = arr.length - 1; j >= 0; i--,j--){
                if(arr[i] != ' ') arr[j] = arr[i];
                else {
                    arr[j--] = '0';
                    arr[j--] = '2';
                    arr[j] = '%';
                }
            }
            return new String(arr);
        }
    }

### 思路二：（超级简单） ###

1.  使用StringBuilder来进行扩容和拼接；

1.  时间复杂度O（N）；

注：字符串对象通过“+”的字符串拼接方式，实际上是通过 StringBuilder 调用 append() 方法实现的，拼接完成之后调用 toString() 得到一个 String 对象 。

import java.util.*;
    
    
    public class Solution {
    
        public String replaceSpace (String s) {
            // 直接用StringBuilder
            StringBuilder sb  = new StringBuilder();
            for(char ch : s.toCharArray()){
                if(ch == ' ') sb.append("%20");
                else sb.append(ch);
            }
            return sb.toString();
        }
    }

[Link 1]: https://www.nowcoder.com/practice/0e26e5551f2b489b9f58bc83aa4b6c68?tpId=265&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D265&difficulty=&judgeStatus=&tags=&title=&gioEnter=menu