【剑指offer】-替换空格-02/67

1. 题目描述:

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

2. 题目分析

  1. 从前向后记录空格(count) 数目,从后向前替换空格
  2. 重点:从后向前替换的时候的技巧 例如:“we are lucky”
    1
    2
    3
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    w e a r e l u c k y
    w e % 2 0 a r e % 2 0 l u c k y
    可以得知count=2;。 所以在替换的时7-11的字母要向后移动count×2个位置,3-5字母要向后移动(count-1)×2个位置。

3. 代码(c++)

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
class Solution {
public:
void replaceSpace(char *str,int length)
{
int count = 0;
for(int i = 0; i < length; i++)
{
if(str[i] == ' ')
{
count++;
}
}
for(int i = length - 1; i >= 0; i--)
{
if(str[i] == ' ')
{
str[2 * count + i] = '0';
str[2 * count + i - 1] = '2';
str[2 * count + i - 2] = '%';
count--;
}
else
{
str[2 * count + i] = str[i];
}
}
}
};

//运行时间:8ms
//占用内存:508k

总结

  1. 分析问题一定要全面分析,充分考虑复杂度和时间的问题。
  2. 用JAVA语言来写这道题,还有太多的不足,等学完JAVA在来补上这道题。
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信