题目:
请实现一个函数,把字符串 s 中的每个空格替换成"%20"。
示例:
输入:s = "We are happy." 输出:"We%20are%20happy."
思路:
直接的思路就是:使用一个新的对象,复制 str,复制的过程对其判断,是空格则替换,否则直接复制。
JAVA中Stringbuffer有append( )方法: 而Stringbuffer是动态字符串数组,append( )是往动态字符串数组添加,跟“xxxx”+“yyyy”相当‘+’号。
//方式一:直接思路
class Solution { public String replaceSpace(String s) { if (s == null) { return null; } char[] ch=s.toCharArray(); StringBuilder sb = new StringBuilder(); for(int i=0;i<ch.length;i++){ if(ch[i]==(' ')){ sb.append("%20"); }else{ sb.append(ch[i]); } } return sb.toString(); } }
双指针法:
首先扩充数组到每个空格替换成"%20"之后的大小。
然后从后向前替换空格,过程如下:
i指向新长度的末尾,j指向旧长度的末尾。
为什么要从后向前填充,从前向后填充不行么? 从前向后填充就是O(n^2)的算法了,因为每次添加元素都要将添加元素之后的所有元素向后移动。
这么做有两个好处:
- 不用申请新数组。
- 从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题。
//方式二:双指针法class Solution {
public String replaceSpace(String s) { if(s == null || s.length() == 0){ return 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); }
}
标签:offer05,right,String,chars,力扣,length,str,空格 From: https://www.cnblogs.com/cjhtxdy/p/16980651.html