string类的模拟实现以及oj题
前言
上篇博客实现了string类的begin()、end()、构造函数、析构函数、c_str、size()、clear()、capacity()、[ ]、reserve()、push_back、append()、insert()、+=。这篇博客实现剩下的一些重要功能。
string类的模拟实现
string.h
#include<iostream>
#include<string>
#include<assert.h>
#include<string.h>
using namespace std;
namespace stringbyself
{
class string
{
public:
typedef char* iterator;
typedef const char* const_iterator;
//编译器开始
iterator begin()
{
return _str;
}
//编译器结束
iterator end()
{
return _str + _size;
}
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str+_size;
}
//构造函数
string(const char* str = "")
{
_size = strlen(str);
_capacity = _size;
_str = new char(_size + 1);
strcpy(_str, str);
}
//析构
~string()
{
if (_str)
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
}
//c_str
const char* c_str() const
{
return _str;
}
//clear
void clear()
{
_str[0] = '\0';
_size = 0;
}
//size
size_t size() const
{
return _size;
}
//capacity
size_t capacity() const
{
return _capacity;
}
//[]
char& operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}
const char& operator[](size_t pos) const
{
assert(pos < _size);
return _str[pos];
}
void reserve(size_t n);
void push_back(char ch);
string& operator+=(char ch);
string& operator+=(const char* str);
void append(const char* str);
void insert(size_t pos, char ch);
void insert(size_t pos, const char* str);
void erase(size_t pos, size_t len = npos);
size_t find(char ch, size_t pos = 0);
size_t find(const char* str, size_t pos = 0);
string substr(size_t pos = 0, size_t len = npos);
private:
char* _str = nullptr;
size_t _size = 0;
size_t _capacity = 0;
static const size_t npos;
};
bool operator<(const string& s1, const string& s2);
bool operator<=(const string& s1, const string& s2);
bool operator>(const string& s1, const string& s2);
bool operator>=(const string& s1, const string& s2);
bool operator==(const string& s1, const string& s2);
bool operator!=(const string& s1, const string& s2);
ostream& operator<<(ostream& out, const string& s);
istream& operator>>(istream& in, string& s);
}
string.cpp
主要实现的函数：
- erase——删除字符串。首先判断删除的字符串长度是否会超出pos位置开始的原先的字符串长度，若超出则改变len的大小，将pos位置的值改为‘\0’；若未超出长度，接着将需要删除字符串用后面的字符串进行覆盖，改变——size的大小即可。
- find——查找字符和字符串。字符从头到尾进行遍历，查找相同字符，记录位置即可；字符串则利用strstr进行查找。
- substr——字符串截取。首先判断从pos开始的长度是否会超出原先字符串的长度，接着从pos位置开始遍历，并将字符串进行复制即可。
- <、<=、>、>=、==、!=的判断。只需完成两个函数，其他的函数便可用这两个函数实现。判断只需使用strcmp即可进行判断。
- <<、>>——流输出和流输入。流输出只需用范围for即可快速进行判断；流输入注意使用get()，即可在遇到空格时不会停下。
#include"string.h"
namespace stringbyself
{
const size_t string::npos = -1;
void string::reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];//给'\0'多开辟一个空间
strcpy(tmp,_str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
void string::push_back(char ch)
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
_str[_size] = ch;
_size++;
_str[_size] = '\0';
}
string& string::operator+=(char ch)
{
push_back(ch);
return *this;
}
string& string::operator+=(const char* str)
{
append(str);
return *this;
}
void string::append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len > _capacity * 2 ? _size + len : _capacity * 2);
}
strcpy(_str + _size, str);
_size = _size + len;
}
void string::insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
size_t end = _size + 1;
while (end > pos)
{
_str[end] = _str[end - 1];
--end;
}
_str[pos] = ch;
_size++;
}
void string::insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len > _capacity * 2 ? _size + len : _capacity * 2);
}
size_t end = _size + len;
while (end > pos + len - 1)
{
_str[end] = _str[end - len];
--end;
}
for (size_t i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
_size += len;
}
void string::erase(size_t pos, size_t len)
{
assert(pos < _size);
if (len >= _size - pos)
{
_str[pos] = '\0';
_size = pos;
}
else
{
for (int i = 0; i < len; i++)
{
_str[pos] = _str[pos + len];
}
_size -= len;
}
}
size_t string::find(char ch, size_t pos)
{
assert(pos < _size);
for (int i = 0; i < _size; i++)
{
if (ch == _str[i])
return i;
}
return npos;
}
size_t string::find(const char* str, size_t pos)
{
assert(pos < _size);
const char* ptr = strstr(_str + pos, str);
if (ptr == nullptr)
{
return npos;
}
else
{
return ptr - _str;
}
}
string string::substr(size_t pos, size_t len)
{
assert(pos < _size);
if (len > _size - pos)
{
len = _size - pos;
}
string str;
str.reserve(len);
for (int i = 0; i < len; i++)
{
str += _str[pos + i];
}
return str;
}
bool operator<(const string& s1, const string& s2)
{
return strcmp(s1.c_str(), s2.c_str()) < 0;
}
bool operator<=(const string& s1, const string& s2)
{
return s1 < s2 || s1 == s2;
}
bool operator>(const string& s1, const string& s2)
{
return !(s1 < s2 || s1 == s2);
}
bool operator>=(const string& s1, const string& s2)
{
return !(s1 < s2);
}
bool operator==(const string& s1, const string& s2)
{
return strcmp(s1.c_str(), s2.c_str()) == 0;
}
bool operator!=(const string& s1, const string& s2)
{
return !(s1 == s2);
}
ostream& operator<<(ostream& out, const string& s)
{
for (auto ch : s)
{
out << ch<<" ";
}
return out;
}
istream& operator>>(istream& in, string& s)
{
s.clear();
const int n = 256;
char buff[n];
int i = 0;
char ch = in.get();
while (ch != '\0' && ch != '\n')
{
buff[i++] = ch;
if (i == n-1)
{
buff[i] = '\0';
s += ch;
i = 0;
}
ch = in.get();
}
if (i > 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}
}
test.cpp
#include"string.h"
int main()
{
string s("hello world");
cout << s << endl;
s.erase(2, 2);
cout << s << endl;
int pos = s.find(' ');
s[pos] = '$';
cout << s << endl;
pos = s.find("rl");
s[pos] = '$';
cout << s << endl;
string ss;
ss = s.substr(2,5);
cout << ss << endl;
cout << (s > ss) << endl;
cout << (s <= ss) << endl;
cout << (s == ss) << endl;
cout << (s != ss) << endl;
return 0;
}
oj题
字符串相加
字符串相加-力扣
思路：从后往前将字符转化为数字进行相加（注意是否需要进位），写入新的字符串，最后再将字符串进行反转即可
class Solution {
public:
string addStrings(string num1, string num2) {
int len1=num1.size()-1;
int len2=num2.size()-1;
string num3;
int value1 = 0, value2 = 0, next = 0;
while(len1 >= 0 || len2 >= 0)
{
if(len1 >= 0)
value1=num1[len1--]-'0';
else
value1=0;
if(len2 >= 0)
value2=num2[len2--]-'0';
else
value2=0;
int sum=value1+value2+next;
if(sum > 9)
{
sum-=10;
next=1;
}
else
next=0;
num3+=(sum+'0');
}
if(next == 1)
num3+='1';
reverse(num3.begin(),num3.end());
return num3;
}
};
验证回文串
验证回文串-力扣
思路：
- 将字符串都转化为小写
- 当左右都为字母时，则进行比较，若不为字母则++或–直到为字母为止，直到左边和右边相等
class Solution {
public:
bool isLetterOrNumber(char ch)
{
return (ch >= '0' && ch <= '9')
|| (ch >= 'a' && ch <= 'z')
|| (ch >= 'A' && ch <= 'Z');
}
bool isPalindrome(string s) {
if(s == " ")
return true;
for(auto& ch:s)
{
if(ch >= 'A' && ch <='Z')
ch+=32;
}
int left=0;
int right=s.size()-1;
while(left < right)
{
while(left < right && !isLetterOrNumber(s[left]))
{
left++;
}
while(left < right && !isLetterOrNumber(s[right]))
{
right--;
}
if(s[left] == s[right])
{
left++;
right--;
}
else
{
return false;
}
}
return true;
}
};
反转字符串 II
反转字符串 II-力扣
思路：
- 判断待反转字符是否小于设定值，若小于设定值，直接将右端点设定为最后即可，否则，则将右端点设定为左端点+设定值-1
- 当左端点小于字符串长度时进入循环，将设定值长度的字符进行反转，然后将左端点加上两倍的设定值，将右端点设定为左端点+设定值-1，判断右端点是否超出字符串的范围，若超出则赋值为最后一位
class Solution {
public:
string reverseStr(string s, int k) {
if(k == 1)
return s;
int left=0;
int right=left+k-1;
if(k >= s.size())
{
right=s.size()-1;
}
while(left < s.size())
{
int len1=left;
int len2=right;
while(len1<len2)
{
swap(s[len1++],s[len2--]);
}
left+=2*k;
right=left+k-1;
if(right >= s.size())
{
right=s.size()-1;
}
}
return s;
}
};
