1.翻轉(zhuǎn)字符串里的單詞

題目：

給你一個(gè)字符串?s?，請你反轉(zhuǎn)字符串中?單詞?的順序。

單詞?是由非空格字符組成的字符串。s?中使用至少一個(gè)空格將字符串中的?單詞?分隔開。

返回?單詞?順序顛倒且?單詞?之間用單個(gè)空格連接的結(jié)果字符串。

注意：輸入字符串?s中可能會(huì)存在前導(dǎo)空格、尾隨空格或者單詞間的多個(gè)空格。返回的結(jié)果字符串中，單詞間應(yīng)當(dāng)僅用單個(gè)空格分隔，且不包含任何額外的空格。

示例 1：

輸入：s = "the sky is blue"
輸出："blue is sky the"

示例 2：

輸入：s = " ?hello world ?"
輸出："world hello"
解釋：反轉(zhuǎn)后的字符串中不能存在前導(dǎo)空格和尾隨空格。

思路：

這題歸檔為中等，等會(huì)strStr（）歸檔為簡單？真是不理解。。。

題目思路就是先去除多余空格，然后全部翻轉(zhuǎn)，然后一個(gè)個(gè)翻轉(zhuǎn)單詞

代碼：

class Solution {
public:void reverse(string& s, int start, int end){ //翻轉(zhuǎn)，區(qū)間寫法：左閉右閉 []for (int i = start, j = end; i < j; i++, j--) {swap(s[i], s[j]);}}void removeExtraSpaces(string& s) {//去除所有空格并在相鄰單詞之間添加空格, 快慢指針。int slow = 0;   //整體思想?yún)⒖糷ttps://programmercarl.com/0027.移除元素.htmlfor (int i = 0; i < s.size(); ++i) { //if (s[i] != ' ') { //遇到非空格就處理，即刪除所有空格。if (slow != 0) s[slow++] = ' '; //手動(dòng)控制空格，給單詞之間添加空格。slow != 0說明不是第一個(gè)單詞，需要在單詞前添加空格。while (i < s.size() && s[i] != ' ') { //補(bǔ)上該單詞，遇到空格說明單詞結(jié)束。s[slow++] = s[i++];}}}s.resize(slow); //slow的大小即為去除多余空格后的大小。}string reverseWords(string s) {removeExtraSpaces(s); //去除多余空格，保證單詞之間之只有一個(gè)空格，且字符串首尾沒空格。reverse(s, 0, s.size() - 1);int start = 0; //removeExtraSpaces后保證第一個(gè)單詞的開始下標(biāo)一定是0。for (int i = 0; i <= s.size(); ++i) {if (i == s.size() || s[i] == ' ') { //到達(dá)空格或者串尾，說明一個(gè)單詞結(jié)束。進(jìn)行翻轉(zhuǎn)。reverse(s, start, i - 1); //翻轉(zhuǎn)，注意是左閉右閉 []的翻轉(zhuǎn)。start = i + 1; //更新下一個(gè)單詞的開始下標(biāo)start}}return s;}
};

?這里有個(gè)弱智問題，我是弱智我解釋下：

為什么有些用string& s，有些用string s？

參數(shù)類型	傳遞方式	是否修改原字符串	性能特點(diǎn)
string s	值傳遞	否（修改副本）	復(fù)制整個(gè)字符串（開銷大）
string& s	引用傳遞	是（直接修改原對象）	不復(fù)制字符串（開銷小）
const string& s	常量引用	否（禁止修改）	不復(fù)制字符串（開銷小）

一句話，不改s就&，引用一下；要改s本身就無&。

其實(shí)是三個(gè)函數(shù)，一個(gè)先把字符串里面多余的空格刪掉，一個(gè)是定義翻轉(zhuǎn)函數(shù)，最后一個(gè)調(diào)用前倆再把單詞一個(gè)個(gè)翻轉(zhuǎn)。難點(diǎn)在于邊界條件的控制。

2.右旋轉(zhuǎn)字符串、

題目:

字符串的右旋轉(zhuǎn)操作是把字符串尾部的若干個(gè)字符轉(zhuǎn)移到字符串的前面。給定一個(gè)字符串 s 和一個(gè)正整數(shù) k，請編寫一個(gè)函數(shù)，將字符串中的后面 k 個(gè)字符移到字符串的前面，實(shí)現(xiàn)字符串的右旋轉(zhuǎn)操作。?

例如，對于輸入字符串 "abcdefg" 和整數(shù) 2，函數(shù)應(yīng)該將其轉(zhuǎn)換為 "fgabcde"。

思路：

思路簡單，選全部翻轉(zhuǎn)，再分段翻轉(zhuǎn)，跟上一題有點(diǎn)像但邊界條件簡單的多且不用刪除空格

代碼：
?

#include<iostream>
#include<algorithm>
using namespace std;
int main() {int n;string s;cin >> n;cin >> s;int len = s.size(); //獲取長度reverse(s.begin(), s.end()); // 整體反轉(zhuǎn)reverse(s.begin(), s.begin() + n); // 先反轉(zhuǎn)前一段，長度nreverse(s.begin() + n, s.end()); // 再反轉(zhuǎn)后一段cout << s << endl;} 

reverse函數(shù)上大分

3.實(shí)現(xiàn)strStr()

題目：

給你兩個(gè)字符串?haystack?和?needle?，請你在?haystack?字符串中找出?needle?字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從 0 開始）。如果?needle?不是?haystack?的一部分，則返回??-1?。

示例 1：

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標(biāo) 0 和 6 處匹配。
第一個(gè)匹配項(xiàng)的下標(biāo)是 0 ，所以返回 0 。

示例 2：

輸入：haystack = "leetcode", needle = "leeto"
輸出：-1
解釋："leeto" 沒有在 "leetcode" 中出現(xiàn)，所以返回 -1 。

思路：

說實(shí)話我是真沒看懂這題，特別是KMP，只能說硬著頭皮敲了。。還分類為簡單，nnd

代碼：

class Solution {
public:void getNext(int* next, const string& s) {int j = -1;next[0] = j;for(int i = 1; i < s.size(); i++) { // 注意i從1開始while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了j = next[j]; // 向前回退}if (s[i] == s[j + 1]) { // 找到相同的前后綴j++;}next[i] = j; // 將j（前綴的長度）賦給next[i]}}int strStr(string haystack, string needle) {if (needle.size() == 0) {return 0;}vector<int> next(needle.size());getNext(&next[0], needle);int j = -1; // // 因?yàn)閚ext數(shù)組里記錄的起始位置為-1for (int i = 0; i < haystack.size(); i++) { // 注意i就從0開始while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配j = next[j]; // j 尋找之前匹配的位置}if (haystack[i] == needle[j + 1]) { // 匹配，j和i同時(shí)向后移動(dòng)j++; // i的增加在for循環(huán)里}if (j == (needle.size() - 1) ) { // 文本串s里出現(xiàn)了模式串treturn (i - needle.size() + 1);}}return -1;}
};

只從代碼結(jié)構(gòu)來看的話，先定義一個(gè)next數(shù)組，這個(gè)是當(dāng)匹配到不同字符時(shí)候高效回調(diào)的，不用每次都要重頭再匹配，后面的strStr()分兩種情況，第一種是不匹配了，就用?j = next[j]找之前的匹配位置；第二種情況是匹配的，那么就j++，繼續(xù)往下匹配。最后找到長度等于模式串的子字符串，就返回此子字符串開始的下標(biāo)。

4.重復(fù)的子字符串

題目：

給定一個(gè)非空的字符串?s?，檢查是否可以通過由它的一個(gè)子串重復(fù)多次構(gòu)成。

示例 1:

輸入: s = "abab"
輸出: true
解釋: 可由子串 "ab" 重復(fù)兩次構(gòu)成。

示例 2:

輸入: s = "aba"
輸出: false

示例 3:

輸入: s = "abcabcabcabc"
輸出: true
解釋: 可由子串 "abc" 重復(fù)四次構(gòu)成。 (或子串 "abcabc" 重復(fù)兩次構(gòu)成。)

思路：

這題也是要用KMP，我只能說后面再看一遍嗎，現(xiàn)在不能卡這里了。

代碼：

class Solution {
public:void getNext (int* next, const string& s){next[0] = -1;int j = -1;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) {if (s.size() == 0) {return false;}int next[s.size()];getNext(next, s);int len = s.size();if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {return true;}return false;}
};

?和上題一樣，先創(chuàng)建next數(shù)組，后面就基于一個(gè)類似于數(shù)學(xué)中的定理的東西，證明出來的，用此定理去判斷。