【算法题】string算法题练习

Brilliantwxx

864人浏览 · 2026-05-03 20:52:42

Brilliantwxx · 2026-05-03 20:52:42 发布

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) 的算法如下：

读入字符串并丢弃无用的前导空格

检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。

读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。

将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。

如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。

返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ' ' 。

除前导空格或数字后的其余字符串外，请勿忽略任何其他字符
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 小写、数字、符号

函数	作用	真（返回 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，因此条件成立，循环继续执行。