📒博客主页：要早起的杨同学的博客
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
✉️坚持和努力从早起开始！
💬参考在线编程网站：🌐牛客网🌐力扣
🙏作者水平有限，如果发现错误，敬请指正！感谢感谢！
本文相关知识点总结：
C++（第七篇）：string 容器（介绍、使用、深浅拷贝、模拟实现、写时拷贝）
替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
思路：
多开一个空间，然后遍历原数组，不等于空格就尾插在新数组，等于空格，尾插%20。
本题较为简单
解答
class Solution {
public:
string replaceSpace(string s)
{
string tmp;
int len = s.size();
for(int i = 0; i<s.size(); i++)
{
if(s[i]==' ')
{
len+=2;
}
}
tmp.reserve(len+1);
for(int i = 0; i<s.size(); i++)
{
if(s[i]==' ')
{
tmp += "%20";
}
else
{
tmp += s[i];
}
}
return tmp;
}
};
把字符串转换成整数
把字符串转换成整数_牛客题霸_牛客网 (nowcoder.com)
描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为 0 或者字符串不是一个合法的数值则返回 0
class Solution {
public:
int StrToInt(string str)
{
int flag = 1;
int cur = 0;
if(str[0] == '-')
{
flag = -1;
cur++;
}
if(str[0] == '+')
{
flag = 1;
cur++;
}
int ret = 0;
for(int i = cur; i<str.size(); i++)
{
if(isdigit(str[i]))//判断是否是数字字符
{
ret = ret * 10 + flag * (str[i] - '0');
}
else
{
return 0;
}
}
return ret;
}
};
字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = "11", num2 = "123"
输出："134"
示例 2：
输入：num1 = "456", num2 = "77"
输出："533"
本题我们可以从两个字符串的后面依次往前加，对加的和判断，大于10就保留一个进位并-10，小于10不变，将结果尾插到新字符串ret里。最后逆置ret
class Solution {
public:
string addStrings(string num1, string num2)
{
int end1 = num1.size()-1, end2 = num2.size()-1;
string ret;
int next = 0;
while(end1 >= 0 || end2 >= 0)
{
int val = 0;
if(end1 >= 0)
{
val += num1[end1] - '0';
}
if(end2 >= 0)
{
val += num2[end2] - '0';
}
val += next;
if(val>9)
{
val -= 10;
next = 1;
}
else
{
next = 0;
}
ret += val+'0';
end1--;
end2--;
}
//如果最后还有进位
if(next == 1)
{
ret += next + '0';
}
//逆置
reverse(ret.begin(),ret.end());
return ret;
}
};
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
class Solution {
public:
void reverseString(vector<char>& s)
{
int begin = 0, end = s.size()-1;
while(begin < end)
{
swap(s[begin], s[end]);
begin++;
end--;
}
}
};
字符串中的第一个唯一字符
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
示例 1：
输入: s = "leetcode"
输出: 0
示例 2:
输入: s = "loveleetcode"
输出: 2
示例 3:
输入: s = "aabb"
输出: -1
本题可以使用哈希表。
class Solution {
public:
int firstUniqChar(string s)
{
int count[26] = {0};
for(int i = 0; i<s.size(); i++)
{
count[s[i] - 'a']++;
}
//打印第一个
for(int i = 0; i<s.size(); i++)
{
if(count[s[i] - 'a'] == 1)
{
return i;
}
}
return -1;
}
};
字符串最后一个单词的长度
字符串最后一个单词的长度_牛客题霸_牛客网 (nowcoder.com)
描述
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
输入描述：
输入一行，代表要计算的字符串，非空，长度小于5000。
输出描述：
输出一个整数，表示输入字符串最后一个单词的长度。
示例1
输入：hello nowcoder
输出：8
说明：最后一个单词为nowcoder，长度为8
#include <iostream>
#include <string>
using namespace std;
int main()
{
string a;
getline(cin, a);
int pos = a.rfind(" ");
int len = a.size() - pos -1;
cout<<len<<endl;
}
验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
**说明：**本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串
先将大写字母都转换成统一的小写字母，然后左右指针依次找要进行对比的字符，挨个对比。
class Solution {
public:
bool isLetterOrNumber(char ch)
{
if((ch >= 'a' && ch<='z')
|| (ch >= '0' && ch<='9') )
{
return true;
}
else
{
return false;
}
}
bool isPalindrome(string s)
{
int begin = 0, end = s.size()-1;
for(auto& ch: s)
{
if(ch>='A' && ch<='Z')
{
ch += 32;
}
}
/*
for(int i = 0; i < s.size(); i++)
{
s[i] = tolower(s[i]);
}
*/
while(begin<end)
{
while( begin < end && !isLetterOrNumber(s[begin]))
{
begin++;
}
while( begin < end && !isLetterOrNumber(s[end]))
{
end--;
}
if(s[begin]!=s[end])
{
return false;
}
begin++;
end--;
}
return true;
}
};
反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例 2：
输入：s = "abcd", k = 2
输出："bacd"
class Solution {
public:
string reverseStr(string s, int k)
{
string a = s;
int count = 0;//计数
int pos_cur = 0;//记录位置
int size = s.size();//循环次数,走过多少个字符
while(size--)
{
//如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
if((s.size()-pos_cur) >= k && (s.size()-pos_cur)<2*k )
{
reverse(a.begin()+pos_cur, a.begin()+pos_cur+k);
break;
}
//如果剩余字符少于 k 个，则将剩余字符全部反转。
else if((s.size()-pos_cur) < k)
{
reverse(a.begin()+pos_cur, a.end());
break;
}
count++;
if(count == k*2)
{
reverse(a.begin()+pos_cur,a.begin()+pos_cur+k);
pos_cur += 2*k;
count = 0;
}
}
return a;
}
};
反转字符串中的单词 III
给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1：
输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
示例 2:
输入： s = "God Ding"
输出："doG gniD"
class Solution {
public:
string reverseWords(string s)
{
string a = s;
int pos_cur = 0;
int pos_prev_cur = 0;
while((pos_cur = a.find(" ",pos_prev_cur)) != 18446744073709551615)
{
reverse(a.begin()+pos_prev_cur,a.begin()+pos_cur);
pos_cur++;
pos_prev_cur = pos_cur;
}
if(pos_prev_cur < a.size())
{
reverse(a.begin()+pos_prev_cur, a.end());
}
return a;
}
};
※字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
以num1 = 123 , num2 = 456为例：我们遍历 num2 每一位与 num1 进行相乘，将每一步的结果进行累加，在这个过程如果相乘或者相加的结果大于等于10 ，我们都要去满10进位，如下图所示：
class Solution {
public:
string multiply(string num1, string num2)
{
if(num1 == "0" || num2 == "0")
{
return "0";
}
int m = num1.size();
int n = num2.size();
vector<int> ret((m+n),0);//m位乘以n位最多m+n位数
int sign = 0;//进位
for(int i = m-1; i>=0; --i)
{
for(int j = n-1; j>=0; --j)
{
int n1 = num1[i] - '0';
int n2 = num2[j] - '0';
int sum = n1 * n2 + ret[i+j+1];//加上对应位置已经放上的进位
if(sum > 9)
{
sign = sum/10;
sum %= 10;
}
else
{
sign = 0;
}
ret[i+j+1] = sum; // i+j+1刚好是从m+n-1的位置开始
ret[i+j] += sign; //是+=，否则会覆盖原来的进位，导致丢失数据
}
}
string str;
for(int i = 0; i<ret.size(); i++)
{
if(str.size() == 0 && ret[i] == 0)
{
continue;
}
char ch = (ret[i]+'0');
str+=ch;
}
return str;
}
};