剑指Offer---面试题5---替换空格.md

目录

• 1、介绍
• 2、题解
• 3、变形题

剑指Offer-面试题5---替换空格

1、介绍

实现一个函数，把字符串中每个空格替换成"%20"。例如，输入"Hello World"，输出"Hello%20World"。

2、题解

不推荐的方法1：从前向后遍历，每次碰到空格替换并把后面所有字符向后移动。
时间复杂度：O(n^2)

推荐的方法2：从后向前遍历，详细过程看代码。
时间复杂度：O(n)

///arr是要修改的字符串，length表示这个字符串的最大长度
void ChangeSpace(char arr[], int length)
{
    if (arr == nullptr || length<=0)
    {
        return;
    }

    int i = 0;
    //字符串实际长度
    int arrLength = 0;
    //空格个数
    int spaceNum = 0;
    while (arr[i] != '\0')
    {
        if (arr[i] == ' ')
            spaceNum++;

        arrLength++;
        i++;
    }

    //新字符串需要的长度
    int newArrLength = arrLength + spaceNum * 2;
    if (newArrLength > length)
        return;

    //从后向前依次比较替换
    while (arrLength >= 0 && newArrLength > arrLength)
    {
        if (arr[arrLength] == ' ')
        {
            arr[newArrLength] = '0';
            arr[newArrLength-1] = '2';
            arr[newArrLength-2] = '%';
            arrLength--;
            newArrLength-=3;
        }
        else {
            arr[newArrLength] = arr[arrLength];
            arrLength--;
            newArrLength--;
        }
    }
}

3、变形题

有两个排序的数组a1和a2，内存在a1的末尾有足够多的空余时间容纳a2。实现一个函数，把a2中的所有数字插入a2中，并且所有的数字是排序的。

///需要排序的两个数组和其各自的长度
void Sort(int arr1[], int arr2[], int length1, int length2)
{
    if (arr1 == nullptr || arr2 == nullptr || length2<=0)
    {
        return;
    }

    //总长度
    int length = length1 + length2;

    //从后向前依次比较
    while (length1 >= 0 && length > length1)
    {
        if (arr1[length1-1] >= arr2[length2-1])
        {
            arr1[length - 1] = arr1[length1 - 1];
            length--;
            length1--;
        }
        else {
            arr1[length - 1] = arr2[length2 - 1];
            length--;
            length2--;
        }
    }
}