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

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

题目

请实现一个函数,把符串 s 中的每个空格替换成"%20"。

示例 1:

输入:s = “We are happy.”

输出:“We%20are%20happy.”

限制:

0 <= s 的长度 <= 10000

分析

本题唯一难点就是如何将一个字符替换为三个,这样就会加长字符串。

暴力解法

直接双层循环,时间复杂度O(n^2) 空间复杂度为O(1)


C

#include<stdio.h>
#include<string.h>
void ReplaceBlank(char string[], int length) 
{
  int i = 0;
  int count = 0;//计算多少个空格
  for(i = 0; string[i] != '\0'; i++)//从前向后遍历
  {
    if (string[i] == ' ')//找到空格
    {
      count++;
      for (int j = length - 1 + count * 2; j > i + 2; j--)//找临界条件
      {
        string[j] = string[j - 2];
      }
      string[i++] = '%';
      string[i++] = '2';
      string[i++] = '0';
    }
  }
  string[i] = '\0';
}
int main()
{
  char s[30] = "We are happy.";
  ReplaceBlank(s, 13);
  printf("%s\n", s);
  return 0;
}


遍历添加

稍微分析以下代码,我们可以一次遍历找到总的空格数,然后一次全部替换。时间复杂度为O(n),空间复杂度为O(1)

C

void ReplaceBlank(char string[], int length)
{
  int count = 0;
  for (int i = 0; i < length; i++)//计算空格数量
  {
    if (string[i] == ' ')
    {
      count++;
    }
  }
  //从\0开始省去了最后添加\0
  int end = length + count * 2;
  int start = length;
  while (start > 0 || start != end)
  {
    if (string[start] == ' ')
    {
      string[end--] = '0';
      string[end--] = '2';
      string[end--] = '%';
      start--;
    }
    else
    {
      string[end--] = string[start--];
    }
  }
}
int main()
{
  char s[30] = "We are happy.";
  ReplaceBlank(s, 13);
  printf("%s\n", s);
  return 0;
}


原地修改

在C++中,string字符串时可变的。

见链接 http://www.cplusplus.com/reference/string/string/resize/


翻译:

调整字符串大小

将字符串的大小调整为n个字符的长度。 如果n小于当前字符串长度,则当前值将缩短为它的前n个字符,并删除第n个字符之外的字符。 如果n大于当前字符串的长度,则通过在结尾处插入任意数量的字符来扩展当前内容,以达到n的大小。如果指定了c,则新元素被初始化为c的副本,否则,它们是值初始化的字符(空字符)。


那么就好办多了 ,代码如下,思想和上面类型。时间复杂度O(n),空间复杂度O(1)。


C++

#include<iostream>
using namespace std;
class Solution {
public:
    string ReplaceBlank(string str) {
        int count = 0;
        int len = str.size();
        for (char c : str) // 统计空格数量
        {
            if (c == ' ')
            {
                count++;
            }
        }
        str.resize(len + 2 * count);//重置字符串长度
        //遍历修改
        int end = str.size() - 1;
        int start = len - 1;
        while(start < end && start >= 0)
        {
            if (str[start] == ' ')
            {
                str[end--] = '0';
                str[end--] = '2';
                str[end--] = '%';
                start--;
            }
            else
            {
                str[end--] = str[start--];
            }
        }
        return str;
    }
};
int main()
{
    Solution s;
    string str = "We are happy.";
    string ret = s.ReplaceBlank(str);
    cout << ret << endl;
  return 0;
}


相关题目

有俩个排序的数组A1和A2,内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数,把A2中的所有数字插入A1中,并且所有的数字是排序的。


思想

我们首先想到的是从前往后,那么就会出现多次移动同一个数字的情况。所以,我们从后向前插。这样就能减少移动的次数,从而提高效率。

#include<stdio.h>
void MergeArray(int arr1[], int arr2[], int len1, int len2)
{
  int end = len1 + len2 - 1;  //尾插的指针
  int i = len1 - 1;     //记录arr1数组的位置
  int j = len2 - 1;     //记录arr2数组的位置
  while (i >=0 && j >= 0 && end >= 0)
  {
    if (arr1[i] > arr2[j])  //arr1大
    {
      arr1[end--] = arr1[i--];
    }
    else          //arr2大
    {
      arr1[end--] = arr2[j--];    
    }
  }
  while(i >= 0) //arr2提前完了
  {
    arr1[end--] = arr1[i--];
  }
  while (j >= 0)  //arr1提前完了
  {
    arr1[end--] = arr2[j--];
  }
}
void print(int arr[], int len)
{
  for (int i = 0; i < len && arr[i] != 0; i++)
  {
    printf("%d ", arr[i]);
  }
}
int main()
{
  int arr1[20] = { 1,3,7,9,11 };
  int arr2[5] = { 2,4,6,8,10 };
  int len1 = 5;
  int len2 = 5;
  MergeArray(arr1, arr2, len1, len2);
  print(arr1, len1 + len2);
  return 0;
}


本章完

目录
相关文章
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面