剑指Offer--05替换空格&&58左旋字符串-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指Offer--05替换空格&&58左旋字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、剑指Offer–05.替换空格

题目是这样的

剑指Offer--05替换空格&&58左旋字符串

意思是将字符串s中的空格替换为字符串"%20",如果只是替换一个字符还好，可以在原数组直接替换，但是是将空格替换为字符串，所以再在原数组上替换，原数组原内容会被覆盖，且长度大小不够，所以此时要动态开辟一个字符数组，这个数组开多大？考虑最坏的情况，也就是全为空格的情况，此时也就是原数组长度的三倍，但是开出来的数组大小只是存储的有效字符，还没有算上’\0’,所以还要多开一个空间。有人可以算数字符串s中空格字符的个数(count)，然后新开数组空间大小为原数组s大小，加上count*2再加一

char* replaceSpace(char* s){
  int count = 0;
  for(int i = 0;i<strlen(s);i++)
  {
    if(s[i]==' ')
    {
      count++;
    }
  }
  
  int len = strlen(s);
  char*ret = (char*)malloc(sizeof(char)*(len+(count*2)+1));
  //char*ret = (char*)malloc(sizeof(char)*(len*3+1));可以这样写

  int j = 0;
  for(int i = 0;i<strlen(s);i++)
  {
    if(s[i] ==' ')
    {
        ret[j++] = '%';
        ret[j++] = '2';
        ret[j++] =  '0'; 
    }

    else
    {
      ret[j++] = s[i];
    }
  }
  ret[j] = '\0';//这里为何要对其数组ret数组有效字符数据的下一位赋值为字符'\0'
  //因为返回首地址，找的是'\0\结束，如果不赋值为'\0',有可能字符数组要过了很久才是'\0,这样会造成越界访问，所以要对其赋值为'\0'。
  return ret;
}

二、剑指Offer–58.左旋字符串

题目是这样的
剑指Offer--05替换空格&&58左旋字符串
其实就是给定一个变量n，将n之前的字符旋转到后面，然后将n之后的字符旋转到前面

朴素旋转
可以用最朴素的方法，先将第一个字符存下，然后依次将后面的字符往前覆盖，循环n次，但是这样时间复杂度为O(n^2)
剑指Offer--05替换空格&&58左旋字符串

char* reverseLeftWords(char* s, int n) {
    int len = strlen(s);
    int k = n % len;//当要旋转的长度大于了数组的长度，这样就会造成重复操作，
    //所以对其取模，保证最多旋转字符串长度，保证不会不会重复


    while (k--)
    {
        char tmp = s[0];
        int i = 0;
        for (i = 0; i < strlen(s) - 1; i++)
        {

            s[i] = s[i + 1];
        }
        s[i] = tmp;
    }

    return s;
}

这样时间复杂度为O(n^2),会显示超时，有些用例不能过

分区间旋转

先将0~n-1的字符逆置，然后将[n,len-1]之间的字符逆置，再最后总体逆置

void reserve(char* str, int left, int right)
{
    while (left < right)
    {
        char tmp = str[left];
        str[left] = str[right];
        str[right] = tmp;

        left++;
        right--;
    }
}

char* reverseLeftWords(char* s, int n) {

    int len = strlen(s);
    int k = n % len;

    reserve(s, 0, k - 1);
    reserve(s, k, len - 1);
    reserve(s, 0, len - 1);

    return s;
}

再开一个数组，将n之后的字符串赋值赋值给新数组从0开始依次赋值，然后再将0~n-1之间的字符依次尾插到新数组后面

剑指Offer--05替换空格&&58左旋字符串
只是这样需要新开一个数组，时间复杂度为O(n),空间复杂度为O(n)文章来源地址https://www.toymoban.com/news/detail-458130.html

char* reverseLeftWords(char* s, int n) {
    int len = strlen(s);
    int k = n % len;

    char* ret = (char*)malloc(sizeof(char) * len);
    int i = 0;
    int j = k;
    for (i = 0, j = k; j < len; j++, i++)
    {
        ret[i] = s[j];
    }
    int m = 0;
    while (m < k)
    {
        ret[i++] = s[m++];
    }

    for (int x = 0; x < len; x++)
    {
        s[x] = ret[x];
    }

    return s;
}