C++中String類常見題目分享
1. 僅僅反轉(zhuǎn)字母
給你一個字符串 s ，根據(jù)下述規(guī)則反轉(zhuǎn)字符串：
所有非英文字母保留在原有位置。
所有英文字母（小寫或大寫）位置反轉(zhuǎn)。
返回反轉(zhuǎn)后的 s 。
示例 1：
輸入：s = "ab-cd"
輸出："dc-ba"
示例 2：
輸入：s = "a-bC-dEf-ghIj"
輸出："j-Ih-gfE-dCba"
示例 3：
輸入：s = "Test1ng-Leet=code-Q!"
輸出："Qedo1ct-eeLg=ntse-T!"
提示：
1 <= s.length <= 100
s 僅由 ASCII 值在范圍 [33, 122] 的字符組成
s 不含 '\"' 或 '\\'
思路：
使用左右指針法。
假設(shè)left指向字符串首個字符，right指向字符串最后一個字符：
當(dāng)left和right指向的字符都是字母時使用swap函數(shù)進(jìn)行交換；
當(dāng)left指向的不是字母時，right–；
right指向的不是字母時，left++；
如果left和right指向的都不是字母時，同時移動；
代碼：
//左右指針法解決
class Solution {
public:
//判斷是否是字母
bool IsWord(char c)
{
if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
{
return true;
}
return false;
}
string reverseOnlyLetters(string s) {
//判斷是否為空
if(s.empty())
{
return s;
}
int left = 0;
int right = s.size() - 1;
//切記不能等于，否則會陷入死循環(huán)
while (left < right)
{
//兩個都是字母。交換
if (IsWord(s[right]) && IsWord(s[left]))
{
swap(s[left], s[right]);
right--;
left++;
}
//右邊為字母，左邊向右進(jìn)
else if (IsWord(s[right]))
{
left++;
}
//左邊為字母，右邊向左走
else if (IsWord(s[left]))
{
right--;
}
//兩邊都不為字母，同時移動
else
{
left++;
right--;
}
}
return s;
}
};時間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)
2.字符串中的第一個唯一字符
給定一個字符串 s ，找到 它的第一個不重復(fù)的字符，并返回它的索引 。如果不存在，則返回 -1 。
示例 1：
輸入: s = "leetcode"
輸出: 0
示例 2:
輸入: s = "loveleetcode"
輸出: 2
示例 3:
輸入: s = "aabb"
輸出: -1
提示:
1 <= s.length <= 10的5次方
s 只包含小寫字母
思路：
因為s只包含小寫字母也就是一共有26個字母，所以可以使用一個數(shù)組將字符串中出現(xiàn)字母的次數(shù)統(tǒng)計起來，然后在數(shù)組中按照字符串順序找第一個只出現(xiàn)一次的字符。
代碼：
class Solution {
public:
int firstUniqChar(string s) {
//使用int數(shù)組存放累加個數(shù)
int str[26] = {0};
for(int i = 0; i < s.size(); i++)
{
//將字符串中的字母出現(xiàn)次數(shù)統(tǒng)計到數(shù)組中
str[s[i] - 'a']++;
}
for(int i = 0; i < s.size(); i++)
{
//當(dāng)數(shù)組中次數(shù)為1時，返回下標(biāo)即可
if(str[s[i] - 'a'] == 1)
return i;
}
return -1;
}
};時間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)
3.字符串最后一個單詞的長度
計算字符串最后一個單詞的長度，單詞以空格隔開，字符串長度小于5000。（注：字符串末尾不以空格為結(jié)尾）
輸入描述：輸入一行，代表要計算的字符串，非空，長度小于5000。
輸出描述：輸出一個整數(shù)，表示輸入字符串最后一個單詞的長度。
示例1：
輸入：hello nowcoder
輸出：8
說明：最后一個單詞為nowcoder，長度為8
思路1：
通過rfind函數(shù)或者find_last_of函數(shù)從后往前找到第一個空格，此時這個空格往后知道結(jié)尾的長度就是最后一個單詞的長度，可以通過size() - pos - 1計算得到最后一個單詞的長度；如果函數(shù)返回值pos = string::npos，說明這個字符串就只有一個單詞，直接返回size即可。注意不能使用cin>>輸入字符串，因為字符串中含有空格，所以要使用getline函數(shù)獲取字符串。
代碼：
#include <iostream>
using namespace std;
int main() {
string s1;
getline(cin,s1);
//通過rfind函數(shù)從前往后查找空格，也可以使用find_last_of函數(shù)
size_t pos = s1.rfind(' ');
//size_t pos = s1.find_last_of(' ');
if(pos == string::npos)//此時說明只有一個單詞
{
cout << s1.size() << endl;
return 0;
}
//找到第一個空格，然后通過計算得到最后一個單詞長度
cout << s1.size() - pos - 1 << endl;
return 0;
}
// 64 位輸出請用 printf("%lld")時間復(fù)雜度：O(N)，最壞情況下rfind函數(shù)遍歷完整個字符串，N為字符串長度。
空間復(fù)雜度：O(1)
4.驗證回文串
如果在將所有大寫字符轉(zhuǎn)換為小寫字符、并移除所有非字母數(shù)字字符之后，短語正著讀和反著讀都一樣。則可以認(rèn)為該短語是一個 回文串 。
字母和數(shù)字都屬于字母數(shù)字字符。
給你一個字符串 s，如果它是 回文串 ，返回 true ；否則，返回 false 。
示例 1：
輸入: s = "A man, a plan, a canal: Panama"
輸出：true
解釋："amanaplanacanalpanama" 是回文串。
示例 2：
輸入：s = "race a car"
輸出：false
解釋："raceacar" 不是回文串。
示例 3：
輸入：s = " "
輸出：true
解釋：在移除非字母數(shù)字字符之后，s 是一個空字符串 "" 。
由于空字符串正著反著讀都一樣，所以是回文串。
提示：
1 <= s.length <= 2 * 10的5次方
s 僅由可打印的 ASCII 字符組成
思路一：
通過去除字符串中不是字母或者數(shù)字的字符之后，再將字符串中的大寫字母全部轉(zhuǎn)換成小寫，將原字符串經(jīng)過上述修改之后保存在新字符串s1中，最后通過reverse翻轉(zhuǎn)函數(shù)將s1翻轉(zhuǎn)之后比較s和s1兩個字符串是否相等；或者使用左右指針的方法比較s字符串中左右兩邊的字符是否相同。我們將字符串中的大寫字母轉(zhuǎn)換成小寫也可以使用庫中提供的tolower函數(shù)。
代碼1：使用reverse函數(shù)
class Solution {
public:
//判斷是否是字母或者數(shù)字
bool IsWAN(char ch)
{
if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
{
return true;
}
return false;
}
//大寫轉(zhuǎn)換成小寫
void StoB(char& ch)
{
if (ch >= 'A' && ch <= 'Z')
{
ch = ch + 'a' - 'A';
}
}
bool isPalindrome(string s) {
if (s.empty())
return true;
//先移除所有非字母數(shù)字字符
string s1;
for (auto e : s)
{
//也可以使用tolower函數(shù)
if (IsWAN(e))
{
StoB(e);//如果是大寫抓換成小寫
s1 += e;
}
}
s = s1;
//翻轉(zhuǎn)后是否相等，如果相等就是回文串
reverse(s1.begin(), s1.end());
if (s1 == s)
return true;
else
return false;
}
};時間復(fù)雜度：O(N)，reverse函數(shù)的時間復(fù)雜度為O(N)
空間復(fù)雜度：O(N)
代碼2：使用左右指針方法
class Solution {
public:
bool IsWAN(char ch)
{
if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
{
return true;
}
return false;
}
void StoB(char& ch)
{
if (ch >= 'A' && ch <= 'Z')
{
ch = ch + 'a' - 'A';
}
}
bool isPalindrome(string s) {
if (s.empty())
return true;
//先移除所有非字母數(shù)字字符
string s1;
for (auto e : s)
{
if (IsWAN(e))
{
//也可以使用tolower函數(shù)
StoB(e);
s1 += e;
}
}
s = s1;
int left = 0;
int right = s.size() - 1;
while (left <= right)
{
if (s[left] != s[right])
{
return false;
}
left++;
right--;
}
return true;
};時間復(fù)雜度：O(N)
空間復(fù)雜度：O(N)
思路二：
通過erase函數(shù)和左右指針搭配。此方法時間復(fù)雜度比較高，不推薦。
代碼：
class Solution {
public:
bool IsWAN(char ch)
{
if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
{
return true;
}
return false;
}
//大寫轉(zhuǎn)換成小寫
void StoB(char& ch)
{
if (ch >= 'A' && ch <= 'Z')
{
ch = ch + 'a' - 'A';
}
}
bool isPalindrome(string s) {
if (s.empty())
return true;
//先移除所有非字母數(shù)字字符
string s1;
int i = 0;
//注意迭代器失效問題
while(i < s.size())
{
if (!IsWAN(s[i]))
{
s.erase(s.begin() + i);
}
else
{
i++;
}
}
//再將字符串中的大寫字母全部轉(zhuǎn)換成小寫
for(auto& e : s)
{
StoB(e);
}
//使用tolower函數(shù)
/*for(auto& e : s)
{
if(e >= 'A' && e <= 'Z')
{
e = tolower(e);
}
}*/
int left = 0;
int right = s.size() - 1;
while (left <= right)
{
if (s[left] != s[right])
{
return false;
}
left++;
right--;
}
return true;
}
};時間復(fù)雜度：O(N*N)，最壞情況下，每次循環(huán)都要移動，字符串長度為N，所以一共需要移動N次，而erase函數(shù)的時間復(fù)雜度為O(N)。
空間復(fù)雜度：O(1)
5.字符串相加
給定兩個字符串形式的非負(fù)整數(shù) num1 和num2 ，計算它們的和并同樣以字符串形式返回。
你不能使用任何內(nèi)建的用于處理大整數(shù)的庫（比如 BigInteger）， 也不能直接將輸入的字符串轉(zhuǎn)換為整數(shù)形式。
示例 1：
輸入：num1 = "11", num2 = "123"
輸出："134"
示例 2：
輸入：num1 = "456", num2 = "77"
輸出："533"
示例 3：
輸入：num1 = "0", num2 = "0"
輸出："0"
提示：
1 <= num1.length, num2.length <= 10的4次方
num1 和num2 都只包含數(shù)字 0-9
num1 和num2 都不包含任何前導(dǎo)零
思路：
將兩個字符串從右邊開始向前遍歷，即從低位到高位開始計算，定義一個新的字符串s，將位數(shù)從低到高依次放在新字符串；
還需要定義標(biāo)記位用來確定是否需要進(jìn)位；
當(dāng)right1不為0，即num1沒有遍歷完，單獨遍歷num1；
當(dāng)right2不為0，即num2沒有遍歷完，單獨遍歷num2；
還要判斷標(biāo)記位是否還為1，如果是還需要再向前進(jìn)位；
因為字符串中是從低位到高位記錄的，所以最后還要翻轉(zhuǎn)一下才能得到正確結(jié)果。
無論是同時處理還是單獨處理字符串num1和num2，其基本邏輯都差不多。
代碼：
class Solution {
public:
string addStrings(string num1, string num2) {
string s;
//從字符串的右邊開始
int right1 = num1.size() - 1;
int right2 = num2.size() - 1;
int flag = 0;//標(biāo)記位是否需要向前進(jìn)一
int p = 0;//位數(shù)上的值
while(right1 >= 0 && right2 >= 0)
{
//計算出對應(yīng)位置上的整數(shù)
int n1 = num1[right1] - '0';
int n2 = num2[right2] - '0';
int n = n1 + n2;
//當(dāng)flag=1時需要向前進(jìn)一
if(flag)
{
n += 1;
flag = 0;
}
//n大于9時，需要標(biāo)記下，下次進(jìn)一
if(n > 9)
{
flag = 1;
p = n % 10;
}
else
{
flag = 0;
p = n;
}
s += p + '0';
right1--;
right2--;
}
//right1不為0，即num1沒有遍歷完，基本邏輯和上面相同
while(right1 >= 0)
{
int n = num1[right1] - '0';
if(flag)
{
n += 1;
flag = 0;
}
if(n > 9)
{
flag = 1;
p = n % 10;
}
else
{
flag = 0;
p = n;
}
s += p + '0';
right1--;
}
//right2不為0，即num2沒有遍歷完，基本邏輯和上面相同
while(right2 >= 0)
{
int n = num2[right2] - '0';
if(flag)
{
n += 1;
flag = 0;
}
if(n > 9)
{
flag = 1;
p = n % 10;
}
else
{
flag = 0;
p = n;
}
s += p + '0';
right2--;
}
//當(dāng)最后標(biāo)記位仍為1時，向前進(jìn)
if(flag)
{
s += flag + '0';
}
//從個位上開始加，所以最后需要翻轉(zhuǎn)一下
reverse(s.begin(),s.end());
return s;
}
};時間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)
6.反轉(zhuǎn)字符串
編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 s 的形式給出。
不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 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"]
提示：
- 1 <= s.length <= 10的5次方
- s[i] 都是 ASCII 碼表中的可打印字符
思路：
左右指針法進(jìn)行交換，該函數(shù)是引用傳參直接對字符數(shù)組修改即可。也可以直接使用reverse函數(shù)進(jìn)行逆置。
代碼：
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size() - 1;
while(left < right)
{
swap(s[left],s[right]);
left++;
right--;
}
}
};時間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)
class Solution {
public:
void reverseString(vector<char>& s) {
//使用reverse函數(shù)
reverse(s.begin(),s.end());
}
};時間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)
到此這篇關(guān)于C++中String類常見題目分享的文章就介紹到這了,更多相關(guān)C++ String類內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++?通過pqxxlib庫鏈接?PostgreSql數(shù)據(jù)庫的詳細(xì)過程
這篇文章主要介紹了C++?通過pqxxlib庫鏈接?PostgreSql數(shù)據(jù)庫,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-04-04
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)個人財務(wù)管理軟件，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要為大家詳細(xì)介紹了一個基于QT6的音頻可視化Demo,文中的示例代碼,具有一定的借鑒價值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-12-12
這篇文章我們來聊聊C++中的整型,整型即整數(shù)，與小數(shù)對應(yīng)。許多語言只能表示一種整型（如Python），而在C++當(dāng)中根據(jù)整數(shù)的范圍提供了好幾種不同的整型,下面文章我們就來看看具體是哪幾種,需要的朋友也可以參考一下2021-11-11
這篇文章主要介紹了C語言中的判斷質(zhì)數(shù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要介紹了C++類的大小，在C++中，結(jié)構(gòu)體和類的唯一區(qū)別就是結(jié)構(gòu)體和類具有不同的默認(rèn)訪問控制屬性，下面一起進(jìn)入文章查看詳細(xì)內(nèi)容2021-11-11
這篇文章主要介紹了C語言求冪計算的高效解法,分別演示了求冪運算與整數(shù)次方的解法,具有不錯的參考借鑒價值,需要的朋友可以參考下2014-09-09
c語言中實現(xiàn)數(shù)組幾個數(shù)求次大值
這篇文章主要介紹了c語言中實現(xiàn)數(shù)組幾個數(shù)求次大值，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
C語言中有很多內(nèi)置的字符串處理函數(shù),這些函數(shù)都在<string.h>頭文件中聲明,本文給大家介紹C語言字符串常用處理函數(shù)小結(jié),感興趣的朋友一起看看吧2023-11-11
C++中typedef 及其與struct的結(jié)合使用
這篇文章主要介紹了C++中typedef 及其與struct的結(jié)合使用,需要的朋友可以參考下2014-02-02