反轉字符串里的單詞

題目鏈接：151. 反轉字符串中的單詞

雙指針法解題邏輯

• head指針遍歷字符串
• 遍歷到單詞首單詞，生成end指針移動到單詞尾部
• 遇到完整單詞收集，壓入棧中
• head指針移動到end指針處
• 遍歷完之后
• 通過出棧還原字符串

代碼如下：

class Solution {public String reverseWords(String s) {int head = 0;Deque<String> strs = new ArrayDeque<String>();int count = 0;while(head < s.length()) {if(s.charAt(head) == ' ') {head++;continue;}int end = head;while(end < s.length() && s.charAt(end) != ' ') end++;strs.push(s.substring(head,end));count++;head = end + 1;}StringBuilder result = new StringBuilder();while(!strs.isEmpty()) {if(count-- == 1) result.append(strs.pop());else result.append(strs.pop() + " ");}return result.toString();}
}

右旋字符串

題目鏈接：55. 右旋字符串（第八期模擬筆試）

雙指針法解題邏輯：

• head指針指向str頭部，end指針指針在尾部
• end指針逆著走k步
• 截取前一部分字符串與后一部分字符串拼接即可

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 讀取右旋轉的位數 kint k = scanner.nextInt();scanner.nextLine(); // 消耗掉換行符// 讀取需要旋轉的字符串 sString s = scanner.nextLine();int head = 0;int end = s.length() - k;System.out.println(s.substring(end,s.length()) + s.substring(head,end));}
}

KMP算法

關于kmp算法的理解可以看我的另外一篇文章：KMP算法詳解，能認字就能搞懂

題目鏈接：28. 找出字符串中第一個匹配項的下標

解題邏輯：

• 首先創建模式串的next數組
• 創建雙指針一個指向主串，另一個指向模式串
  • 如果不相同，則模式串的指針根據next數組進行回退
  • 如果兩個指針所指字符相同，則雙指針都向前進一位
  • 要注意如果要回退一定是先回退再比較
• 當模式串的指針指向模式串尾部后一位的時候代表找到了
• 此時把指向主串的指針對應的下標減去模式串的長度再加1就是模式串首次出現的下標
• 如果主串遍歷完了都沒有達到要求則表示沒找到，返回-1

代碼如下：

class Solution {public int strStr(String haystack, String needle) {int[] next = new int[needle.length()];builtNums(next,needle);int j = 0;for(int i = 0;i < haystack.length();i++) {while(haystack.charAt(i) != needle.charAt(j) && j > 0) {j = next[j - 1];}if(haystack.charAt(i) == needle.charAt(j)) {j++;if(j == needle.length()) return i - j + 1;}}return -1;}public void builtNums(int[] next,String needle){//創建雙指針int j = 0;next[j] = 0;//創建next數組for (int i = 1;i < next.length;i++) {while(needle.charAt(i) != needle.charAt(j) && j > 0) j = next[j - 1];if (needle.charAt(i) == needle.charAt(j)) j++;next[i] = j;}}
}

雙指針法總結

這種方法在一些線性結構上使用的比較多例如：數組、鏈表、字符串

要明確雙指針法的靈魂就在于：使用雙指針將兩個for循環才能完成的任務使用一個for循環就可以完成！

比較常見的兩種形式：

• 雙指針一頭一尾，同時向中間逼近（例如我們前面的反轉字符串、n數之和等題）
• 雙指針都在頭部，職責不同，其中一個為循環變量（例如我們前面的移除數組元素等題）