剑指offer 题目4:替换空格

深碍√TFBOYSˉ_ 2022-11-30 05:56 173阅读 0赞

**转载请注明作者和出处：** [http://blog.csdn.net/john\_bh/][http_blog.csdn.net_john_bh]  
**github地址：[https://github.com/johnbhlm/SwordFingerOffer][https_github.com_johnbhlm_SwordFingerOffer]**

### 文章目录 ###

*   *  1. 题目
     *  2. 解题思路
     *   *  2.1 思路1
         *  2.2 思路2
     *  3. python 实现
     *  4. C++ 实现
     *   *  4.1 思路2 实现代码
         *  4.2 官方代码

完整代码，已经同步到github：[https://github.com/johnbhlm/SwordFingerOffer][https_github.com_johnbhlm_SwordFingerOffer]，欢迎关注，欢迎star~

## 1. 题目 ##

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

## 2. 解题思路 ##

### 2.1 思路1 ###

最简单最直观的方法就是从头到尾遍历，每一次碰到空格字符的时候做替换，但是因为是把1个字符替换成3个字符，我们必须把空格后面所有的字符都后移两个字节，否则，就有两个字符被覆盖，所以时间复杂度为O(n^2)。  
例如，从头到尾把 “We Are Happy.” 中的每一个空格替换成“%20”。这里用一个表格来表示字符串，表格中的每个格子表示一个字符，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG5fYmg_size_16_color_FFFFFF_t_70_pic_center]  
替换第一个空格，这个字符串变成了图2.3(b)中的内容，表格中灰色背景的格子表示需要做移动的区域。接着替换第二个空格，替换后的内容如图2.3©所示。同时，注意到深灰色背景标注的“happy”部分移动了两个。

假设字符串长度是  n n n 。对每个空格字符，需要移动后面  O ( n ) O(n) O(n) 个字符，因此对含有  O ( n ) O(n) O(n)个空格字符的字符串而言总的时间效率是  O ( n 2 ) O(n^2) O(n2)

### 2.2 思路2 ###

时间复杂度为  O ( n ) O(n) O(n) 的方法。

1.  先遍历一次字符串，这样就可以统计出字符串空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。以"We are happy"为例，“We are happy"这个字符串的长度为14（包括结尾符号”\\n"），里面有两个空格，因此替换之后字符串的长度是18。
2.  从`字符串的尾部开始复制和替换`。  
    首先准备两个指针， P 1 P\_1 P1和 P 2 P\_2 P2， P 1 P\_1 P1指向原始字符串的末尾，而 P 2 P\_2 P2指向替换之后的字符串的末尾，如图2.4(a)所示；  
    接下来向前移动指针 P 1 P\_1 P1，逐个把它指向的字符复制到 P 2 P\_2 P2指向的位置，直到碰到第一个空格为止，如图2.4(b)所示；  
    碰到第一个空格之后，把 P 1 P\_1 P1向前移动1格，在 P 2 P\_2 P2之前插入字符串"%20"。由于"%20"的长度为3，同时也要把 P 2 P\_2 P2向前移动3格，如图2.4(c )所示；  
    接着向前复制，知道碰到第二个空格（如图2.4(d)所示），把  P 1 P\_1 P1向前移动1格，并把  P 2 P\_2 P2向前移动3格，插入“%20”，如图2.4(e)所示；  
     **P 1 P\_1 P1 和 P 2 P\_2 P2 指向同一个位置，表明所有空格都一起替换完毕**。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG5fYmg_size_16_color_FFFFFF_t_70_pic_center 1]  
    所有的字符只复制（移动）一次，因此这个思路的时间复杂度是 O ( n ) O(n) O(n)，比第一个思路快。

## 3. python 实现 ##

# -*- coding:utf-8 -*-
    class Solution:
        def replaceSpace(self, s):
            s_new= []
            for i in s:
                if i != ' ':
                    s_new.append(i)
                else:
                    s_new.append('%20')
            return ''.join(s_new)

# -*- coding:utf-8 -*-
    class Solution:
        def replaceSpace(self, s):
            s_new=s.split(' ')
            return '%20'.join(s_new)

# -*- coding:utf-8 -*-
    class Solution:
        def replaceSpace(self, s):
            return s.replace(' ', '%20')

# -*- coding:utf-8 -*-
    class Solution:
        def replaceSpace(self, s):
            s_len=len(s)
            spaceCnt=0
    
            for i in s:
                if i==' ':
                    spaceCnt+=1
    
            s_newLen=(spaceCnt<<1)+s_len
            s_new=[' ']*s_newLen
            j=0
            for i in range(s_len):
                if s[i]==' ':
                    s_new[j]='%'
                    s_new[j+1] = '2'
                    s_new[j+2] = '0'
                    j+=3
                else:
                    s_new[j]=s[i]
                    j+=1
            return ''.join(s_new)

## 4. C++ 实现 ##

### 4.1 思路2 实现代码 ###

#include <iostream>
    
    using namespace std;
    
    /*
    请实现一个函数，将一个字符串中的每个空格替换成“%20”。
    例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
    */
    class Solution {
        
    public:
    	void replaceSpace(char *str, int length) {
        
    		if (str == NULL && length <= 0) {
        
    			return;
    		}
    
    		int spaceCnt = 0; //空格数
    		int strOrgLen = 0; //字符串实际长度
    
    		while (str[strOrgLen] != '\0') {
        			
    			if (str[strOrgLen] == ' ') {
        
    				spaceCnt++;
    			}
    			strOrgLen++;
    		}
    
    		int strNewLen = (spaceCnt << 1) + strOrgLen; //strNewLen 为把空格替换成'%20'之后的长度
    		int p1 = strOrgLen; //原始数组最后一个元素的下标
    		int p2 = strNewLen; //新数组最后一个元素的下标
    		
    		while (p1 >= 0 && p2 > p1) {
        
    			if (str[p1] == ' ') {
        
    				str[p2--] = '0';
    				str[p2--] = '2';
    				str[p2--] = '%';
    			}
    			else {
        
    				str[p2--] = str[p1];
    			}
    			p1--;
    		}
    	}
    };
    
    int main()
    {
        
    	char str[14] = "We Are Happy.";
    	cout << "original string:" << endl;
    	cout << str << endl;
    
    	Solution solu;
    	solu.replaceSpace(str, 14);
    	cout << "replace string:" << endl;
    	cout << str << endl;
    
    	return 0;
    }

### 4.2 官方代码 ###

官方代码：[ReplaceSpaces.cpp][]

/*******************************************************************
    Copyright(c) 2016, Harry He
    All rights reserved.
    Distributed under the BSD license.
    (See accompanying file LICENSE.txt at
    https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
    *******************************************************************/
    
    //==================================================================
    // 《剑指Offer——名企面试官精讲典型编程题》代码
    // 作者：何海涛
    //==================================================================
    
    // 面试题5：替换空格
    // 题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，
    // 则输出“We%20are%20happy.”。
    
    #include <cstdio>
    #include <cstring>
    
    /*length 为字符数组str的总容量，大于或等于字符串str的实际长度*/
    void ReplaceBlank(char str[], int length)
    {
        
        if(str == nullptr && length <= 0)
            return;
    
        /*originalLength 为字符串str的实际长度*/
        int originalLength = 0;
        int numberOfBlank = 0;
        int i = 0;
        while(str[i] != '\0')
        {
        
            ++ originalLength;
    
            if(str[i] == ' ')
                ++ numberOfBlank;
    
            ++ i;
        }
    
        /*newLength 为把空格替换成'%20'之后的长度*/
        int newLength = originalLength + numberOfBlank * 2;
        if(newLength > length)
            return;
    
        int indexOfOriginal = originalLength;
        int indexOfNew = newLength;
        while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
        {
        
            if(str[indexOfOriginal] == ' ')
            {
        
                str[indexOfNew --] = '0';
                str[indexOfNew --] = '2';
                str[indexOfNew --] = '%';
            }
            else
            {
        
                str[indexOfNew --] = str[indexOfOriginal];
            }
    
            -- indexOfOriginal;
        }
    }
    
    // ====================测试代码====================
    void Test(char* testName, char str[], int length, char expected[])
    {
        
        if(testName != nullptr)
            printf("%s begins: ", testName);
    
        ReplaceBlank(str, length);
    
        if(expected == nullptr && str == nullptr)
            printf("passed.\n");
        else if(expected == nullptr && str != nullptr)
            printf("failed.\n");
        else if(strcmp(str, expected) == 0)
            printf("passed.\n");
        else
            printf("failed.\n");
    }
    
    // 空格在句子中间
    void Test1()
    {
        
        const int length = 100;
    
        char str[length] = "hello world";
        Test("Test1", str, length, "hello%20world");
    }
    
    // 空格在句子开头
    void Test2()
    {
        
        const int length = 100;
    
        char str[length] = " helloworld";
        Test("Test2", str, length, "%20helloworld");
    }
    
    // 空格在句子末尾
    void Test3()
    {
        
        const int length = 100;
    
        char str[length] = "helloworld ";
        Test("Test3", str, length, "helloworld%20");
    }
    
    // 连续有两个空格
    void Test4()
    {
        
        const int length = 100;
    
        char str[length] = "hello  world";
        Test("Test4", str, length, "hello%20%20world");
    }
    
    // 传入nullptr
    void Test5()
    {
        
        Test("Test5", nullptr, 0, nullptr);
    }
    
    // 传入内容为空的字符串
    void Test6()
    {
        
        const int length = 100;
    
        char str[length] = "";
        Test("Test6", str, length, "");
    }
    
    //传入内容为一个空格的字符串
    void Test7()
    {
        
        const int length = 100;
    
        char str[length] = " ";
        Test("Test7", str, length, "%20");
    }
    
    // 传入的字符串没有空格
    void Test8()
    {
        
        const int length = 100;
    
        char str[length] = "helloworld";
        Test("Test8", str, length, "helloworld");
    }
    
    // 传入的字符串全是空格
    void Test9()
    {
        
        const int length = 100;
    
        char str[length] = "   ";
        Test("Test9", str, length, "%20%20%20");
    }
    
    int main(int argc, char* argv[])
    {
        
        Test1();
        Test2();
        Test3();
        Test4();
        Test5();
        Test6();
        Test7();
        Test8();
        Test9();
    
        return 0;
    }

[http_blog.csdn.net_john_bh]: http://blog.csdn.net/john_bh/
[https_github.com_johnbhlm_SwordFingerOffer]: https://github.com/johnbhlm/SwordFingerOffer
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG5fYmg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/cdd521842d4f4b96846b4c6640ad3575.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG5fYmg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/2f9aaacb81114e769e14ba5f4df889be.png
[ReplaceSpaces.cpp]: https://github.com/johnbhlm/CodingInterviewChinese2/blob/master/05_ReplaceSpaces/ReplaceSpaces.cpp