0 题目来源

力扣《程序员面试金典》

1 本题涉及到的知识点

字符串、双指针、substr

substr

  • 功能为从原来的字符串中截取一部分字符串。
  • string类型的一个方法
  • 使用方式为：**str.substr(begin,num);**begin处填写开始的子串位置，num处填写截取子串的长度。如**str.substr(2,4);**表示截取str的2~5位。

    2 题目描述

    URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）

提示：

  • 字符串长度在 [0, 500000] 范围内。

    3 输入与输出格式

    无，力扣略了

    4 样例

    示例 1：
    输入：”Mr John Smith “, 13
    输出：”Mr%20John%20Smith”
    示例 2：
    输入：” “, 5
    输出：”%20%20%20%20%20”

    5 分析与代码

    按照本题的题意，需要在原来字符串的基础上进行修改，因此我们可以采用从后向前遍历字符串的方法。
    首先对字符串进行遍历，得出其中拥有的需要转化的空格数目。
    然后使用两个指针，一个指向我们计算出的转化后的字符串的末尾，另一个指向未转化的字符串末尾。
    之后用一个while循环对字符串进行转化，两个指针同步移动，如果遇到空格，则将接下来的3个位置转化为02%，以此类推，直到两个指针移到字符串的头。
    在这个过程中，我那么可以判断两个指针是否相等，如果相等，则说明剩下的部分没有空格，不需要转化了，此时就需要推出循环，通过这种方式可以减小时间复杂度。
    最后，要注意使用substr对返回的字符传进行控制，由于给定的字符串的空间最后可能还有剩余（空格），因此，我们需要去掉这些空格，使用substr取出给定字符串的子串，从而得到最终的答案。
    代码：
    1. class Solution {
    2. public:
    3.   string replaceSpaces(string S, int length) {
    4.       int SpaceNum = 0;
    5.       for (int i = 0; i < length; i++)
    6.       {
    7.           if (S[i] == ' ')
    8.               SpaceNum++;
    9.       }
    10.       int p1 = length - 1;//字母指针
    11.       int p2 = length + SpaceNum * 2 - 1;//字符串指针
    12.       while (p2 >= 0 && p1 >= 0)
    13.       {
    14.           if (S[p1] != ' ')
    15.               S[p2--] = S[p1];
    16.           else
    17.           {
    18.               S[p2--] = '0';
    19.               S[p2--] = '2';
    20.               S[p2--] = '%';
    21.           }
    22.           p1--;
    23.           if (p1 == p2)
    24.               break;
    25.       }
    26.       return S=S.substr(0,length + SpaceNum * 2);
    27.   }
    28. };