剑值offer之替换空格
替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
描述方法：
这是一道考察字符串的题目。由于函数返回的是void，说明此题不能开辟新数组，需要在字符串内直接替换（in-place）可以通过遍历字符串的方式来找到空格进行替换。但要考虑空格只占一个字符的位置，而需要替换的"%20"需要三个字符的位置。因此需要增加两倍空格数量的空间来存储数据。通过定义两个指针来实现遍历替换操作，考虑遍历顺序：
1）如果从左到右遍历，会发现遇到空格，替换会将原来的字符覆盖。
2）如果从右到左遍历，遇到空格就填充"02%"，否则将原字符移动到后面指针的位置。
-
length为原字符串最后一个字符的位置，new_length为结果字符串的最后一个位置
-
如果str[length]不等于空格，就复制，然后指针分别左移一位。
- 如果str[length]等于空格，就填充“20%”
- 一直进行上述步骤，直到字符串遍历完毕
class Solution {
public:
void replaceSpace(char *str,int length) {
if (str == nullptr || length <= 0) return;
int cont = 0;
for (int i = 0; i <= length; ++i ){
if (str[i] == ' ') ++cont;
}
if (!cont) return;
int new_length = length + cont * 2;
for(int i = length; i >= 0; --i){
if (str[i] == ' '){
str[new_length--] = '0';
str[new_length--] = '2';
str[new_length--] = '%';
}
else{
str[new_length--] = str[i];
}
}
}
};
复杂度分析
时间复杂度：O(length) 只遍历了一遍字符串
空间复杂度：O(1) 没有开辟空间
class Solution {
public:
void replaceSpace(char *str,int length) {
string ths(str);
while(1){
int index = ths.find(" ",0);
if (index >= 0&& index < length){
ths.replace(index,1,"%20");
}
else
break;
}
realloc(str,ths.length() + 1);
ths.copy(str,ths.length());
*(str + ths.length()) = '\0';
}
};
C++中string与char的区别
在C语言中，string 是定义一个字符串，存储的是一段如“abcd”的数据，而且最后还有一个结束符’\0’;
char 是定义一个字符，存储一个字符，占一个字节。
在C++中，string有两种，一种是字符串char[]，另外一种是封装好的字符串类，要区别理解。例如’a’是char, "a"是char string，这两者都是普通的字符和字符串，和C语言中没什么不同值得注意的是后者包含两个字符，末尾有一个隐身的’\0’ 。而 string str = “a” 是C++ 封装好的string。C++中的char string和string不是一回事。当用到了"string"这个关键词，就不是普通的字符串，而是用到了封装后的类。
C++中使用char*定义字符串，同样不能改变字符串内的字符的内容，但却可以把另外一个字符串付给它
C++中string的定义字符串，同样不能改变字符串内的字符，但却可以把另外一个字符串付给它，但可以修改里面的字符。
因为传进的参数是char* 指针，因此考虑使用char*转换成string，操作完成之后在通过c_str()方法将string转换成char *
class Solution {
public:
void replaceSpace(char *str,int length) {
string res,s = str;
for (char x : s) {
if (x == ' ') res += "%20";
else res += x;
}
strcpy(str,res.c_str());
}
};
理解string类
string是C++标准库的一个重要的部分，主要用于字符串处理。可以使用输入输出流方式直接进行string操作，也可以通过文件等手段进行string操作。同时，C++的算法库对string类也有着很好的支持，并且string类还和c语言的字符串之间有着良好的接口。
string转换为char*
#include <string>
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
string strOutput = "Hello World";
cout << "[cout] strOutput is: " << strOutput << endl;
// string 转换为 char*
const char* pszOutput = strOutput.c_str();
printf("[printf] strOutput is: %s\n", pszOutput);
return 0;
}
- cout 可直接输出 string 类的对象的内容；
- 使用 c_str() 方法转换 string 类型到 char* 类型时，需要为char*添加 const 关键字；
- printf() 函数不能直接打印 string 类的对象的内容，可以通过将 string 转换为 char* 类型，再使用 printf() 函数打印。
data()方法与c_str()方法
data()方法与c_str()方法相似，都返回 const char* 类型。两者区别和联系如下：
- 在C++98版本中，c_str()返回 const char* 类型，返回的字符串会以空字符（null character）结尾；
- 在C++98版本中，data()返回 const char* 类型，返回的字符串不以空字符（null character）结尾；
- 在C++11版本中，c_str()与data()用法相同（Both string::data and string::c_str are synonyms and return the same value.）
char*、char[] 转换为string
将 char *、char[] 转换为 string 类型时，直接进行赋值操作，将 char *、char[] 的变量赋值给 string 对象即可。
**说明：*这里所说的“赋值”操作，实际上是将 char、char[] 定义的字符串的首地址赋值给 string 对象了。
#include <string>
#include <iostream>
using namespace std;
int main()
{
const char* pszName = "liitdar";
char pszCamp[] = "alliance";
string strName;
string strCamp;
strName = pszName;
strCamp = pszCamp;
cout << "strName is: " << strName << endl;
cout << "strCamp is: " << strCamp << endl;
return 0;
}
string类的find方法
用法如下：
size_t find (const string& str, size_t pos = 0) const;
size_t find (const char* s, size_t pos = 0) const;
size_t find (const char* s, size_t pos, size_t n) const;
size_t find (char c, size_t pos = 0) const;
返回值
第一个匹配项的第一个字符的位置。如果未找到匹配项，该函数将返回String::npos。size_t是无符号整数类型(与成员类型string::size_type相同)。
示例代码
#include <string>
#include <iostream>
using namespace std;
int main()
{
// 待检索的字符串
string strOutput = "|0|1|2|";
// 需要检索的子串
string strObj = "|1|";
// 子串位于字符串中的位置
size_t nLoc = strOutput.find(strObj);
// 如果检索到子串在字符串中，则打印子串的位置
if (nLoc != string::npos)
{
cout << "nLoc is: " << nLoc << endl;
}
return 0;
}