FilesExpand file tree

 master

/

offer05.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

35 lines (34 loc) · 1.72 KB

 master

/

offer05.java

Copy path

Top

File metadata and controls

• Code
• Blame

35 lines (34 loc) · 1.72 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

/**

* [05] 替换空格

*

* 题目：将给定字符串 s 中的每个空格都替换成 "%20"。

*

* 思路：1。初始化一个 StringBuilder，遍历字符串，当前字符为 ' ' 时，向 StringBuilder 中加入 "%20"；当前字符不为 ' ' 时，

* 向 StringBuilder 中加入该字符。

*

* 其实原题想考察的是：给定一个包含空格的字符数组，将数组中的空格替换为 "%20" 三个字符，要求额外空间复杂度为 O(1)。

* （假设数组中有足够的的空间来保存新添加的字符）

* 因为要求额外空间复杂度为 O(1)，所以就在原字符数组上进行操作：

* 2。从前往后遍历字符串，每次遇到空格时需要先将空格后的字符全部后移两个字节，再将空格替换为 "%20"。时间复杂度：O(n ^ 2)。

* 3。令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要

* 令 P2 指向的位置依次填充 "20%" （注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容

* 时，不会影响到 P1 遍历原来字符串的内容。这样就避免多次重复移动字符。

*/

class Solution {

/**

* 时间复杂度：O(n)

* 空间复杂度：O(n)

*/

public String replaceSpace1(String s) {

StringBuilder sb = new StringBuilder();

for (char chr : s.toCharArray()) {

if (chr == ' ') {

// replace all ' ' with "%20".

sb.append("%20");

} else {

sb.append(chr);

}

}

return sb.toString();

}

}