【算法训练营Day08】字符串part2

反转字符串里的单词

题目链接：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);
        // 读取右旋转的位数 k
        int k = scanner.nextInt();
        scanner.nextLine(); // 消耗掉换行符
        // 读取需要旋转的字符串 s
        String 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数之和等题）
• 双指针都在头部，职责不同，其中一个为循环变量（例如我们前面的移除数组元素等题）