【C++】13.string类的底层
文章目录
- 3. string类的经典模拟
- 3.1 浅拷贝
- 3.2 深拷贝
- 3.3 模拟实现string
- 3.3.1 传统版写法的String类
- 3.3.2 现代版写法的String类
- 3.3.3 完整代码
- 3.4 写时拷贝(了解)
- 3.5string类的模拟实现
- 4.扩展阅读
- 5. 牛刀小试
- 5.1 仅仅反转字母
- 5.2找字符串中第一个只出现一次的字符
- 5.3字符串里面最后一个单词的长度
- 5.4 验证一个字符串是否是回文
- 5.5字符串相加
- 5.6 字符串相乘
- 5.7 把字符串转换成整数
- 5.8反转字符串 ll
- 5.9 反转字符串中的单词 lll
3. string类的经典模拟
3.1 浅拷贝
浅拷贝:也称位拷贝,编译器只是将对象中的值拷贝过来。如果对象中管理资源,最后就会导致多个对象共享同一份资源,当一个对象销毁时就会将该资源释放掉,而此时另一些对象不知道该资源已经被释放,以为还有效,所以当继续对资源进项操作时,就会发生发生了访问违规。
3.2 深拷贝
如果一个类中涉及到资源的管理,其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。一般情况都是按照深拷贝方式提供。
3.3 模拟实现string
3.3.1 传统版写法的String类
class String
{
public:
String(const char* str = "")
{
// 构造String类对象时,如果传递nullptr指针,可以认为程序非法
if (nullptr == str)
{
assert(false);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
String(const String& s)
: _str(new char[strlen(s._str) + 1])
{
strcpy(_str, s._str);
}
String& operator=(const String& s)
{
if (this != &s)
{
char* pStr = new char[strlen(s._str) + 1];
strcpy(pStr, s._str);
delete[] _str;
_str = pStr;
}
return *this;
}
~String()
{
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};
3.3.2 现代版写法的String类
class String {
public:
String(const char* str = "")
{
if (nullptr == str)
{
assert(false);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
String(const String& s)
: _str(nullptr) {
String strTmp(s._str);
swap(_str, strTmp._str);
}
// 对比下面和上面的赋值那个实现比较好?
String& operator=(String s)
{
swap(_str, s._str);
return *this;
}
/*
String& operator=(const String& s)
{
if(this != &s)
{
String strTmp(s);
swap(_str, strTmp._str);
}
return *this;
} */
~String() {
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};
3.3.3 完整代码
string.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
// 防止头文件被多次包含
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
// 命名空间bit,用于封装自定义的string类
namespace bit
{
class string
{
public:
// 定义迭代器类型
//typedef char* iterator;
using iterator = char*;
using const_iterator = const char*;
//string();
// string类的构造函数
string(const char* str = "");
string(const string& s);
string& operator=(const string& s);
~string();
void reserve(size_t n);// 预留空间
void push_back(char ch);// 添加单个字符
void append(const char* str);// 追加字符串
string& operator+=(char ch);// 重载+=操作符,用于添加单个字符
string& operator+=(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);
// 重载[]操作符,用于访问字符
char& operator[](size_t i)
{
assert(i < _size);
return _str[i];
}
// 重载[]操作符,用于访问字符(常量版本)
const char& operator[](size_t i) const
{
assert(i < _size);
return _str[i];
}
// 返回迭代器指向字符串的开始和结束
iterator begin()
{
return _str;
}
iterator end()
{
return _str + _size;
}
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str + _size;
}
// 返回字符串的大小
size_t size() const
{
return _size;
}
// 返回C风格字符串
const char* c_str() const
{
return _str;
}
// 清空字符串
void clear()
{
_str[0] = '\0';
_size = 0;
}
// 返回子字符串
string substr(size_t pos, size_t len = npos);
private:
char* _str = nullptr;
size_t _size = 0;
size_t _capacity = 0;
public:
//
//static const size_t npos = -1;
static const size_t npos;// 静态常量,表示无效位置
};
// 重载比较运算符
bool operator== (const string& lhs, const string& rhs);
bool operator!= (const string& lhs, const string& rhs);
bool operator> (const string& lhs, const string& rhs);
bool operator< (const string& lhs, const string& rhs);
bool operator>= (const string& lhs, const string& rhs);
bool operator<= (const string& lhs, const string& rhs);
ostream& operator<<(ostream& os, const string& str);// 重载输出运算符
istream& operator>>(istream& is, string& str);// 重载输入运算符
}
string.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include"string.h"
namespace bit
{
// 重定义 string::npos 为 -1
const size_t string::npos = -1;
// 默认构造函数
/*string::string()
:_str(new char[1]{ '\0' })
, _size(0)
, _capacity(0)
{}*/
// 从 C 风格字符串构造
string::string(const char* str)
:_size(strlen(str))
{
_capacity = _size;
_str = new char[_size + 1];
strcpy(_str, str);
}
// s2(s1)
// 复制构造函数
string::string(const string& s)
{
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
// s2 = s1 = s3
// s1 = s1;
// 赋值操作符
string& string::operator=(const string& s)
{
if (this != &s)
{
delete[] _str;
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
// 析构函数
string::~string()
{
delete[] _str;
_str = nullptr;
_size = 0;
_capacity = 0;
}
// 预留空间
void string::reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
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++;*/
insert(_size, ch);
}
// 在末尾添加字符串
void string::append(const char* str)
{
//size_t len = strlen(str);
//if (_size + len > _capacity)
//{
// size_t newCapacity = 2 * _capacity;
// // 扩2倍不够,则需要多少扩多少
// if (newCapacity < _size + len)
// newCapacity = _size + len;
// reserve(newCapacity);
//}
//strcpy(_str + _size, str);
//_size += len;
insert(_size, str);
}
// 重载 += 操作符,添加字符
string& string::operator+=(char ch)
{
push_back(ch);
return *this;
}
// 重载 += 操作符,添加字符串
string& string::operator+=(const char* str)
{
append(str);
return *this;
}
// 在指定位置插入字符
void string::insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
/*int end = _size;
while (end >= (int)pos)
{
_str[end + 1] = _str[end];
--end;
}*/
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)
{
size_t newCapacity = 2 * _capacity;
// 扩2倍不够,则需要多少扩多少
if (newCapacity < _size + len)
newCapacity = _size + len;
reserve(newCapacity);
}
/*int end = _size;
while (end >= (int)pos)
{
_str[end + len] = _str[end];
--end;
}*/
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
{
// 从后往前挪
size_t end = pos + len;
while (end <= _size)
{
_str[end - len] = _str[end];
++end;
}
_size -= len;
}
}
// 查找字符
size_t string::find(char ch, size_t pos)
{
assert(pos < _size);
for (size_t i = pos; 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;
}
bit::string sub;
sub.reserve(len);
for (size_t i = 0; i < len; i++)
{
sub += _str[pos + i];
}
//cout << sub.c_str() << endl;
return sub;
}
// 重载 == 操作符,比较两个字符串
bool operator== (const string& lhs, const string& rhs)
{
return strcmp(lhs.c_str(), rhs.c_str()) == 0;
}
// 重载 != 操作符
bool operator!= (const string& lhs, const string& rhs)
{
return !(lhs == rhs);
}
// 重载 > 操作符
bool operator> (const string& lhs, const string& rhs)
{
return !(lhs <= rhs);
}
// 重载 < 操作符
bool operator< (const string& lhs, const string& rhs)
{
return strcmp(lhs.c_str(), rhs.c_str()) < 0;
}
// 重载 >= 操作符
bool operator>= (const string& lhs, const string& rhs)
{
return !(lhs < rhs);
}
// 重载 <= 操作符
bool operator<= (const string& lhs, const string& rhs)
{
return lhs < rhs || lhs == rhs;
}
// 重载 << 操作符,用于输出
ostream& operator<<(ostream& os, const string& str)
{
//os<<'"';
//os << "xx\"xx";
for (size_t i = 0; i < str.size(); i++)
{
//os << str[i];
os << str[i];
}
//os << '"';
return os;
}
// 重载 >> 操作符,用于输入
istream& operator>>(istream& is, string& str)
{
str.clear();
char ch;
//is >> ch;
ch = is.get();
while (ch != ' ' && ch != '\n')
{
str += ch;
ch = is.get();
}
return is;
}
}
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include"string.h"
// 测试函数1:演示基本操作和迭代器的使用
void test_string1()
{
bit::string s2;// 创建一个空的 bit::string 对象
cout << s2.c_str() << endl;// 输出空字符串
bit::string s1("hello world");// 创建一个包含初始值的 bit::string 对象
cout << s1.c_str() << endl;// 输出 "hello world"
s1[0] = 'x';// 修改字符串的第一个字符
cout << s1.c_str() << endl;// 输出 "xello world"
// 使用迭代器遍历字符串
for (size_t i = 0; i < s1.size(); i++)
{
cout << s1[i] << " ";// 输出每个字符
}
cout << endl;
// 迭代器 -- 像指针一样的对象
// 使用迭代器进行字符修改
bit::string::iterator it1 = s1.begin();// 获取迭代器指向字符串开始
while (it1 != s1.end())
{
(*it1)--;
++it1;
}
cout << endl;
it1 = s1.begin();
// 再次使用迭代器遍历字符串
while (it1 != s1.end())
{
cout << *it1 << " ";// 输出每个字符
++it1;
}
cout << endl;
// 修改
// 底层是迭代器的支持
// 意味着支持迭代器就支持范围for
// 使用范围 for 循环修改字符串
for (auto& ch : s1)
{
ch++;
}
// 使用范围 for 循环输出修改后的字符串
for (auto ch : s1)
{
cout << ch << " ";
}
cout << endl;
const bit::string s3("xxxxxxxxx");
// 使用范围 for 循环遍历 s3 中的每个字符
// 由于 s3 是常量,不能修改其内容,因此使用引用 &ch 来遍历
for (auto& ch : s3)
{
//ch++;
cout << ch << " ";// 输出每个字符
}
cout << endl;
}
// 测试函数2:演示字符串的拼接和插入操作
void test_string2()
{
bit::string s1("hello world");
cout << s1.c_str() << endl;
s1 += '#';// 追加字符
s1 += "#hello world";
cout << s1.c_str() << endl;
bit::string s2("hello world");
cout << s2.c_str() << endl;
s2.insert(6, 'x');// 在指定位置插入字符
cout << s2.c_str() << endl;
s2.insert(0, 'x');// 在字符串开始位置插入字符
cout << s2.c_str() << endl;
bit::string s3("hello world");
cout << s3.c_str() << endl;
s3.insert(6, "xxx");// 在指定位置插入字符串
cout << s3.c_str() << endl;
s3.insert(0, "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");// 在字符串开始位置插入长字符串
cout << s3.c_str() << endl;
}
// 测试函数3:演示字符串的删除操作
void test_string3()
{
bit::string s1("hello world");
cout << s1.c_str() << endl;
s1.erase(6, 2);// 删除指定位置的字符
cout << s1.c_str() << endl;
s1.erase(5, 20);// 删除指定位置的字符,超出字符串长度
cout << s1.c_str() << endl;
s1.erase(3);// 删除指定位置的字符
cout << s1.c_str() << endl;
}
void test_string4()// 测试函数4:演示字符串的查找操作
{
bit::string s1("hello world");
cout << s1.find(' ') << endl;// 查找空格字符的位置
cout << s1.find("wo") << endl;// 查找子字符串 "wo" 的位置
bit::string s2 = "https://legacy.cplusplus.com/reference/cstring/strstr/?kw=strstr";
//bit::string s2 = "https://blog.csdn.net/ww753951/article/details/130427526";
size_t pos1 = s2.find(':');// 查找字符 ':' 的位置
size_t pos2 = s2.find('/', pos1 + 3);// 查找字符 '/' 的位置,从 pos1 + 3 开始
if (pos1 != string::npos && pos2 != string::npos)// 如果都找到了,执行以下操作
{
bit::string domain = s2.substr(pos1 + 3, pos2 - (pos1 + 3));// 提取域名
cout << domain.c_str() << endl;// 输出域名
bit::string uri = s2.substr(pos2 + 1);// 提取 URI
cout << uri.c_str() << endl;// 输出 URI
}
}
// 测试函数5:演示字符串的复制和赋值操作
void test_string5()
{
bit::string s1("hello world");
bit::string s2(s1);// 使用构造函数复制字符串
cout << s1.c_str() << endl;
cout << s2.c_str() << endl;
s1[0] = 'x';// 修改原字符串
cout << s1.c_str() << endl;
cout << s2.c_str() << endl;// 输出复制的字符串,应保持不变
bit::string s3("xxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
s1 = s3;// 使用赋值操作符复制字符串
cout << s1.c_str() << endl;
cout << s3.c_str() << endl;// 输出赋值的字符串,应保持不变
s1 = s1;// 自赋值
cout << s1.c_str() << endl;
}
// 测试函数6:演示字符串的比较和输出操作
void test_string6()
{
bit::string s1("hello world");
bit::string s2(s1);
bit::string s3 = s1;
// 构造+拷贝 ->优化直接构造
bit::string s4 = "hello world";
cout << (s1 == s2) << endl;// 比较两个字符串是否相等
cout << (s1 < s2) << endl;// 比较两个字符串的字典序
cout << (s1 > s2) << endl;
cout << (s1 == "hello world") << endl;// 比较字符串与 C 风格字符串
cout << ("hello world" == s1) << endl;
//operator<<(cout, s1); // 输出字符串
cout << s1 << endl;// 使用重载的 << 运算符输出字符串
cin >> s1;// 从标准输入读取字符串
cout << s1 << endl;// 输出读取的字符串
std::string ss1("hello world");// 使用标准库的 std::string
cin >> ss1;// 从标准输入读取字符串
cout << ss1 << endl;// 输出读取的字符串
}
int main()
{
//test_string1();
//test_string2();
//test_string3();
//test_string4();
//test_string5();
test_string6();
return 0;
}
打印:
test_string1();
test_string2();
test_string3();
test_string4();
test_string5();
test_string6();
3.4 写时拷贝(了解)
写时拷贝就是一种拖延症,是在浅拷贝的基础之上增加了引用计数的方式来实现的。
引用计数:用来记录资源使用者的个数。在构造时,将资源的计数给成1,每增加一个对象使用该资源,就给计数增加1,当某个对象被销毁时,先给该计数减1,然后再检查是否需要释放资源,如果计数为1,说明该对象时资源的最后一个使用者,将该资源释放;否则就不能释放,因为还有其他对象在使用该资源。
写时拷贝
写时拷贝在读取是的缺陷
3.5string类的模拟实现
string模拟实现参考
4.扩展阅读
面试中string的一种正确写法
STL中的string类怎么了?
5. 牛刀小试
5.1 仅仅反转字母
仅仅反转字母
题目:
代码:
class Solution {
public:
bool isLetter(char ch)
{
if(ch >= 'a' && ch <= 'z')
return true;
if(ch >= 'A' && ch <= 'Z')
return true;
return false;
}
string reverseOnlyLetters(string S) {
if(S.empty())
return S;
size_t begin = 0, end = S.size()-1;
while(begin < end)
{
while(begin < end && !isLetter(S[begin]))
++begin;
while(begin < end && !isLetter(S[end]))
--end;
swap(S[begin], S[end]);
++begin;
--end;
}
return S;
}
};
5.2找字符串中第一个只出现一次的字符
找字符串中第一个只出现一次的字符
题目:
代码:
class Solution {
public:
int firstUniqChar(string s){
int count[26]={0};
// 统计次数
for(auto ch :s){
count[ch -'a']++;
}
for(size_t i=0;i < s.size(); ++i){
if(count[s[i]-'a']== 1)
return i;
}
return -1;
}
};
在这个例子中,
for(auto ch : s)
是一个基于范围的循环(range-based for loop),它遍历字符串s
中的每个字符。auto
关键字告诉编译器自动推断ch
的类型,这里ch
将是char
类型,因为它是从字符串中逐个字符取出的。代码中,
ch
是一个变量,用于在for
循环中遍历字符串s
中的每个字符。在for(auto ch : s)
这行代码中,ch
代表字符串s
中当前遍历到的字符。具体来说,这段代码使用了基于范围的循环(
range-based for loop
),它是一种简洁的遍历容器(如数组、向量、字符串等)的方法。在这个循环中,ch
会依次取得字符串s
中的每个字符,从第一个字符开始,直到字符串的末尾。例如,如果字符串
s
是"hello"
,那么循环将依次执行如下:
ch
被赋值为'h'
ch
被赋值为'e'
ch
被赋值为'l'
ch
被赋值为'l'
ch
被赋值为'o'
每次循环迭代,
ch
都会更新为字符串中的下一个字符。在代码中,ch
被用来统计每个字符在字符串中出现的次数。
5.3字符串里面最后一个单词的长度
字符串里面最后一个单词的长度
题目:
代码:
#include<iostream>
#include<string>
using namespace std;
int main()
{
string line;
// 不要使用cin>>line,因为会它遇到空格就结束了
// while(cin>>line)
while(getline(cin, line))// 使用getline函数读取一行文本,直到遇到换行符
{
size_t pos = line.rfind(' ');// 使用rfind函数查找最后一个空格的位置
cout<<line.size()-pos-1<<endl;// 计算最后一个空格之后的字符数量并输出
//例如(0,2)左开右开是1个,2-(0+1)=1
//[0,2)左闭右开是2个,2-0=2
//(0,2]左开右闭是2个,2-0=2
//[0,2]左闭右闭是3个,2-0+1=3
//上面是左开右开的情况
}
return 0;
}
5.4 验证一个字符串是否是回文
验证一个字符串是否是回文
题目:
代码:
class Solution {
public:
// 判断字符是否为字母或数字
bool isLetterOrNumber(char ch)
{
return (ch >= '0' && ch <= '9')
|| (ch >= 'a' && ch <= 'z')
|| (ch >= 'A' && ch <= 'Z');
}
// 判断字符串是否为回文
bool isPalindrome(string s) {
// 先小写字母转换成大写,再进行判断
for(auto& ch : s)
{
if(ch >= 'a' && ch <= 'z')
ch -= 32;// 将小写字母转换为大写
}
int begin = 0, end = s.size()-1;// 初始化双指针,分别指向字符串的开始和结束位置
while(begin < end)// 当双指针未相遇时继续循环
{
while(begin < end && !isLetterOrNumber(s[begin]))// 移动左指针,直到它指向字母或数字
++begin;
while(begin < end && !isLetterOrNumber(s[end]))// 移动右指针,直到它指向字母或数字
--end;
if(s[begin] != s[end])// 比较左右指针指向的字符是否相等
{
return false;// 如果不相等,说明不是回文
}
else
{
++begin; // 如果相等,移动指针继续比较
--end;
}
}
return true;// 如果所有字符都相等,说明是回文
}
};
注意:
我们要实现的是:给你一个字符串
s
,如果它是 回文串 ,返回true
;否则,返回false
。而:如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。这个东西是回文串的描述,不需要实现!
5.5字符串相加
字符串相加
题目:
代码:
class Solution {
public:
// 将两个字符串形式的数字相加
string addStrings(string num1, string num2) {
string str;// 用于存储最终的相加结果
int end1=num1.size()-1,end2=num2.size()-1;// 两个字符串的末尾索引
int next=0;// 用于存储进位值
// 循环处理两个字符串的每一位数字
while(end1>=0 || end2>=0){
int x1=end1>=0?num1[end1]-'0':0;// 获取num1当前位的数字,如果已经遍历完则为0
int x2=end2>=0?num2[end2]-'0':0;// 获取num2当前位的数字,如果已经遍历完则为0
--end1;// 移动到num1的前一位
--end2;// 移动到num2的前一位
int ret = x1+x2+next;// 计算当前位的和加上进位
next=ret/10;// 计算新的进位值
ret=ret%10;// 计算当前位的结果
// 将当前位的结果插入到结果字符串的开头
str.insert(str.begin(), '0'+ret);
//str.insert(0,1,'0'+ret);// 这行代码与上面一行功能相同,但注释掉的这行代码是另一种插入方式
}
// 如果最后还有进位,需要将进位值添加到结果字符串的开头
if(next==1){
str.insert(str.begin(), '1');
}
return str;// 返回最终的相加结果
}
};
5.6 字符串相乘
43. 字符串相乘 - 力扣(LeetCode)
题目:
代码:
class Solution
{
public:
void MulItem(string &tmp, string &num1, char a)
{
int i = 0, sign=0;
int mul = 0;
while(i < num1.size())
{
mul = (num1[i]-'0') * (a-'0') + sign;
if(mul >= 10)
{
sign = mul / 10;
mul %= 10;
}
else
sign = 0;
tmp.push_back(mul+'0');
i++;
}
if(sign > 0)
tmp.push_back(sign+'0');
}
//对应为相加,sign进位采用引用传递
int AddItem(int a, int b, int &sign)
{
int add = a+b+sign;
if(add >= 10)
{
sign = 1;
add -= 10;
}
else
sign = 0;
return add;
}
//错位相加
void MoveAdd(string &result, string &tmp, int k)
{
int i, j;
i = k;
j = 0;
int sign = 0;
while(i<result.size() &&j<tmp.size())
{
result[i] = AddItem(result[i]-'0', tmp[j]-'0', sign) + '0';
i++;
j++;
}
while(i<result.size() && sign)
{
result[i] = AddItem(result[i]-'0', 0, sign)+'0';
i++;
}
while(j < tmp.size())
{
int v = AddItem(0, tmp[j]-'0', sign);
result.push_back(v+'0');
j++;
}
if(sign)
result.push_back(sign+'0');
}
string multiply(string num1, string num2)
{
//先翻转数据,方便进位处理
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
string tmp, result;
for(int i=0; i<num2.size(); ++i)
{
//使用num2的每一个数据乘以num1
MulItem(tmp, num1, num2[i]);
//将乘得的结果进行错位相加
MoveAdd(result, tmp, i);
tmp.clear();
}
while(result.size()!=1 && result.back()=='0')
result.pop_back();
//翻转数据,恢复数据
reverse(result.begin(), result.end());
return result;
}
};
5.7 把字符串转换成整数
LCR 192.把字符串转换成整数(atoi)
题目:
代码:
class Solution {
public:
int myAtoi(string str)
{
bool sign = true; //默认为正数
// 跳过开头可能存在的空格
int i = 0;
while(i < str.size() && str[i] == ' ')
{
i++;
}
//接着判断首个字符是否为正负号
if(str[i] == '-')
{
sign = false; // 该字符串为负数,移至下一个字符接着判断
i++;
}
else if(str[i] == '+') // 字符串为正数,sign已经默认为true,直接移动到下一位即可
i++;
//下面开始对非正负符号位进行判断
if(str[i] < '0' || str[i] > '9') // 正常数字第一位不能是0,必须为1~9之间的数字,否则就是非法数字
return 0;
int res = 0; //这里res用的int型,需要更加仔细考虑边界情况,但如果用long的话可以省去一些麻烦
int num = 0;
int border = INT_MAX / 10; // 用来验证计算结果是否溢出int范围的数据
while(i < str.size())
{
// 遇到非数字字符,则返回已经计算的res结果
if(str[i] < '0' || str[i] > '9')
break;
// 注意这句话要放在字符转换前,因为需要验证的位数比实际值的位数要少一位, 这里比较巧妙的地方在于
// 1. 用低于int型数据长度一位的数据border判断了超过int型数据长度的值
// 2. 将超过最大值和低于最小值的情况都包括了
if(res > border || res == border && str[i] > '7')
return sign == true ? INT_MAX : INT_MIN;
//开始对数字字符进行转换
num = str[i] - '0';
res = res * 10 + num;
i++;
}
//最后结果根据符号添加正负号
return sign == true ? res : -res;
}
};
5.8反转字符串 ll
541.反转字符串 ll
题目:
代码:
class Solution {
public:
string reverseStr(string s, int k) {
for(int i=0;i<s.size();i+=2*k){
if(i+k<=s.size()){
reverse(s.begin()+i,s.begin()+i+k);
}
else{
reverse(s.begin()+i,s.end());
}
}
return s;
}
};
5.9 反转字符串中的单词 lll
557.反转字符串中的单词 lll
题目:
代码:
class Solution {
public:
void Reverse(string &s, int start, int end)
{
char tmp;
while(start < end)
{
tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
string reverseWords(string s)
{
size_t start = 0;
size_t end = 0;
while(start < s.size())
{
end = s.find(' ', start);
if(end == string::npos)
{
end = s.size();
break;
}
Reverse(s, start, end-1);
start = end+1;
}
Reverse(s, start, end-1);
return s;
}
};