LeetCode 剑指offer 58 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
示例 1：
输入: s = “abcdefg”, k = 2
输出: “cdefgab”
示例 2：
输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”
限制：
1 <= k < s.length <= 10000
思路：
1.首先翻转前n
2,.翻转剩余字符串
3.整个进行翻转
代码：
class Solution { public String reverseLeftWords(String s, int n) { int len=s.length(); StringBuilder sb=new StringBuilder(s); reverseString(sb,0,n-1); reverseString(sb,n,len-1); return sb.reverse().toString(); } public void reverseString(StringBuilder sb, int start, int end) { while (start < end) { char temp = sb.charAt(start); sb.setCharAt(start, sb.charAt(end)); sb.setCharAt(end, temp); start++; end--; } } } //解法二：空间复杂度：O(1)。用原始数组来进行反转操作 //思路为：先整个字符串反转，再反转前面的，最后反转后面 n 个 class Solution { public String reverseLeftWords(String s, int n) { char[] chars = s.toCharArray(); reverse(chars, 0, chars.length - 1); reverse(chars, 0, chars.length - 1 - n); reverse(chars, chars.length - n, chars.length - 1); return new String(chars); } public void reverse(char[] chars, int left, int right) { while (left < right) { chars[left] ^= chars[right]; chars[right] ^= chars[left]; chars[left] ^= chars[right]; left++; right--; } }
题目：LeetCode 28 实现strStr（）
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
KMP算法理解：
例：计算“aabaabaaf”中是否包含“aabaaf”
暴力算法：两层for循环，里层for循环每次移动一个位置进行匹配。
KMP解法：
首先用aabaaf进行匹配。每次从出错位置开始找已走元素的最长前缀。
aabaab，在b的时候，由于是aabaaf，出错。找aabaa的最长相等前后缀
a 0
aa 1
aab 0
aaba 1
aabaa 2
所以最长相等前后缀是2
从已走过位置的下标位置2开始重新匹配
前缀数组的三种写法：
next数组
a a b a a b a a f
0 1 0 1 2 0 重新匹配位置为冲突位置下标-1的位置
-1 0 1 0 1 2 整体右移，这样重新匹配的位置就是冲突位置的下标
-1 0 -1 0 1 -1 整体-1，计算重新匹配位置的时候整体+1还原回来。
（ps:感觉多此一举没搞懂，
一种回答：避免算法死循环
另一种回答：减一是为了优化next数组，不右移的情况下0号位值0你得写额外判断条件，不然打转）
整体代码：
s：a a b a a b a a f
t：a a b a a f
class Solution { //前缀表（不减一）Java实现 public int strStr(String haystack, String needle) { if (needle.length() == 0) return 0; int[] next = new int[needle.length()]; getNext(next, needle); int j = 0; for (int i = 0; i < haystack.length(); i++) { while (j > 0 && needle.charAt(j) != haystack.charAt(i)) j = next[j - 1]; if (needle.charAt(j) == haystack.charAt(i)) j++; if (j == needle.length()) return i - needle.length() + 1; } return -1; }
private void getNext(int[] next, String s) { int j = 0; next[0] = 0; for (int i = 1; i < s.length(); i++) { while (j > 0 && s.charAt(j) != s.charAt(i)) j = next[j - 1]; if (s.charAt(j) == s.charAt(i)) j++; next[i] = j; } } }先理解一下getNext()方法：
四部：
1.初始化 2.处理不相同前缀（回退）3.处理相同前缀（前进） 4.给next数组赋值
next[i]代表当前位置的最大前后缀长度，i代表后缀末尾，j代表前缀末尾
初始化 j 的值为0，next[0]的值一定为0
i从1开始，因为i是后缀末尾。前缀末尾j从0开始
第一个while判断：是用来判断前后缀不相等时候进行回溯到重新进行匹配的位置。重新进行匹配的位置应该是下标的前一位。
且，当j>0并且前后缀末尾不等时才会进行回退。（ j>0保证当前前缀一定是有回退余地的）
第二个if判断：当前后缀末尾相等时，前后缀同时+1。并把当前的前缀末尾值作为当前的最长前后缀相等长度。··
例如：“abaa” 使用getNext后：
初始化：
第一轮循环：
next[1]=0
第二轮循环：
触发条件，j++
next[2]=1
第三轮循环：
i=3 j=1 进入while循环，注意，这是while循环，会多次执行，不要错看成if循环。第一次while，回退到j=0
第二次比较是j=0 i=3进行比较。 最后next[3]=1
最后得到的next[]数组
最后就是取用next数组匹配文本串。
需要注意何时进行终止即可，当j=模式串的大小时，就说明完全匹配上了。因为这里的j不仅仅代表前缀末尾，还代表当前位置的最长前后缀大小值。
当最长前后缀的长度等于模式串的长度时候就说明匹配成功了。
JAVA完整代码和多种写法如下：
package com.dwj.LeetCode.String; public class KMP { public static void main(String[] args) { KMP kmp = new KMP(); String needle = "abaa"; int[] next = new int[needle.length()]; kmp.getNext(next,"abaa"); } public int strStr(String haystack, String needle) { if (needle.length() == 0) return 0; int[] next = new int[needle.length()]; getNext(next, needle); int j = 0; for (int i = 0; i < haystack.length(); i++) { while (j > 0 && needle.charAt(j) != haystack.charAt(i)) j = next[j - 1]; if (needle.charAt(j) == haystack.charAt(i)) j++; if (j == needle.length()) return i - needle.length() + 1; } return -1; } private void getNext(int[] next, String s) { int j = 0; next[0] = 0; for (int i = 1; i < s.length(); i++) { while (j > 0 && s.charAt(j) != s.charAt(i)) j = next[j - 1]; if (s.charAt(j) == s.charAt(i)) j++; next[i] = j; } } }
窗口滑动的方法求：
class Solution { /** * 基于窗口滑动的算法 * <p> * 时间复杂度：O(m*n) * 空间复杂度：O(1) * 注：n为haystack的长度，m为needle的长度 */ public int strStr(String haystack, String needle) { int m = needle.length(); // 当 needle 是空字符串时我们应当返回 0 if (m == 0) { return 0; } int n = haystack.length(); if (n < m) { return -1; } int i = 0; int j = 0; while (i < n - m + 1) { // 找到首字母相等 while (i < n && haystack.charAt(i) != needle.charAt(j)) { i++; } if (i == n) {// 没有首字母相等的 return -1; } // 遍历后续字符，判断是否相等 i++; j++; while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) { i++; j++; } if (j == m) {// 找到 return i - j; } else {// 未找到 i -= j - 1; j = 0; } } return -1; } }
初始化-1：
// 方法一 class Solution { public void getNext(int[] next, String s){ int j = -1; next[0] = j; for (int i = 1; i<s.length(); i++){ while(j>=0 && s.charAt(i) != s.charAt(j+1)){ j=next[j]; } if(s.charAt(i)==s.charAt(j+1)){ j++; } next[i] = j; } } public int strStr(String haystack, String needle) { if(needle.length()==0){ return 0; } int[] next = new int[needle.length()]; getNext(next, needle); int j = -1; for(int i = 0; i<haystack.length();i++){ while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){ j = next[j]; } if(haystack.charAt(i)==needle.charAt(j+1)){ j++; } if(j==needle.length()-1){ return (i-needle.length()+1); } } return -1; } }
原文地址：http://www.cnblogs.com/dwj-ngu/p/16823167.html
