剑指Offer05~替换字符串中的空格

「爱情、让人受尽委屈。」 2022-05-14 13:41 222阅读 0赞

## 题目描述 ##

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为 We Are  
Happy. 则经过替换之后的字符串为 We%20Are%20Happy。

### 解题思路 ###

（剑指offer上面的分析）看到这个题目，我们首先应该想到的是原来一个空格字符，替换之后变成”%’、2’和’0这3个字符，因此字符串会变长。如果是在原来的字符串.上做替换，那么就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串\_上做替换，那么我们可以自已分配足够多的内存。由于有两种不同的解决方案，我们应该向面试官问清楚，让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上做替换，并且保证输入的字符串后面有足够多的空余内存。  
       先遍历字符串，填充字符。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。  
        令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。

public class ReplaceSpace { 
    
        public static String replaceString(StringBuffer str) {
            // 先遍历整个字符串，检查字符串中有几个空格，每遍历到一个空格在字符串后面填充两个空间（两个空格）
            // We Are Happy
            int oldlen = str.length();// 原长度12
            for (int i = 0; i < oldlen; i++) {
                if (str.charAt(i) == ' ') {
                    str.append(" ");// 末尾添加两个空格
                }
            }
            // 定义两个“指针” p1指向字符串原来的末尾位置 p2 指向现在的末尾位置 p1和p2 从后往前遍历
            int p1 = oldlen - 1;
            int p2 = str.length() - 1;
            while (p1 >= 0 && p2 > p1) {
                // 当前遍历到的字符
                char c = str.charAt(p1--);
                if (c == ' ') {
       // 依次填充02% 逆序
                    str.setCharAt(p2--, '0');
                    str.setCharAt(p2--, '2');
                    str.setCharAt(p2--, '%');
                } else {
                    str.setCharAt(p2--, c);
                }
            }
            return str.toString();
        }
    
        // 测试
        public static void main(String[] args) {
            StringBuffer str = new StringBuffer("We Are Happy");
            System.out.println("原字符串：" + str);
            System.out.println("输出转换后的字符串：" + replaceString(str));
        }
    }