1. 415. 字符串相加
傳送門(mén)
題目詳情
代碼1
class Solution {
public:
string addStrings(string num1, string num2) {
int index1=num1.size()-1,index2=num2.size()-1;//找到最后一位
int next=0;//進(jìn)位
string retStr;
while(index1>=0||index2>=0)//還有一個(gè)沒(méi)完就要進(jìn)來(lái)：有可能一直進(jìn)位
{
int val1=0,val2=0;
if(index1>=0)
{
val1=num1[index1--]-'0';
}
if(index2>=0)
{
val2=num2[index2--]-'0';
}
int ret=next+val1+val2;//兩者相加后加上進(jìn)位數(shù)
next=ret/10;//需要進(jìn)位就是1了，不需要就是0
ret%=10;
retStr.insert(0,1,'0'+ret);//頭插到新string
}
//最后有可能有1+9的情況,現(xiàn)在只會(huì)有0
if(next==1)
{
retStr.insert(0,1,'1');
}
return retStr;
}
};
思路1
- 首先，定義兩個(gè)指針 index1 和 index2 分別指向兩個(gè)輸入字符串的最后一位，用來(lái)從后往前遍歷字符串。
- 然后定義一個(gè)變量 next 用來(lái)表示進(jìn)位，初始化為 0。
- 接下來(lái)使用一個(gè)循環(huán)來(lái)遍歷兩個(gè)字符串，直到 index1 和 index2 都小于 0。在循環(huán)中，每次取出 index1 和 index2 對(duì)應(yīng)位置的數(shù)字，并將它們與進(jìn)位相加，得到一個(gè)臨時(shí)的結(jié)果 ret。
- 然后更新進(jìn)位 next 為 ret/10，并將 ret%10 插入到需要返回的字符串 retStr 的開(kāi)頭。
- 循環(huán)結(jié)束后，還需要檢查最后是否有進(jìn)位，如果有，需要將進(jìn)位插入到結(jié)果字符串的開(kāi)頭。
但此時(shí)還是有一個(gè)問(wèn)題的，那就是效率低（因?yàn)轭^插時(shí)間復(fù)雜度O（N^2））;
代碼2
class Solution {
public:
string addStrings(string num1, string num2) {
int index1=num1.size()-1,index2=num2.size()-1;//找到最后一位
int next=0;//進(jìn)位
string retStr;
while(index1>=0||index2>=0)//還有一個(gè)沒(méi)完就要進(jìn)來(lái)：有可能一直進(jìn)位
{
int val1=0,val2=0;
if(index1>=0)
{
val1=num1[index1--]-'0';
}
if(index2>=0)
{
val2=num2[index2--]-'0';
}
int ret=next+val1+val2;//兩者相加后加上進(jìn)位數(shù)
next=ret/10;//需要進(jìn)位就是1了，不需要就是0
ret%=10;
//使用尾插效率更好,尾插有append，這里我們使用+=
retStr+='0'+ret;
}
//最后有可能有1+9的情況,現(xiàn)在只會(huì)有0
if(next==1)
{
retStr+='1';
}
reverse(retStr.begin(),retStr.end());//尾插后，最后翻轉(zhuǎn)一下
return retStr;
}
};
思路2
整體思路都是一樣的，只不過(guò)有頭插換成了尾插+翻轉(zhuǎn)
2. 125. 驗(yàn)證回文串
傳送門(mén)
題目詳情
代碼1（按照要求修改后放到新string里）
class Solution {
public:
bool isPalindrome(string s) {
string re;
for(auto e:s)//按照要求修改好
{
if((e>='A'&&e<='Z')||(e>='a'&&e<='z')||(e>='0'&&e<='9'))
{
if(e>='A'&&e<='Z')
{
re+=(e+32);
}
else
{
re+=e;
}
}
}
string modified(re);
reverse(re.begin(),re.end());
//看看是否相同
for(int i=0;i<modified.size();i++)
{
if(re[i]!=modified[i])
{
return false;
}
}
return true;
}
思路1
-
遍歷輸入字符串 s 中的每個(gè)字符 e。
如果字符 e 是字母或數(shù)字，則根據(jù)題目要求將大寫(xiě)字母轉(zhuǎn)換為小寫(xiě)字母，并將其添加到新的字符串 re 中。 -
創(chuàng)建一個(gè)新的字符串 modified，它是字符串 re 的一個(gè)副本。
-
反轉(zhuǎn)字符串 re。
-
比較反轉(zhuǎn)后的字符串 re 和副本字符串 modified，如果它們不相等，則返回 false，表示不是回文字符串；如果它們相等，則返回 true，表示是回文字符串
代碼2(利用雙指針/索引)
bool isLetterOrNumber(char ch)
{
return (ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')||(ch>='0'&&ch<='9');
}
class Solution {
public:
bool isPalindrome(string s) {
for(auto& e:s)//大的變小的
{
if(e>='A'&&e<='Z')
{
e+=32;
}
}
int begin=0;
int end=s.size()-1;
while(begin<end)
{
while(begin<end&&!isLetterOrNumber(s[begin]))
{
begin++;
}
while(begin<end&&!isLetterOrNumber(s[end]))
{
--end;
}
if(s[begin]!=s[end])
{
return false;
}
else
{
++begin;
--end;
}
}
return true;
}
};
思路2
- 創(chuàng)建一個(gè)輔助函數(shù) isLetterOrNumber，用于判斷一個(gè)字符是否是字母或數(shù)字。
- 遍歷輸入字符串 s 中的每個(gè)字符 e，將大寫(xiě)字母轉(zhuǎn)換為小寫(xiě)字母。
- 初始化兩個(gè)指針 begin 和 end，分別指向字符串的開(kāi)頭和結(jié)尾。
- 在一個(gè) while 循環(huán)中，不斷移動(dòng)指針 begin 和 end，直到兩個(gè)指針相遇。
在移動(dòng)指針的過(guò)程中，跳過(guò)非字母和數(shù)字的字符。 - 在二者都是數(shù)字或者字母后，比較指針指向的字符，如果不相等，則返回 false，表示不是回文字符串；如果相等，則繼續(xù)移動(dòng)指針。
- 如果循環(huán)結(jié)束后都沒(méi)有返回 false，則說(shuō)明是回文字符串，返回 true。
3. 541. 反轉(zhuǎn)字符串 II
傳送門(mén)
題目詳情
代碼1
class Solution {
public:
string reverseStr(string s, int k) {
int len=s.size();
for(int i=0;i<len;i+=2*k)
{
if(i+k<=len)//剩余字符小于 2k 但大于或等于 k 個(gè)，則反轉(zhuǎn)前 k 個(gè)字符
//同時(shí)前面的2k區(qū)域不用管，直接滿足，只有最后那個(gè)不夠2k的區(qū)間才討論
{
reverse(s.begin()+i,s.begin()+i+k);
}
else{
reverse(s.begin()+i,s.begin()+len);
}
}
return s;
}
};
思路1
利用每次要跳2k來(lái)處理：就直接i+=2k，這樣每次直接跳到下一個(gè)區(qū)間，前面夠2k的不用管，直接滿足i+k<=len，只有那最后一個(gè)不夠2k的需要討論（畢竟s.begin()+len是最后元素的下個(gè)位置）
4. 557. 反轉(zhuǎn)字符串中的單詞 III
傳送門(mén)
題目詳情
代碼1（利用find）
class Solution {
public:
string reverseWords(string s) {
size_t pos=0;
int i=0;
while(i<s.size())
{
pos=s.find(' ',i);
if(pos==string::npos)//只有一個(gè)單詞了
{
reverse(s.begin()+i,s.end());
break;
}
reverse(s.begin()+i,s.begin()+pos);
i=(pos+1);
}
return s;
}
};
思路1
總體思路是找到單詞的左和右索引，在這個(gè)區(qū)間內(nèi)進(jìn)行翻轉(zhuǎn)
- 利用一個(gè)
i對(duì)字符串進(jìn)行遍歷，pos來(lái)儲(chǔ)存找到的' '的下標(biāo) - 那么從i到pos就是一個(gè)單詞加上’ '，正好滿足
reserve()函數(shù)左閉右開(kāi)的性質(zhì) - 然后
i=pos+1（跳到空格后） - 如果沒(méi)找到空格，就說(shuō)明只剩下一個(gè)，或者只有一個(gè)單詞。 就直接
i到end（）進(jìn)行翻轉(zhuǎn)了
代碼2（利用雙指針）
class Solution {
public:
string reverseWords(string s) {
int i=0;
while(i<s.size())//直接進(jìn)循環(huán)
{
int left=i;//存一下起始位置
while(i<s.size()&&s[i]!=' ')//找空格
{
i++;
}
//現(xiàn)在要么找到了，要么到size處了
int right=i-1;
while(left<right)//開(kāi)始換
{
swap(s[left],s[right]);
left++;
right--;
}
if(s[i]==' ')
{
i++;
}
}
return s;
}
};
思路2
總體思路是一樣的，不過(guò)自己找，沒(méi)有利用find文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-819175.html
今天就到這里啦！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-819175.html
到了這里，關(guān)于c++：string相關(guān)的oj題（415. 字符串相加、125. 驗(yàn)證回文串、541. 反轉(zhuǎn)字符串 II、557. 反轉(zhuǎn)字符串中的單詞 III）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
