LeetCode—string练习
415.字符串相加
. - 力扣（LeetCode）
错误示范：
遇到这种我们第一想法就是将字符串转化成整数，但这种解法无法提交通过，只能支持将小数字互相转化，遇到较长的字符串就没法通过。
class Solution {
public:
string addStrings(string num1, string num2) {
long long x = stoll(num1);//stoll将字符串转化成long long类型
long long y = stoll(num2);
long long z = x + y;
return to_string(z);//将器转化成字符串类型
}
};
思路：
解法：对两个大整数模拟「竖式加法」的过程 。
我们定义两个指针 end1 和 end2 分别指向 num 1和 num 2 的末尾，即最低位，同时定义一个变量 pcur 维护当前是否有进位，然后从末尾到开头逐位相加即可。当两个数字位数不同时，这里我们在指针当前下标处于负数的时候返回 0，等价于对位数较短的数字进行了补零操作，这样就可以除去两个数字位数不同情况的处理！
代码参考：
class Solution {
public:
string addStrings(string num1, string num2) {
string str;
int pcur = 0;
int end1 = num1.size()-1,end2 = num2.size()-1;
while(end1 >= 0 || end2 >= 0)
{ // 位数不同时用0补位
// 从右向左取数
int val1 = end1 < 0 ? 0 : num1[end1--] - '0';
int val2 = end2 < 0 ? 0 : num2[end2--] - '0';
int sum = val1 + val2 + pcur;
pcur = sum / 10;//进位
sum %= 10;
str += (sum + '0');//加上'0'才是字符串
}
if(pcur == 1)//最后多出的进位
{
str += '1';
}
reverse(str.begin(),str.end());//逆置
return str;
}
};HJ1 字符串最后一个单词的长度
字符串最后一个单词的长度_牛客题霸_牛客网
思路：
调用流插入cin时，流提取遇到' '空格会被自动跳过，直到遇到下一个非空白字符，遇到'\0'结束读取，所以用到
get()函数，get()函数是istream类的一个成员函数，用于从输入流中读取字符，get()函数不会自动跳过任何空白字符，包括空格和制表符。
while循环提取字符串，直到输入流读取到字符串结束符
代码：
#include <iostream>
using namespace std;
int main() {
string str;
while(cin >> str)
{
if(cin.get() == '\0')
break;
}
cout << str.size() << endl;
}125. 验证回文串
思路：
使用双指针。初始时，左右指针分别指向 s 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明 s 是回文串。
代码：
class Solution {
public:
bool isLetterOrNumber(char ch)
{
return (ch >= '0' && ch <= '9')
|| (ch >= 'a' && ch <= 'z')
|| (ch >= 'A' && ch <= 'Z');
}
bool isPalindrome(string s) {
int begin = 0,end = s.size() - 1;
for(auto& ch : s)//加&，在原字符串上修改,现将所有大写转化成小写
{
if(ch >= 'A' && ch <= 'Z')
{
ch += 32;
}
}
while(begin <= end)
{
while(begin < end && !isLetterOrNumber(s[begin]))
{
++begin;
}
while(begin < end && !isLetterOrNumber(s[end]))
{
--end;
}
if(s[begin++] != s[end--])
{
return false;
}
}
return true;
}
};541. 反转字符串 II
思路：
我们直接按题意进行模拟：反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串。
len < i + k 时，就是剩余子串不足k；
len > i + k 时，是子串个数大于k
—> 剩余字符小于 2k 但大于或等于 k 个 / 在原字符上，字符等于2k；
代码：
class Solution {
public:
string reverseStr(string s, int k) {
int len = s.size();
for(int i = 0; i < len ;i += 2 * k)
{//反转每个下标从 2k 的倍数开始的，长度为 k 的子串
reverse(s.begin() + i,s.begin() + min(i + k ,len));
//len < i + k 时，就是剩余子串不足k
//len > i + k 时，是子串个数大于k
//——> 剩余字符小于 2k 但大于或等于 k 个 / 在原字符上，字符等于2k
}
return s;
}
};557. 反转字符串中的单词 III
思路：
开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
代码：
class Solution {
public:
string reverseWords(string s) {
string tmp;//开一个新空间
int len = s.length();
int i = 0;
while(i < len)
{
int start = i;//刷新单词起始位置
while(i < len && s[i] != ' ')
{//记录一个单词的长度
i++;
}
for(int c = i - 1; c >= start ;c--)
{//倒序尾插
tmp.push_back(s[c]);
}
while(i < len && s[i] == ' ')
{
i++;
tmp.push_back(' ');
}
}
return tmp;
}
};LLCR 192. 把字符串转换成整数 (atoi)
思路1 (用long存储）:
1. 首部空格： 删除之即可；
2. 符号位： 三种情况，即 ''+'' , ''−'' , ''无符号" ；新建一个变量 sign 保存符号位，返回前判断正负即可；
3. 非数字字符： 遇到首个非数字的字符时，应立即返回；
4. 数字字符：
（1）字符转数字： “此数字的 ASCII 码” 与 “ 0 的 ASCII 码” 相减，得到当前数字x；
（2）数字拼接： 若从左向右遍历数字，设当前位字符为 c ，当前位数字为 x ，数字结果为 res ，则数字拼接公式为： res = 10 * res + x5.考虑数据是否溢出：因为res是long类型的整形，所以在每轮数字拼接后，判断 res 在此轮拼接后是否超过 2147483647 ，若超过则加上符号位直接返回。
代码1：
class Solution {
public:
int myAtoi(string str) {
int i = 0,sign = 1;//默认符号是+
long res = 0;
while(i < str.size() && str[i] == ' ')//1.丢弃无用的前导空格
{
++i;
}
//2.考虑正负数
if(str[i] == '-')
{
sign = -1;//更新符号
++i;
}
else if (str[i] == '+')
{
i ++;
}
if(str[i] < '0' || str[i] > '9')
// 正常数字第一位不能是0，必须为1~9之间的数字，否则就是非法数字
return 0;
//3.考虑数据是否溢出
for(;i < str.size() ; i++)
{
//注意这句话要放在字符转换前
if(str[i] < '0' || str[i] > '9')
break;
res = res * 10 + (str[i] - '0');
//INT_MAX = 2^32 - 1 = 2147483647
//大于等于最大值直接返回最大值
if(res >= INT_MAX && sign == 1)
{
return INT_MAX;
}
//INT_MIN = -2^32 = -2147483648
//符号是-，且大于最大值时才能直接返回最小值(不看符号，MIN比MAX大1)
if(res > INT_MAX && sign == -1)
{
return INT_MIN;
}
}
return sign * res;
}
};思路2 (不用long)：
该思路只有第5点与思路1不同，res此时是int类型的数据，要避免超出int范围，我们用低于int型数据长度一位的数据 border 判断是否超过int型数据的长度。在每轮数字拼接前，判断 res 在此轮拼接后是否超过 2147483647 / 10 ，若超过则加上符号位直接返回 INT_MAX或 INT_MIN 。
代码2：
class Solution {
public:
int myAtoi(string str) {
int i = 0,sign = 1;//默认符号是+
while(i < str.size() && str[i] == ' ')//1.丢弃无用的前导空格
{
++i;
}
//2.考虑正负数
if(str[i] == '-')
{
sign = -1;//更新符号
++i;
}
else if (str[i] == '+')
{
i ++;
}
if(str[i] < '0' || str[i] > '9')
// 正常数字第一位不能是0，必须为1~9之间的数字，否则就是非法数字
return 0;
int res = 0;//此时res是int类型，要考虑数据溢出
int border = INT_MAX/10;//用来验证数据是否超出int的范围
//3.考虑数据是否溢出
for(;i < str.size() ; i++)
{
//注意这句话要放在字符转换前，
//因为需要验证的位数比实际值的位数要少一位
if(str[i] < '0' || str[i] > '9')
break;
//将超过最大值和低于最小值的情况都包括了
if(res > border || res == border && str[i] - '0' > 7)
{
//还没*10就大于INT_MAX/10 或
//等于INT_MAX/10 并且 当前位数字大于7(INT_MAX最后一位数是7)
return sign == 1 ? INT_MAX : INT_MIN;
}
res = res * 10 + (str[i] - '0');
}
return sign * res;
}
};43. 字符串相乘
思路：
如果 num 1和 num2 之一是 0，则直接将 0 作为结果返回即可。
如果 num 1和 num2 都不是 0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是 num1 乘数是 num2 需要注意的是，num2 除了最低位以外，其余的每一位的运算结果都需要补0（牛逼）。
代码1：
class Solution {
public:
//字符串相加
string addStrings(string num1, string num2) {
string str;
int pcur = 0;
int end1 = num1.size()-1,end2 = num2.size()-1;
while(end1 >= 0 || end2 >= 0)
{
int val1 = end1 < 0 ? 0 : num1[end1--] - '0';
int val2 = end2 < 0 ? 0 : num2[end2--] - '0';
int sum = val1 + val2 + pcur;
pcur = sum / 10;//进位
sum %= 10;
str += (sum + '0');
}
if(pcur == 1)
{
str += '1';
}
reverse(str.begin(),str.end());
return str;
}
//字符串相乘
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")//任意一个是"0"返回结果就是"0"
return "0";
string str1;
int sign = 0;
for(int i = num1.size() - 1;i >=0 ; i--)
{
string str2;
int add = 0;
//对每一位的运算结果补0(除最低位外)，太吊了，但有风险性
for (int j = num2.size() - 1;j > i;j--)
{
str2.push_back('0');
}
int val2 = num2[i] - '0';//拆分num2从右向左乘num1
for(int k = num1.size()-1;k >= 0;k--)
{
int val1 = num1[k] - '0';//获取当前位数字
int mul = val1 * val2 + add;
add = mul / 10;//进位
mul %= 10;//余数尾插
str2 += ( mul + '0');
}
if(add != 0)//处理剩余的余数
{
str2 += (add % 10 + '0');
add /= 10;
}
//先逆置str2，再进行错位相加
reverse(str2.begin(),str2.end());
str1 = addStrings(str1,str2);
}
return str1;
}
};代码2： （封装函数）
1. 下翻转数据
2. 按位相乘
3. 将乘得的结果进行错位相加，模拟乘法的笔算过程
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;
}
};