字符串

1.反转字符串

344.反转字符串

思路：
用收尾两个指针，每次交换两个指针的值即可。

 public void reverseString(char[] s) {int left,right;for(left=0,right=s.length-1;left<s.length/2;left++,right--) {swap(left,right,s);}}/*** 交换两个字符的值* @param i* @param j* @param s*/public void swap(int i,int j,char []s) {char temp =s[i];s[i]=s[j];s[j]=temp;}

541.反转字符串||

思路
让i的步长为2k，然后每次反转i，i+k区间的字符串即可。

class Solution {public static void reverseString(char[] s,int i,int j) {int left,right;for(left=i,right=j-1;left<right;left++,right--) {swap(left,right,s);}}/*** 交换两个字符的值* @param i* @param j* @param s*/public static  void swap(int i,int j,char []s) {char temp =s[i];s[i]=s[j];s[j]=temp;}public static String  reverseStr(String s, int k) {char []array=s.toCharArray();for(int i=0;i<s.length();i+=2*k) {if((i+k)<s.length()) {reverseString(array, i, i+k);continue;}reverseString(array, i, s.length());}return new String(array);}public static void main(String[] args) {System.out.println(reverseStr("abcdefg",2));}
}

2.替换空格

剑指offer05.替换空格

思路：
双指针法，先统计空格的个数，然后给原字符串扩充空格*2的字符长度，然后left指针指向原字符串最后一个，right指针指向扩充后的字符串最后一个，当left指针遇到空格的时候，right指针存入%20即可，如果是正常字符则存入正常字符。

 public String replaceSpace(String s) {StringBuilder str=new StringBuilder();//如果碰到一个空格，给字符串扩充两个字符for(int i=0;i<s.length();i++) {if(s.charAt(i)==' ') {str.append("  ");}}if(str.length()==0) {return s;}//左指针指向原字符串最后一个位置int left=s.length()-1;s+=str.toString();int right=s.length()-1;char []chars=s.toCharArray();while(left>=0) {if(chars[left]==' ') {chars[right--]='0';chars[right--]='2';chars[right]='%';}else {chars[right]=chars[left];}right--;left--;}return new String(chars);}

3.翻转字符串里的单词

151.反转字符串里的单词

思路：
先去除原字符串多余的空格。
用两个指针，快指针一直往后走，当它遇到不是空字符串的时候，就在慢指针里填充，注意每个单词之间要保证有一个空格。每次循环要保证填入一个单词。怎么保证呢，就是while(sArray[fast]!=’ ')
去除完空格之后字符串要整体翻转。
然后每个单词再单独反转（记录好出现空格的下标，每次反转就是start到字符串的下标即可）

 public static void reverseString(char[] s,int i,int j) {int left,right;for(left=i,right=j-1;left<right;left++,right--) {swap(left,right,s);}}/*** 交换两个字符的值* @param i* @param j* @param s*/public static  void swap(int i,int j,char []s) {char temp =s[i];s[i]=s[j];s[j]=temp;}public static String reverseWords(String s) {//1.去除多余的空格char []sArray=s.toCharArray();int slow=0;for(int fast=0;fast<sArray.length;fast++) {if(sArray[fast]!=' ') {if(slow!=0) {sArray[slow++]=' ';}//当遇到空格的时候说明第一个单词结束,每次只会存入一个单词while(fast<sArray.length&&sArray[fast]!=' ') {sArray[slow++]=sArray[fast++];}}}//2.反转整个字符串reverseString(sArray, 0, slow);//3.对每个单词进行反转int start=0;for(int i=0;i<=slow;i++) {if(i==slow||sArray[i]==' ') {reverseString(sArray, start, i);//记录好开始的下标start=i+1;}}return new String(sArray).substring(0,slow);}

4.左旋转字符串

剑指 Offer 58 - II. 左旋转字符串

思路：
先翻转前n个字符串，然后反转剩下的字符串，最好来个统一字符串反转就ok了。空间复杂度为O(1)。

  public static void reverseString(char[] s,int i,int j) {int left,right;for(left=i,right=j-1;left<right;left++,right--) {swap(left,right,s);}}/*** 交换两个字符的值* @param i* @param j* @param s*/public static  void swap(int i,int j,char []s) {char temp =s[i];s[i]=s[j];s[j]=temp;}public String reverseLeftWords(String s, int n) {char[] charArray=s.toCharArray();reverseString(charArray, 0, n);reverseString(charArray, n, s.length());reverseString(charArray, 0, s.length());return new String(charArray);}

5.实现strStr函数()

28.实现strStr()函数

思路：
这道题就是实现kmp算法。
那么kmp算法究竟是什么意思呢。我们通过对模式串进行处理，生成一个next数组。这样当字符串出现不匹配的时候，会根据next数组进行匹配，而不需要重头进行匹配了。
next里存的是什么呢？
里面存的是模式串到这个下标为止的最长相同子序列。这样后面匹配不成功的时候，我们可以直接移动到前边和后边一样的那个字符串那。
例如aabaaf的next数组就是010120。
不同书籍next数组给出了不同的定义，有的是将前缀表整体减1了。有的是将数组整体向右移动1位。第一个位置标记上-1了。
不管next数组怎么定义。里边的本质都是一样的。只是匹配的时候实现的细节不一样。
那么next数组怎么生成呢。我们用两个指针，第一个指针j指向前缀的末尾。i指向后缀的末尾。i一直向后移动。

1. i和j指向的字符不相等时，j就一直往前走，如果一直不相等，直到变为0.
2. i和j指向的字符相等，j++，然后next数组存j就可以了。
   为什么要参考j呢。因为j指向的字符也代表了以当前字符结尾的最长相同前缀，如果当前的相同和后面i指的也相同，那么自然可以++了。如果不相同j就被大会原位了。相当于在本串中又进行了一个模式匹配。

next数组生成完了，那么就可以进行字符匹配了。如果当前字符匹配不上，就根据next数组进行匹配。注意这个地方是while。因为可能也会出现next数组那个地方匹配不上的情况。如果字符匹配的 上，那么就可以一直++了。直到j等于模式串的长度就相当于匹配完成了。

 public int strStr(String haystack, String needle) {//当needle为空串的时候直接返回0即可if(needle.length()==0) {return 0;}//初始化next数组int []next=new int[needle.length()];getNext(next,needle);//j指针指向模式串int j=-1;for(int i=0;i<haystack.length();i++) {//当模式串和文本串不相同的时候要根据next数组位置继续比较while(j>=0&&haystack.charAt(i)!=needle.charAt(j+1)) {j=next[j-1];}if(haystack.charAt(i)==needle.charAt(j+1)) {j++;}//模式串匹配完成if(j==(needle.length()-1)) {return (i-needle.length()-1);}}return -1;}//得到next数组public void getNext(int[]next,String s) {//i指针指向后缀末尾，j指针指向前缀末尾int j=0;next[0]=0;//第一个默认值是0for(int i=1;i<s.length();i++) {//当两个指针不相等的时候，j指针进行回退操作.while(j>0&&s.charAt(i)!=s.charAt(j)) {j=next[j-1];}if(s.charAt(i)==s.charAt(j)) {j++;next[i]=j;}}}

6.重复的子字符串

459.重复的子字符串

思路：
将原来的字符串拼接起来，然后删去头一个字母和最后一个字母，判断剩下的字符串是否还包含原来的字符串，如果包含的话就符合题意，如果不包含就不符合题意。

 public boolean repeatedSubstringPattern(String s) {String index=s+s;return index.substring(1, index.length()-1).contains(s);}