劍指offer之把字符串里面空格替換成百分之20[時(shí)間復(fù)雜度是O(n)]

1 問題

把字符串里面空格替換成20%

要求：時(shí)間復(fù)雜度是O(n)

 
2 思路

比如我們字符串a(chǎn)b cd ef,我們先計(jì)算出新字符串需要的長度，我們分別搞2個(gè)指針指向老的和新的字符串的尾巴，然后老字符串從'\0'開始拷貝數(shù)據(jù)到新的字符串尾巴,同時(shí)兩個(gè)指針同時(shí)左移，如果老的字符串遇到了空格，那么老的字符串指針往左邊移動(dòng)一格，然后新的字符串指針依然向左移動(dòng)并且填充'0' 、'2'、 '%'，直到老的字符串指針到最左邊或者老的字符串指針和新的字符串指針相等就不循環(huán)了

 
3 代碼實(shí)現(xiàn)

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    int insert(char *a, int len, char *replace, int replaceLen)
    {
        //先得到多少個(gè)空格
        char *p = a;
        //先得到多少個(gè)空格
        int count = 0;
        int oldLen = 0;
        while (*p != '\0')
        {
            if (*p == ' ')
            {
                ++count;
            }
            ++p;
            ++oldLen;
        }
        //計(jì)算新的字符串長度
        int newLen = oldLen + count * (replaceLen - 1);
        printf("oldLen is %d\n", oldLen);
        printf("newLen is %d\n", newLen);
        if (newLen > len)
        {
            printf("數(shù)組的長度不夠\n");
            return -1;
        }
        //循環(huán)條件也就是需要移動(dòng)的數(shù)組下標(biāo)最左邊
        while (oldLen >= 0) //或加上while(oldLen >=0 && oldLen < newLen)
        {
            //if (*(a + oldLen) != ' ')和下面的if等價(jià)
            if (a[oldLen] != ' ')
            {
                //這里用這個(gè)和下面的等價(jià)
                /**
                *(a + newLen) = *(a + oldLen);
                newLen--;
                oldLen--;
                **/
                a[newLen--] = a[oldLen--];
            }
            else
            {
                oldLen--;
                a[newLen--] = '0';
                a[newLen--] = '2';
                a[newLen--] = '%';
            }
        }
        return 0;
    }
     
    
    int main()
    {
        //這里給出數(shù)組的大小長度不能小于空格替換%20后
        //新的數(shù)組的長度,我們后面的函數(shù)需要做出處理
        char a[20] ="ab cd ef";
        int len = sizeof(a);
        int result = insert(a, len, "%20", 3);
        if (result != 0)
        {
            printf("insert fail\n");
            return -1;
        }
        printf("chars is %s\n", a);
        printf("區(qū)分strlen和sizeof\n");
       
        char c[] = "abc";
        char d[3] = "abc";
        char e[4] = "abc";
        char *p = "abc";
        printf("sizeof(c) is %d\n", sizeof(c));
        printf("sizeof(d) is %d\n", sizeof(d));
        printf("sizeof(e) is %d\n", sizeof(e));
        printf("sizeof(p) is %d\n", sizeof(p));
     
        printf("strlen(c) is %d\n", strlen(c));
        printf("strlen(d) is %d\n", strlen(d));
        printf("strlen(e) is %d\n", strlen(e));
        printf("strlen(p) is %d\n", strlen(p));
     
        return 0;   
    }

 
4 運(yùn)行結(jié)果

    oldLen is 8
    newLen is 12
    chars is ab%20cd%20ef
    區(qū)分strlen和sizeof
    sizeof(c) is 4
    sizeof(d) is 3
    sizeof(e) is 4
    sizeof(p) is 8
    strlen(c) is 3
    strlen(d) is 3
    strlen(e) is 3
    strlen(p) is 3

 



 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)