总结

• 反转、替换空格
  • 双指针法
• 翻转单词顺序、左旋转字符串
  • 反转字符串+反转单词
• 第一个子字符串匹配项、重复子字符串
  • KMP算法

344 (简单)反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

• 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

/*** 双指针法：头尾交换*/
class Solution {public void reverseString(char[] s) {//方式一：头尾交换，异或预算int i=0,j=s.length-1;while(is[i]^=s[j];s[j]^=s[i];s[i]^=s[j];i++;j--;}//方式二：头尾交换，使用缓冲字符// for(int i=0;i//     int j=s.length-1-i;//     char buf=s[i];//     s[i]=s[j];//     s[j]=buf;// }}
}

541 (简单)反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

class Solution {/***	方式一：直接在字符数组上使用异或进行反转*		1.转换为字符数组*		2.每次遍历2*k个元素的区间，直接将前k个元素进行反转*		注意最后一个区间的处理*/public String reverseStr(String s, int k) {char[] arr=s.toCharArray();//每次遍历2*k个元素的区间，将该区间前k个元素进行反转for(int i=0;i<=arr.length-1;i+=2*k){//前k个元素的头索引int head=i;//前k个元素的尾索引：不足k个元素，取数组尾索引int tail=arr.length-1arr[head]^=arr[tail];arr[tail]^=arr[head];arr[head]^=arr[tail];head++;tail--;}}String result=new String(arr);return result;}//方式二：循环每2*k的区间，截取转换为StringBuilder反转并拼接public String reverseStr2(String s, int k) {StringBuilder result=new StringBuilder();//开始位置int start=0;int length=s.length();while(start//位置kint mid=start+k-1>length-1?length-1:start+k-1;//位置2kint end=start+2*k-1>length-1?length-1:start+2*k-1;//截取前k个StringBuilder buf=new StringBuilder(s.substring(start,mid+1));//反转并拼接前k个result.append(buf.reverse());//拼接后k个result.append(s.substring(mid+1,end+1));//循环下一个2*k的区间start+=2*k;}return result.toString();}
}

剑指 Offer 05 (简单)替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

/*** 推荐第一种方式：空间复杂度O(n)*/
class Solution {//方式一：转换为字符数组，扩容数组并在数组上进行替换public String replaceSpace(String s) {//1.扩容：找到s串的空格，每个空格增加两个空格StringBuilder buf=new StringBuilder();for(int i=0;iif(' '==s.charAt(i)) buf.append("  ");}//2.判断：没有空格直接返回if(buf.length()==0) return s;//3.将扩容的空格添加到s串尾部s+=buf.toString();//4.双指针替换char[] result=s.toCharArray();int head=result.length-buf.length()-1;int tail=result.length-1;while(head!=tail){if(result[head]==' '){head--;result[tail--]='0';result[tail--]='2';result[tail--]='%';}else{result[tail]=result[head];head--;tail--;}}return new String(result);}//方式二：遍历寻找+拼接//直接遍历拼接：最简单public String replaceSpace2(String s) {StringBuilder result=new StringBuilder();for(int i=0;iif(' '==s.charAt(i)){result.append("%20");}else{result.append(s.charAt(i));}}return result.toString();}//自己写的：使用string类的方法，给复杂化了//使用indexOf(String,int)public String replaceSpace3(String s) {StringBuilder result=new StringBuilder();int start=0;int local=0;while((local=s.indexOf(" ",start))!=-1 && startresult.append(s.substring(start,local));result.append("%20");start=local+1;}//start-s.length() 找不到空格的情况result.append(s.substring(start,s.length()));return result.toString();}
}

151 (中等)翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

• 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

• 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

/***	方法一：1.去除首尾空字符及中间多余空格 2.反转字符串 3.反转单词*	方法二：使用substring，空间复杂度O(n),不建议*///方法一：1.去除首尾及多余空格 2.反转字符串 3.反转单词
class Solution {public String reverseWords2(String s) {//1.去除首尾及多余空格StringBuilder sb=trimStrengthen(s);//2.反转字符串reverseStr(sb,0,sb.length()-1);//3.反转单词reverseWord(sb);return sb.toString();}//1.去除首尾及多余空格private StringBuilder trimStrengthen(String s){StringBuilder sb=new StringBuilder();int len=s.length();int start =0;int end=len-1;//定位s串第一个非空索引：出除头部空格while(s.charAt(start)==' ') start++;//定位s串最后一个非空字符索引：去除尾部空格while(s.charAt(end)==' ') end--;//将start-end中的字符进行添加：去除中间多余空格while(start<=end){char c=s.charAt(start);if(c!=' ' || sb.charAt(sb.length()-1)!=' ') sb.append(c);start++;}return sb;}//2.反转字符串 private void reverseStr(StringBuilder sb,int startIndex,int endIndex){while(startIndexchar c=sb.charAt(startIndex);sb.setCharAt(startIndex,sb.charAt(endIndex));sb.setCharAt(endIndex,c);startIndex++;endIndex--;}}//3.反转单词private void reverseWord(StringBuilder sb){int start=0;int end=start+1;while(end//遇到空格，反转前面的单词if(sb.charAt(end)==' '){reverseStr(sb,start,end-1);start=end+1;end=start+1;continue;}//是最后一个单词找不到空格了，反转最后一个单词if(end==sb.length()-1){reverseStr(sb,start,end);return;}end++;}}
}
//方法二：逻辑比较复杂
//substring 申请了额外空间O(n),不建议使用
class Solution {public String reverseWords(String s) {char[] arr=s.toCharArray();int len=s.length();StringBuilder sb=new StringBuilder();//定位单词的尾索引int tail=-1;//是否是第一个单词boolean isFirst=true;//1.从尾部开始遍历字符for(int i=len-1;i>=0;i--){//2.是非空字符，且是单词尾字符if(' '!=s.charAt(i) && tail==-1){//2.1 不是第一个单词，添加空字符if(!isFirst){sb.append(" ");}//2.2 是第一个单词，改变变量值else{isFirst=false;}//2.3 保存尾字符索引tail=i;}//3.是空字符，且存在单词尾索引if(' '==s.charAt(i) && tail!=-1){//3.1 截取单词并添加sb.append(s.substring(i+1,tail+1));//3.2 重置单词尾索引tail=-1;}//4.是最后一个字符，且存在单词尾索引if(i==0 && tail!=-1){//4.1 截取最后一个单词sb.append(s.substring(0,tail+1));}}return sb.toString();}
}

剑指 Offer 58 - II (简单)左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

class Solution {//方式一：整体反转+局部反转public String reverseLeftWords(String s, int n) {char[] arr=s.toCharArray();//1.整体反转int start=0;int end=s.length()-1;while(startarr[start]^=arr[end];arr[end]^=arr[start];arr[start]^=arr[end];start++;end--;}//2.局部反转start=0;end=arr.length-n-1;while(startarr[start]^=arr[end];arr[end]^=arr[start];arr[start]^=arr[end];start++;end--;}start=arr.length-n;end=arr.length-1;while(startarr[start]^=arr[end];arr[end]^=arr[start];arr[start]^=arr[end];start++;end--;}return new String(arr);}//方式二：保存前n个字符+后面字符前移+n个字符添加到末尾//使用substring，空间复杂度O(n)，不建议public String reverseLeftWords1(String s, int n) {char[] arr=s.toCharArray();//1.保存前n个字符String buf=s.substring(0,n);//2.将后部分字符串前移int before=0;int after=n;while(afterarr[before]^=arr[after];arr[after]^=arr[before];arr[before]^=arr[after];before++;after++;}//3.将前n个字符添加到末尾for(int i=0;iarr[before]=buf.charAt(i);before++;}return new String(arr);}
}

28 (中等)实现 strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

/*** 面试题：当 needle 为null时，应该返回什么？0*/
class Solution {//方法一：KMPpublic int strStr(String haystack, String needle) {//1.获取next数组int[] next=new int[needle.length()];getNext(next,needle);int j=0;for(int i=0;iwhile(j>0 && haystack.charAt(i)!=needle.charAt(j)){j=next[j-1];}if(haystack.charAt(i)==needle.charAt(j)){j++;}if(j==needle.length()) return i+1-needle.length();}return -1;}private void getNext(int next[],String str){int j=0;next[0]=0;for(int i=1;i//如果前缀与后缀匹配不成功：则前缀往前遍历，通过next数组查找可能与后缀相同的元素while(j>0 && str.charAt(i)!=str.charAt(j)){j=next[j-1];}//如果前缀与后缀匹配成功：则前缀与后缀都后移，继续匹配并叠加公共子串的长度if(str.charAt(i)==str.charAt(j)){j++;}next[i]=j;}}//方法二：蛮力法public int strStr2(String haystack, String needle) {int hlen=haystack.length();int nlen=needle.length();for(int i=0;iint j=0;while(jif(haystack.charAt(i+j)!=needle.charAt(j)) break;if(j==nlen-1) return i;j++;}}return -1;}
}

459 (简单)重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

//方法一：KMP
class Solution {public boolean repeatedSubstringPattern(String s) {int len=s.length();int[] next=new int[len];int j=0;for(int i=1;iwhile(j>0 && s.charAt(i)!=s.charAt(j)) j=next[j-1];if(s.charAt(i)==s.charAt(j)) j++;next[i]=j;}int l=len-next[len-1];//注意排除无公共子串的情况if(len%l==0 && l!=len) return true;else return false;}
}