??引言??
大家好啊，我是執梗，今天為大家帶來一套字串處理的專題訓練，字串這東西大家無論是學習還是作業中，接觸的肯定不少，平時如果對字串處理，大家肯定都是直接使用庫函式，畢竟字串的庫函式，那可是多了去了，像Java和Python這種語言，只要你能想到的操作基本都幫你封裝好了，但是這就容易讓人養成了不好的習慣，只會使用庫函式，基礎不扎實，所以打基礎的時候，千萬不要迷戀庫函式！！為了幫助兄弟們打下較好的基礎，我整理了這篇字串處理專題訓練，內容從易到難，幫助你完美過度，夯實基礎，其中更附帶詳細決議，建議兄弟們收藏，有空訓練，

??精彩回放??

??知識導航???

🍅1.進場須知

🍐2.處理字符，血戰力扣

🍍1.反轉字串

🍠2.反轉字串||

🍌3.替換空格

🍐4.翻轉字串里的單詞（中等）

🍑5.左旋轉字串

🍈6.最后一個單詞的長度

🌽7.字串中的第一個唯一字符

🍋3.基礎字串處理總結（題目總鏈接）

🍅1.進場須知

本章旨在為大家鍛煉字串處理的基礎，在大家做題的同時，也該了解自己的語言是否含有相應的庫函式，在進階訓練難題時，大家應該直接使用庫函式，不然代碼會非常冗余，因為進階難題字串的處理往往只是做題的一部分，而基礎訓練只需要對字串處理，所以大家訓練的時候一定也要記住是否有合適的庫函式，

🍐2.處理字符，血戰力扣

🍍1.反轉字串

撰寫一個函式，其作用是將輸入的字串反轉過來，輸入字串以字符陣列 s 的形式給出，

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

題目鏈接：反轉字串

題目分析：題目的要求非常簡單，就是將字符陣列反轉，但要求在原陣列上操作，那我們就不可以new一個新的char[]陣列來交換，既然如此，那我們一定要想到利用雙指標，一個指向陣列頭部，一個指向陣列尾部，交換值后，同時向內移動繼續，直到兩個指標相遇，

方法：雙指標

時間復雜度O(n)：n為陣列s的長度，一共進行了N/2次交換，常數1/2舍去，時間復雜度為O（n）

空間復雜度O(1)：只用了兩個int變數，復雜度為O(1)

class Solution {
    public void reverseString(char[] s) {
        //左指標指向頭部，右指標指向尾部
        int left=0;
        int right=s.length-1;
        while(left<right){
            //交換值
            exch(left,right,s);
            //兩指標同時向中間移動
            left++;
            right--;
        }      
    }
    //寫一個交換方法
    public void exch(int i,int j,char[] s){
        char a=s[i];
        s[i]=s[j];
        s[j]=a;
    }
}

🍠2.反轉字串||

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

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

題目鏈接：反轉字串||

題目決議：這道題是第一題的進階，難點在于要知道合適的反轉范圍，我們用指標l和指標r來每次找到需要反轉的范圍，尤其是注意在最后，r是直接在l的基礎上+k-1，有可能超出陣列長度，所以每次需要在r和n-1之間取小值，這道題l和r的下標，建議畫個圖理解，不要光靠腦子想象，這是大忌，

方法：雙指標

時間復雜度O(n)：n為s的長度，

空間復雜度O(1)或O(n)：這取決于你的語言，像Java中的String不可變，我們只能用一個char陣列取修改，如果你的語言字串可修改，可在原陣列操作即可，這時時間復雜度就是O(1)，

class Solution {
    public String reverseStr(String s, int k) {
        char[] arr=s.toCharArray();
        int n=arr.length;
        //l指標每次+2k
        for(int l=0;l<n;l=l+2*k){
            //r每次在l的基礎上+k-1（因為找的是下標，建議畫個圖寫出下標理解一下）
            int r=l+k-1;
            //如果r超出了陣列長度，這時r就比n-1大了，我們只取到n-1即可
            reverse(arr,l,Math.min(n-1,r));
        }
        return String.valueOf(arr);
    }

    //寫一個反轉方法,反轉char[]陣列指定的索引區間
    public void reverse(char[] arr,int i,int j){
        while(i<j){
            char a=arr[i];
            arr[i++]=arr[j];
            arr[j--]=a;
        }
    }
}

🍌3.替換空格

請實作一個函式，把字串 s 中的每個空格替換成"%20"，

題目鏈接：替換空格https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/替換空格

題目分析：由于是字串，有些語言的字串是可修改的，某些語言的字串是不可修改的，像Java的String是不可修改的，所以這里我們用StringBuilder，當然StringBuffer也可，兩者都是可修改的字串類，但是StringBuilder的效率更高，我們遍歷題目給的String，如果不是空格，之間在StringBuilder后加上相同的，如果是空格，就加上%20，最后把StringBuilder轉換為String回傳即可，

方法: 利用可變字串(這里也可用字串陣列)，遍歷相加

時間復雜度O(n)：n為字串的長度，主要是遍歷的耗時

空間復雜度O(n)：主要是創建了StringBuilder物件，長度最長可能為3n，

class Solution {
    public String replaceSpace(String s) {
        StringBuilder arr=new StringBuilder();
        for(int i=0;i<s.length();i++){
            //是空格就加上%20
            if(s.charAt(i)==' '){
                arr.append("%20");
            }else{
                //不是空格就之間加到arr末尾
                arr.append(s.charAt(i));
            }
        }
        //回傳String形式
        return arr.toString();
    }
}

🍐4.翻轉字串里的單詞（中等）

給你一個字串 s ，逐個翻轉字串中的所有 單詞 ，

單詞 是由非空格字符組成的字串，s 中使用至少一個空格將字串中的 單詞 分隔開，

請你回傳一個翻轉 s 中單詞順序并用單個空格相連的字串，

說明：

輸入字串 s 可以在前面、后面或者單詞間包含多余的空格，
翻轉后單詞間應當僅用一個空格分隔，
翻轉后的字串中不應包含額外的空格，

題目鏈接：翻轉字串里的單詞

題目分析：這道題在字串里算是較有難度的一題，因為它幾乎考察了所有的字串處理操作，想要效率高的完成，還是比較難的，即使是用API，很多人也無從下手，但是這也讓我們了解了更多API的使用操作，是一道非常好的題，下面我為大家講解多種方法以及它們的效率如何，

??考點決議：1.如何修剪掉兩端空格

2.如何把單詞反轉過來

3.如何跳過中間連續的空格

方法1：雙指標遍歷倒插（重點掌握的方法）

首先我們把題目給的String轉換為char[]，還要有一個StringBuilder接收答案，通過從指標從頭尾開始遍歷，如果指的值為空格，均往中間移動，直到不為空格，這樣就剪掉了首尾空格，因為要單詞反轉，所以從后面的right開始尋找單詞，從right的位置，用一個index指標往左移動，找到為空格的位置停止，然后將index+1倒right的位置的單詞遍歷放入到StringBuilder，接著index繼續移動找到不為空格的位置，然后把right更新過來，后面接著同樣的操作知道完成陣列的遍歷得到答案，其實全程除了除去首尾空白，left都沒動過，right也是靠index來更新，主要是index的移動，

由于思路光用語言難以表達，為大家找到一篇優質圖解，建議認真觀看一下——雙指標圖解

時間復雜度O(n)：n為s的長度，只遍歷了一次

空間復雜度O(n)：主要用來存盤字串，因語言而定，字串可變的語言空間復雜度可為O(1)

class Solution {
    public String reverseWords(String s) {
        //轉換為char陣列
        char[] arr = s.toCharArray();
        int left = 0;
        int right = arr.length-1;
        //用來接收答案
        StringBuilder sb = new StringBuilder();
        //去掉空格
        while(arr[left]==' ') left++;
        while(arr[right] == ' ') right--;
        //注意回圈結束條件
        while(left <= right){
            //index從right開始出發
            int index = right;
            //找到為空的地方停下來，這里要注意也得大于等于left,不然在走到最左邊可能會陣列越界
            while(index >= left && arr[index] != ' ' ) index--;
            //注意此時index是指向空格的,從inde+1到right一個個字符加入到StringBuilder中
            for(int i = index+1 ; i <= right ; i++ ) sb.append( arr[i] );
            //因為中間的單詞之間需要加空格，所以index>left時，說明還在中間，我們補一個空格
            if(index > left) sb.append(' ');
            //然后我們繼續移動index找到下一個單詞的，這時也要保證index>=left，原理同上
            while( index >= left && arr[index]==' ' ) index--;
            //然后更新right到index
            right = index;
        }
        return sb.toString();
    }
}

方法2：API大法(雖然復雜度差不多，但其實效率比雙指標低)

時間復雜度：O(n)，其中 nn 為輸入字串的長度，

空間復雜度：O(n)O(n)，用來存盤字串分割之后的結果

上面我們講了這道題的考點決議，如果我們都能夠用API來完成這些需求，那么代碼就會很簡單，前提是大家要會使用和了解這些API，

官方題解的API：

class Solution {
    public String reverseWords(String s) {
        // 除去開頭和末尾的空白字符
        s = s.trim();
        // 正則匹配連續的空白字符作為分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        //Collections帶的reverse方法可以之間反轉，但需要傳入一個List
        Collections.reverse(wordList);
        //String.join方法很冷門，它可以在第二個引數的兩兩元素之間插入第一個引數
        return String.join(" ", wordList);
    }
}

我寫的API法：

class Solution {
    public String reverseWords(String s) {
        //去掉首尾空格的API，需要會用
        String c=s.trim();
        //以連續的空格為切割符，這里涉及到正則運算式
        //ps:split的使用很廣泛，請一定要學會
        String[] arr=c.split("\\s+");
        StringBuilder a=new StringBuilder();
        //從
        for(int i=arr.length-1;i>=0;i--){
                //從尾向頭一個個單詞插入
                //每次插入后補一個空格
                a.append(arr[i]+" ");                             
        }
        //最后一個單詞后面不用空格，刪掉最后一個
        a.deleteCharAt(a.length()-1);
        return a.toString();
    }
}

🍑5.左旋轉字串

字串的左旋轉操作是把字串前面的若干個字符轉移到字串的尾部，請定義一個函式實作字串左旋轉操作的功能，比如，輸入字串"abcdefg"和數字2，該函式將回傳左旋轉兩位得到的結果"cdefgab"，

題目鏈接：左旋轉字串

題目分析：題目的要求很簡單，無非就是將前n個字符移到后面即可，我們可以用StringBuilder或者StringBuffer先接收后面的字符，再接收前n個字符，

方法1：StringBuffer接收

時間復雜度O(n)：n為s的長度，遍歷的耗時

空間復雜度O(n)：主要是StringBuffer的消耗

PS：若面試要求只能用String，這里也可用String，只不過Python和Java中的String不可變，每次都要新建一個字串且拼接的效率低，每次都要申請記憶體，當資料量大時效率低，且申請記憶體高，

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuffer a=new StringBuffer();
        for(int i=n;i<s.length();i++){
            a.append(s.charAt(i));
        }
        for(int i=0;i<n;i++){
            a.append(s.charAt(i));
        }
        return a.toString();
        }     
    }

方法2：String的substring(效率高需掌握，常用API)

時間復雜度O(n):n為s的長度

空間復雜度O(n):n為s的長度

  class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}

🍈6.最后一個單詞的長度

給你一個字串 s，由若干單詞組成，單詞前后用一些空格字符隔開，回傳字串中最后一個單詞的長度，

單詞 是指僅由字母組成、不包含任何空格字符的最大子字串，

題目鏈接：最后一個單詞的長度力扣最后一個單詞的長度

分析：這道題可以看作為第四道題的子題，我們可以考慮同樣的做法，反向遍歷用指標去找到最后一個字母的起始索引和結尾索引，從而求得長度，

方法：反向遍歷

時間復雜度O(n)：n為字串的長度，最多反向遍歷整個字串一遍

空間復雜度O(1)：

class Solution {
    public int lengthOfLastWord(String s) {
      //從末尾開始遍歷
      int index=s.length()-1;
      //結尾有空格有往左移動
      while(s.charAt(index)==' '){
          index--;
      }
      //此時index指向最后一個單詞的最后一個字母,用a記錄此時的位置
      int a=index;
      //index繼續移動,保證index>0
      //這里要注意index指向的是最后一個單詞前面的空格
      while(index>=0&&s.charAt(index)!=' '){
          index--;
      }
      //相級訓得長度
      return a-index;
    }
}

🌽7.字串中的第一個唯一字符

給定一個字串，找到它的第一個不重復的字符，并回傳它的索引，如果不存在，則回傳 -1，

題目鏈接：字串中的第一個唯一字符力扣字串中的第一個唯一字符

題目分析：看到這個題目首先應該想到String的indexOf和lastindexOf兩個API方法，其次應該想到暴力遍歷的方法，效率高的方法，應該想到利用哈希，這里我們不采用map而采用陣列來映射，因為陣列也是哈希映射的一種體現，什么？你說你還不太會哈希或者不懂陣列體現哈希？那你快看看這套哈希專題——【哈希系列】舍友擔心期末考睡不著，我連夜準備了這套哈希全套專題

方法1：利用String的indexOf和lastIndexOf

時間復雜度O(n^2)：涉及到API的原始碼，內部也是回圈實作，這個方法復雜度較高

空間復雜度O(1)

class Solution {
    public int firstUniqChar(String s) {
        for(int i=0;i<s.length();i++){
            //indexOf獲得某個元素從頭遍歷第一次出現的位置
            //lastIndexOf獲得某個元素從尾到頭遍歷第一次出現的位置
            //如果相等說明這個字母就一個
            if(s.indexOf(s.charAt(i))==s.lastIndexOf(s.charAt(i))){
                return i;
            }
        }
        //沒找到回傳-1
        return -1;
    }
}

方法2： 利用陣列哈希映射

時間復雜度O(n)：進行兩次遍歷，這里也可用哈希表來做，只不過使用陣列的效率更好，推薦大家兩種都要嘗試，

空間復雜度O(1)：常數長度的陣列消耗，看為O(1)的復雜度消耗

class Solution {
    public int firstUniqChar(String s) {
        //統計26個字母出現的頻率
        int[] arr=new int[26];
        //遍歷一次陣列統計出現的每個字母出現的次數
        for(int i=0;i<s.length();i++){
            arr[s.charAt(i)-'a']++;
        }
        //再遍歷一次,找到出現次數為1的字母
        for(int i=0;i<s.length();i++){
            if(arr[s.charAt(i)-'a']==1){
                return i;
            }
        }
        return -1;
    }
}

🍋3.基礎字串處理總結（題目總鏈接）

其實我們發現幾乎關于字串的每道題，都或多或少可以利用API直接或者間接求的答案，由此可見了解字串相關API的重要性，但我們在會使用的程序中，也應該掌握其原理，如果沒有這個API你也能自己用實作這個功能，這才是我們的基本功能力，在進階的難題中，字串的處理只是一部分，它還會搭配其他的演算法，為了簡化代碼這時我們就應該使用API來處理，所以大家在打好基礎的同時，也一定要會使用相關的API，

感覺有用的兄弟們，期望給個三連支持一下！！！感謝

文末小驚喜：

Java學習路線總結，搬磚工逆襲Java架構師