【剑指offer】Java实现之替换空格
题目描述:请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,初始字符串为We Are Happy.经过替换之后的字符串为We%20Are%20Happy。
视频题解地址:https://www.bilibili.com/video/bv1nT4y1g771
思路:
方法一、直接调用Java的replace函数
public class Solution { public String replaceSpace(StringBuffer str) { return str.toString().replace(" ", "%20"); } }
方法二、新建一个字符串
换句话说就是,遍历旧字符串,将非空格的直接加到新字符串尾部,当遇到空格时,将‘%20’加到新字符串尾部。虽然很通俗易懂,但是显然新建一个字符串占用了空间,可以更加优化。
import java.util.*; public class Solution { public String replaceSpace(StringBuffer str) { StringBuilder sb = new StringBuilder(); for(int i=0;i<str.length();i++){ if(str.charAt(i)== ' '){ sb.append("%20"); }else{ sb.append(c); } } return sb.toString(); } }
方法三、双指针法
需要将上面的字符串转化为下面的字符串。
首先观察两者的区别,新字符串比旧字符串多2个字符,换句话说,旧字符串每多一个空格,新字符串多一组‘%20’也就是新字符串多两个字符。那么依此规则使用Java的setLength规则扩大旧字符串。例子中将10扩大成12.然后设置两个指针。
此时旧字符串经过扩充近似可以看成:
指针1从旧字符串最后一位10开始,指针2从新字符串最后一位12开始,遍历直到指针1走到头。
当指针1指向的是非空格,例如‘d’,此时指针1指向位置10,字符‘d’,将‘d’直接插入到指针2的指向,也就是12.再将新旧指针同步左移一位。以此类推,直到指针1指向空格,此时指针1指向位置5,新指针指向位置7。
也就是这个样子,这个时候在7的位置上填充‘0’,6的位置上填充‘2’,5的位置上填充‘%’就可以直接处理掉空格。接着再继续指针移动直到0的位置,遍历完成。输出。
import java.util.*; public class Solution { public String replaceSpace(StringBuffer str) { int num=0; for (int i=0;i<str.length();i++){ if (str.charAt(i)==' '){ num++; } } int oldStringLength=str.length(); int newStringLength=oldStringLength+2*num; str.setLength(newStringLength); //扩大字符串 int indexNew = newStringLength-1; int indexOld = oldStringLength-1; //建立指针1和指针2 while (indexOld>=0&&indexNew>indexOld){ if (str.charAt(indexOld)==' '){ //当指向的为空格,同时插入02% str.setCharAt(indexNew--,'0'); str.setCharAt(indexNew--,'2'); str.setCharAt(indexNew--,'%'); } else { str.setCharAt(indexNew--,str.charAt(indexOld)); //指向不为空格则插入指向的字符 } indexOld--; //循环结束不要忘记移动指针1 } return str.toString(); } }
以上