【算法题】string算法题练习

1.把字符串转换成整数

LCR 192. 把字符串转换成整数 (atoi)https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/

请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的atoi函数）。

函数myAtoi(string s)的算法如下：

1. 读入字符串并丢弃无用的前导空格
2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为0。必要时更改符号（从步骤 2 开始）。
5. 如果整数数超过 32 位有符号整数范围[−231, 231 − 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于−231的整数应该被固定为−231，大于231 − 1的整数应该被固定为231 − 1。
6. 返回整数作为最终结果。

注意：

• 本题中的空白字符只包括空格字符' '。
• 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符

using namespace std; class Solution { public: int myAtoi(string str) { int i = 0; int a = 0, b = 1; if (str.size() == 0) return 0; while (i < str.size() && str[i]==' ') { i++; } if (i == str.size()) return 0; if(!isdigit(str[i])&&str[i]!='-'&&str[i]!='+') return 0; i++; if(!isdigit(str[i])&&!str[i]==NULL) { return 0; } i--; if(str[i]=='-'||str[i]=='+') { b=str[i]=='-'?-1:1; i++; } int count = 0; for (int j = i;j < str.size();j++) { if (str[j] >= '0' && str[j] <= '9') { count++; } } count -= 1; while (str[i] >= '0' && str[i] <= '9') { int digit = str[i] - '0'; a = a * 10 + digit; if (a > INT_MAX / 10 || (a == INT_MAX / 10 && digit > 7)) { if (b == 1) { return INT_MAX; } else { return INT_MIN; } } i++; } return a * b; } };

写后感：

1.本题尤其要注意计算整形数值时，会容易出现栈区数据溢出的问题，此时需要检查。

// 正数溢出 if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > INT_MAX % 10)) { return sign == 1 ? INT_MAX : INT_MIN; } // 没有溢出，正常计算 result = result * 10 + digit;

2.次方计算时（pow(10, n)是浮点数），转换整型时，会出现丢失精度。

3.普及is系列函数

函数	作用	真（返回 true）	假（返回 false）
isalpha(c)	判断是不是字母	a-z, A-Z	数字、符号、空格
isdigit(c)	判断是不是数字	0-9	字母、符号、空格
isalnum(c)	判断是不是字母 + 数字	0-9, a-z, A-Z	空格、符号
isspace(c)	判断是不是空白符	空格 ' ', 换行，制表符	字母、数字、符号
islower(c)	判断是不是小写字母	a-z	大写、数字、符号
isupper(c)	判断是不是大写字母	A-Z	小写、数字、符号

2.字符串相加

415. 字符串相加https://leetcode.cn/problems/add-strings/

给定两个字符串形式的非负整数num1和num2，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如BigInteger）， 也不能直接将输入的字符串转换为整数形式

class Solution { public: string addStrings(string num1, string num2) { int end1=num1.size()-1; int end2=num2.size()-1; string s; s.reserve(max(num1.size(),num2.size())+1); int sum=0; int carry=0; while(end2>=0||end1>=0) { sum=0; int x1=end1>=0?num1[end1]-'0':0; int x2=end2>=0?num2[end2]-'0':0; sum=x1+x2+carry; carry=sum/10; end1--; end2--; sum=sum%10; s+=(sum +'0'); } if(carry==1) { s+=(1 +'0'); } reverse(s.begin(),s.end()); return s; } };

3.字符串相乘

43. 字符串相乘https://leetcode.cn/problems/multiply-strings/

给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数

class Solution { public: string multiply(string num1, string num2) { int m = num1.size(), n = num2.size(); // 结果最多为 m + n 位数 vector<int> res(m + n, 0); // 从个位数开始逐位相乘 for (int i = m - 1; i >= 0; i--) for (int j = n - 1; j >= 0; j--) { int mul = (num1[i] - '0') * (num2[j] - '0'); // 乘积在 res 对应的索引位置 int p1 = i + j, p2 = i + j + 1; // 叠加到 res 上 int sum = mul + res[p2]; res[p2] = sum % 10; res[p1] += sum / 10; } // 结果前缀可能存的 0（未使用的位） int i = 0; while (i < res.size() && res[i] == 0) i++; // 将计算结果转化成字符串 string str; for (; i < res.size(); i++) str.push_back('0' + res[i]); return str.size() == 0 ? "0" : str; } };

写后感：

1.掌握拆分乘法的逻辑方法。

2.对于进位的处理，要搞明白索引的位置问题。

3.c_str比较问题

关于代码输出正确的结果是( )（vs2013 环境下编译运行）

int main(int argc, char *argv[]) { string a="hello world"; string b=a; if (a.c_str()==b.c_str()) { cout<<"true"<<endl; } else cout<<"false"<<endl; string c=b; c=""; if (a.c_str()==b.c_str()) { cout<<"true"<<endl; } else cout<<"false"<<endl; a=""; if (a.c_str()==b.c_str()) { cout<<"true"<<endl; } else cout<<"false"<<endl; return 0; }

答案：false false false

分析:a 和 b的值虽然相同，但是a.c_str()==b.c_str()比较的是存储字符串位置的地址，a和b是两个不同的对象，内部数据存储的位置也不相同，因此不相等，后面c="",a=""与b对象都没有任何的影响，所以都不相等

4.strcpy与memcpy

• strcpy是按字符串拷贝，仅拷贝到\0终止符为止，若原字符数组_str没有正确的\0终止符，strcpy会越界拷贝内存中的随机值，导致乱码；
• memcpy是按字节数拷贝，代码中指定拷贝_size + 1个字节（_size为有效字符数，+1通常为了包含\0），能精准控制拷贝范围，避免越界和随机值问题。

5. 整形提升

关键问题原因：

• 类型不匹配导致的整型提升 / 隐式转换：end是int类型（有符号），pos是size_t类型（无符号，如unsigned int）；
• 当end=-1时，比较end >= pos会先将int类型的end隐式转换为size_t（无符号），-1 转换为无符号数后是极大的正数（如 32 位下为4294967295），远大于pos=0，因此条件成立，循环继续执行。