字符串算法：等宽替换,以少换多,以多换少

categories:

C语言

题目一：写一个函数将字符串中的字符移到字符串的前部分，前面的非字符后移，但不能改变非*字符的先后顺序，例如autotoc处理后为****autoc

算法一：

C代码:

//算法1:从后往前复制非*的字符,然后前面的补*
int Move1(char *str)//O(n),O(n)
{
    char *arr =  (char *)malloc(strlen(str)+1);
    assert(arr != NULL);
    int i = strlen(str);//str下标
    int j = i;//arr下标
    int rtval;//返回值
    for(;i>=0;i--)//从后往前复制非*的字符
    {
        if(str[i] != '*')//非*,需要复制到arr中
        {
            arr[j--] = str[i];
        }
    }
    rtval = strlen(str)-j-1;
    //前面补*
    while(j >= 0)
    {
        arr[j--] = '*';
    }
    strcpy(str,arr);//将数据复制到str中
    free(arr);

    return rtval;
}

算法一时间复杂度O(n),空间复杂度0(n)

算法二：

在这里插入图片描述
C代码

//算法2,利用两个下标i,j分别到字符串的末尾,通过i从后往前遍历,如果i的数据为非*则将数据复制到j处,
//j往前,如果没有复制则j不动,最后将前面的部分补充为*
int Move(char *str)//O(n),O(1)
{
    int i = strlen(str);//遍历的下标
    int j = i;//数据移动后的下标
    int rtval;//返回值

    for(;i>=0;i--)//利用i从后往前遍历字符串
    {
        if(str[i] != '*')
        {
            str[j--] = str[i];
        }
    }
    rtval = strlen(str)-j-1;

    while(j >= 0)
    {
        str[j--] = '*';
    }
    return rtval;
}

算法二未使用辅助空间，时间复杂度O(n),空间复杂度度O(1)

题目二：将字符串中的空格替换为%20,例如"a b c"->"a%20b%20%20c"

算法一：
在这里插入图片描述
算法二：

算法二C代码

void replace(char *str1)
{
    //先统计空格数量，利用i定位到字符串末尾，j=i+空格数*2；
    //再从后往前替换，遇到非空格的直接放，遇到空格替换为0 2 %, j往前移动3个
    int i, j;
    int blank = 0;//空格数量
    for (i = 0; str1[i] != '\0'; i++)
    {
        if (str1[i] == ' ')
            blank++;
    }
    for (j = i + blank * 2; i >= 0; i--)//i是旧串末尾，j是新串的末尾
    {
        if (str1[i] != ' ')
        {
            str1[j] = str1[i];
            j--;            
        }
        else//是空格
        {
            str1[j--] = '0';
            str1[j--] = '2';
            str1[j--] = '%';
        }
    }
}

题目三：删除字符串中多余的空格,多个空格只保留一个."a b c d"->"a b c d"

在这里插入图片描述
算法：i不断后移判断，若当前是空格，接下来也是空格，则不赋值，i后移，j不动
若当前是空格接下来不是空格或者当前是非空格则把i赋值给j，i后移，j后移

C代码

void del(char *str2)
{
    //i不断后移判断，若当前是空格，接下来也是空格，则不赋值，i后移，j不动
    //若当前是空格接下来不是空格或者当前是非空格则把i赋值给j，i后移，j后移
    int i, j;
    for (i = 0, j = 0; str2[i] != '\0'; i++)
    {
        if (str2[i] == ' '&&str2[i + 1] == ' ')
        {
            ;
        }
        else
        {
            str2[j] = str2[i];
            j++;
        }
    }
    str2[j] = '\0';
}