反转字符串里的单词

题目链接：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;}}
}