字符串的常用技巧——参照leetCode暑期打卡活动
leetCode 38. 外观数列
to_string(int a)—将a的值转化为字符串的值
class Solution {
public:
string countAndSay(int n) {
string s="1";
for(int i=0;i<n-1;i++)
//由于开始的时候里面有一个数,所以需要循环n-1次
{
string path;
for(int j=0;j<s.size();j++)
{
int k=j;
while(k<s.size()&&s[k]==s[j])k++;
path+=to_string(k-j)+s[j];//前面的是个数(to_string(int a)---将a的值转化为字符串的值)
j=k-1;
}
s=path;
}
return s;
}
};
leetCode 49. 字母异位词分组
1.字符串可以排序
2.哈希表的存储(不是很熟,所以提及一下)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
if(strs.empty())return res;
unordered_map<string,vector<string>> map;
for(auto t:strs)
{
string s=t;
sort(s.begin(),s.end());
map[s].push_back(t);
}
for(auto t:map)
res.push_back(t.second);
return res;
}
};
leetCode 151. 翻转字符串里的单词(不使用过多的额外空间)
常用思路:先将每个字符翻转,然后再将其整个翻转——可以用到reverse这个函数(也可以部分转换)
erase(某一个起点,某一个终点)——全部清零
class Solution {
public:
string reverseWords(string s) {
int k=0;
for(int i=0;i<s.size();i++)
{
while(i<s.size()&&s[i]==' ')i++;
if(i==s.size())break;
int j=i;
while(j<s.size()&&s[j]!=' ')j++;
reverse(s.begin()+i,s.begin()+j);
if(k)s[k++]=' ';
//如果不是第一个字母的话直接跳过,否则的话加上一个空格
while(i<j)s[k++]=s[i++];
//i~j的这一段一定不会再k的前面,因此此时并不会发生错误
}
s.erase(s.begin()+k,s.end());
reverse(s.begin(),s.end());
return s;
}
};
leetCode 165. 比较版本号
字符串中数字的转换——可以通过每次累加乘上10——来计算出当前数字或者使用函数调用
常用思路:用双指针分别指向两个字符串的开头,然后依次往后移动,直至指针全部指向字符串的末尾
例如通过使用atoi这个库函数直接将字符转换为数字:atoi中 s1.substr(起点,长度).c_str()模板
int a = atoi(s1.substr(i,x-i).c_str());
int b = atoi(s2.substr(j,y-j).c_str());
class Solution {
public:
int compareVersion(string s1, string s2) {
int i=0,j=0;
while(i<s1.size()||j<s2.size())
{
int x=i,y=j,u=0,v=0;
while( x<s1.size() && s1[x]!='.')u=u*10+s1[x++]-'0';
while( y<s2.size() && s2[y]!='.')v=v*10+s2[y++]-'0';
if(u>v)return 1;
if(u<v)return -1;
i=x+1,j=y+1;
//双指针算法需要将字符串中的第一个指针转移到第二个指针的地方的后一位—因为当前的那个点是'.',否则会造成死循///环
}
return 0;
}
};
leetCode 929. 独特的电子邮件地址
int b=s.find(‘c’)找到第一个出现字符c的地方
email.substr(0,at)表示只要从0到at这一部分的所有字符
class Solution {
public:
int numUniqueEmails(vector<string>& emails) {
unordered_set<string> hash;
for(auto email:emails)
{
int at=email.find('@');
string name;
for(auto c:email.substr(0,at))
if(c=='+')break;
else if(c!='.')name+=c;
string domian = email.substr(at+1);
hash.insert(name+'#'+domian);
}
return hash.size();
}
};
leetCode 5. 最长回文子串
思路:从字符的每一个点开始向左向右扩展,并判断其长度与答案的长度大小(由于回文串可以是奇数也可以是偶数,因此在这里需要判断两次)
class Solution {
public:
string longestPalindrome(string s) {
string res;
for(int i=0;i<s.size();i++)
{
for(int j=i,k=i;j>=0&&k<s.size()&&s[j]==s[k];j--,k++)
if(res.size()<k-j+1)
res=s.substr(j,k-j+1);
for(int j=i,k=i+1;j>=0&&k<s.size()&&s[j]==s[k];j--,k++)
if(res.size()<k-j+1)
res=s.substr(j,k-j+1);
}
return res;
}
};
AcWing 445 反转数字
string类似于vector可直接翻转或者直接从最后一个元素弹出元素
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
string a;
cin >> a;
reverse(a.begin(),a.end());
if(a.back()=='-')
{
cout << '-';
a.pop_back();
}
int k=0;
while(k+1<a.size()&&a[k]=='0')k++;
while(k<a.size())cout << a[k++];
return 0;
}