反轉字符串

題目鏈接

描述

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。

不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。

你可以假設數組中的所有字符都是 ASCII 碼表中的可打印字符。

示例 1：
輸入：[“h”,“e”,“l”,“l”,“o”]
輸出：[“o”,“l”,“l”,“e”,“h”]

示例 2：
輸入：[“H”,“a”,“n”,“n”,“a”,“h”]
輸出：[“h”,“a”,“n”,“n”,“a”,“H”]

題解

C++庫函數 reverse 做題肯定要了解其內部原理

class Solution {
public:void swap(char&c1,char&c2){char tmp = c1;c1=c2;c2=tmp;}void reverseString(vector<char>& s) {size_t left = 0,right = s.size()-1;while(left <right){swap(s[left],s[right]);++left;--right;}}
};

反轉字符串II

題目鏈接

描述

給定一個字符串 s 和一個整數 k，從字符串開頭算起, 每計數至 2k 個字符，就反轉這 2k 個字符中的前 k 個字符。

如果剩余字符少于 k 個，則將剩余字符全部反轉。

如果剩余字符小于 2k 但大于或等于 k 個，則反轉前 k 個字符，其余字符保持原樣。

示例:

輸入: s = “abcdefg”, k = 2
輸出: “bacdfeg”

題解

字符串是一段一段的進行反轉，所以我們在循環的時候可以每次+一段

class Solution {
public:string reverseStr(string s, int k) {size_t len = s.size();// 對于字符串是一段一段的處理 所以可以一次跳一段for(int i=0;i<len;i+=2*k){if(i+k<=len){reverse(s.begin()+i,s.begin()+i+k);continue;}reverse(s.begin()+i,s.end());}return s;}
};

替換數字

題目鏈接

描述

給定一個字符串 s，它包含小寫字母和數字字符，請編寫一個函數，將字符串中的字母字符保持不變，而將每個數字字符替換為number。

例如，對于輸入字符串 “a1b2c3”，函數應該將其轉換為 “anumberbnumbercnumber”。

對于輸入字符串 “a5b”，函數應該將其轉換為 “anumberb”

輸入：一個字符串 s,s 僅包含小寫字母和數字字符。

輸出：打印一個新的字符串，其中每個數字字符都被替換為了number

樣例輸入：a1b2c3

樣例輸出：anumberbnumbercnumber

數據范圍：1 <= s.length < 10000。

題解：replace函數

利用string的replace函數

#include <iostream>
#include <string>
using namespace std;void change_string(string&s){size_t len = s.size();for(int i=0;i<len;++i){if(s[i]<='9'&&s[i]>='0'){s.replace(s.begin()+i,s.begin()+i+1,"number");len+=5;i+=5;			}}
}
int main(){string s{"1das1das25das"};change_string(s);cout<<s<<"\n";return 0;
}

題解：雙指針

先將字符串擴充到最后的大小，然后從后先前進行填充

#include <iostream>
#include <string>
using namespace std;void change_string(string&s){size_t old_len = s.size();int count{0};for(int i=0;i<old_len;++i){if(s[i]<='9'&&s[i]>='0')++count;}s.resize(old_len+5*count);size_t new_len = s.size();for(int front = old_len-1,back=new_len-1;front>=0;--back,--front){if(s[front]>='0'&&s[front]<='9'){s[back]='r';s[back-1]='e';s[back-2]='b';s[back-3]='m';s[back-4]='u';s[back-5]='n';back-=5;}elses[back]=s[front];}
}
int main(){string s;cin>>s;change_string(s);cout<<s<<"\n";return 0;
}

翻轉字符串里的單詞

題目鏈接

描述

給定一個字符串，逐個翻轉字符串中的每個單詞。

示例 1：
輸入: “the sky is blue”
輸出: “blue is sky the”

示例 2：
輸入: " hello world! "
輸出: “world! hello”
解釋: 輸入字符串可以在前面或者后面包含多余的空格，但是反轉后的字符不能包括。

示例 3：
輸入: “a good example”
輸出: “example good a”
解釋: 如果兩個單詞間有多余的空格，將反轉后單詞間的空格減少到只含一個。

題解

分三個步驟：
1、去除多余空格
2、全部字符串進行反轉
3、字符串中的單詞進行一個一個的反轉

class Solution {
public:void deleteSpace(string &s){int slow{0},fast{0};size_t len{s.size()};//去除多余的前面的空格while(len>0&&fast<len&&s[fast]==' ')++fast;while(fast<len){//去除中間if(fast-1>0&&s[fast-1]==' '&&s[fast]==' '){++fast;continue;}elses[slow++]=s[fast++];}//去除尾部if(slow-1>0&&s[slow-1]==' ')s.resize(slow-1);elses.resize(slow);}//[beg,end]void reverse(string&s,int beg,int end){for(;beg<end;--end,++beg){char tmp = s[beg];s[beg] = s[end];s[end] = tmp;}}string reverseWords(string s) {deleteSpace(s);size_t len = s.size();reverse(s,0,len-1);int i,j;for(i=0,j=0;i<len;++i){if(s[i]==' '){reverse(s,j,i-1);j=i+1;}}reverse(s,j,i-1);return s;}
};

右旋字符串

題目鏈接

描述

字符串的右旋轉操作是把字符串尾部的若干個字符轉移到字符串的前面。給定一個字符串 s 和一個正整數 k，請編寫一個函數，將字符串中的后面 k 個字符移到字符串的前面，實現字符串的右旋轉操作。

例如，對于輸入字符串 “abcdefg” 和整數 2，函數應該將其轉換為 “fgabcde”。

輸入：輸入共包含兩行，第一行為一個正整數 k，代表右旋轉的位數。第二行為字符串 s，代表需要旋轉的字符串。

輸出：輸出共一行，為進行了右旋轉操作后的字符串。

樣例輸入：

2
abcdefg

樣例輸出：

fgabcde

數據范圍：1 <= k < 10000, 1 <= s.length < 10000;

題解

1、整體反轉
2、起點到target這一段反轉
3、target到結尾這一段反轉

#include <iostream>
#include <string>
using namespace std;
// [beg,end]
void my_reverse(string&s,int beg,int end){for(;beg<end;++beg,--end){int tmp = s[beg];s[beg]=s[end];s[end]=tmp;}
}
void rightHanded(string&s,int target){size_t len = s.size();my_reverse(s,0,len-1);my_reverse(s,0,target-1);my_reverse(s,target,len-1);
} 
int main(){string s;int target;cin>>target>>s;rightHanded(s,target);cout<<s<<endl;return 0;
}

實現 strStr()

題目鏈接

描述

實現 strStr() 函數。

給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在，則返回 -1。

示例 1: 輸入: haystack = “hello”, needle = “ll” 輸出: 2

示例 2: 輸入: haystack = “aaaaa”, needle = “bba” 輸出: -1

說明: 當 needle 是空字符串時，我們應當返回什么值呢？這是一個在面試中很好的問題。 對于本題而言，當 needle 是空字符串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

題解：暴力算法

class Solution {
public:int strStr(string haystack, string needle) {if(haystack==""||needle=="")return -1;int pLen = haystack.size(),sLen = needle.size();for(int i = 0; i < pLen;++i){if(haystack[i]==needle[0]){int j = 1;for(;j<sLen;++j)if(haystack[i+j]!=needle[j])break;if(j==sLen)return i;}}return -1;}
};

題解：KMP算法(懵懂)

KMP算法：解決字符串匹配的問題

最長相等前后綴得到前綴表

class Solution {
public:void getNext(int *next,const string&s){/*初始化：i：后綴末尾j：前綴末尾*/int j{-1};next[0] = j;for(int i=1;i<s.size();i++){// 前后綴不相同while(j>=0&&s[j+1]!=s[i])j=next[j];//回退// 前后綴相同if(s[j+1]==s[i])++j;// 將j（前綴的長度）賦給next[i]next[i]=j;}}int strStr(string haystack, string needle) {if(!(haystack.size())||!(needle.size()))return -1;int next[needle.size()];getNext(next,needle);int j = -1; // // 因為next數組里記錄的起始位置為-1for(int i=0;i<haystack.size();++i){while(j>=0&&needle[j+1]!=haystack[i])j = next[j];if(haystack[i]==needle[j+1])++j;if(j==(needle.size()-1))return (i-needle.size()+1);}return -1;}
};

重復的子字符串

題目鏈接

描述

題解

給定一個非空的字符串，判斷它是否可以由它的一個子串重復多次構成。給定的字符串只含有小寫英文字母，并且長度不超過10000。

示例 1:

輸入: “abab”
輸出: True
解釋: 可由子字符串 “ab” 重復兩次構成。
示例 2:

輸入: “aba”
輸出: False
示例 3:

輸入: “abcabcabcabc”
輸出: True
解釋: 可由子字符串 “abc” 重復四次構成。 (或者子字符串 “abcabc” 重復兩次構成。）

題解：暴力

class Solution {
public:bool repeatedSubstringPattern(string s) {string tmp,str;for(int i=0;i<s.size()/2;++i){str="";tmp+=s[i];while(str.size()<s.size())str+=tmp;if(str==s)return true;}return false;}
};

題解：KMP

class Solution {
public:void getNext(int *next,const string &s){int j=-1;next[0]=j;for(int i=1;i<s.size();i++){while(j>=0 && s[i]!=s[j+1])j=next[j];if(s[i]==s[j+1])++j;next[i]=j;}}bool repeatedSubstringPattern(string s) {int len = s.size();if(len==0)return false;int next[len];getNext(next,s);if(next[len-1]!=-1 && len % (len - (next[len-1]+1))==0)return true;return false;}
};

題解：移動匹配

class Solution {
public:bool repeatedSubstringPattern(string s) {string t = s+s;t.erase(t.end()-1);if(t.find(s,1)!=string::npos)return true;return false;}
};