541 反转字符串2

按照题目的意思来写就行，但是写了非常久，因为在string的基础上改是改不了的，string不是可以编辑的字符，要先转换成char[]数组，再在数组上改动，最后把char[]变为String

class Solution {public String reverseStr(String s, int k) {char[] arr = s.toCharArray();      for(int i=0;i// if(i+k//     rever(arr,i,i+k);// }else{//     rever(arr,i,arr.length); //剩下不足k的全部翻转// }rever(arr,i,Math.min(i+k,arr.length));}return new String(arr);}public void rever(char[] s, int begin, int end){for(int i=begin,j=end-1;i<=j;i++,j--){//记得是从begin开始end结束char t = s[i];s[i] = s[j];s[j] = t;}}
}

剑指offer 05 替换空格

这题太简单，两分钟解决

class Solution {public String replaceSpace(String s) {//37-39StringBuffer res = new StringBuffer();for(int i = 0;iif(s.charAt(i)==' ') res.append("%20");else res.append(s.charAt(i));}return res.toString();}
}

看了题解可以用双指针在原地进行修改，先把长度扩充到加入%20后的长度，然后从右往左赋值，这样的好处是不用额外的数组。但是这样的方法用Java行不通，因为java的string不能原地扩充，还是要用StringBuffer之后用双指针，那就失去了双指针的意义。

151 反转字符串中的单词

class Solution {public String reverseWords(String s) {//50-09String[] strs = s.split(" +");StringBuffer res = new StringBuffer();for(int i=strs.length-1;i>=0;i--){res.append(strs[i]);if(i>0) res.append(" ");}if(strs[0].equals("")){ //而不是" "！！ split方法无法去掉开头的空格，如果开头有空格，strs[0]为"",而不是" "res.deleteCharAt(res.length()-1);} return res.toString();}
}

下次直接用trim()函数去掉首尾的多个空格

class Solution {public String reverseWords(String s) {//50-09//先去掉首尾的多个空格s= s.trim();String[] strs = s.split(" +");StringBuffer res = new StringBuffer();for(int i=strs.length-1;i>=0;i--){res.append(strs[i]);if(i>0) res.append(" ");}return res.toString();}
}

28 找出字符串中第一个匹配的字符

暴力匹配很简单时间复杂度是O(mn)

class Solution {public int strStr(String haystack, String needle) {//32-47int res = -1;for(int i=0;iif(haystack.charAt(i)==needle.charAt(0)&&i+needle.length()<=haystack.length()){//第一个相同才会继续判断int f = 1;int start = i;for(int j=0;jif(haystack.charAt(start++)!=needle.charAt(j++)){//不同就跳出f = 0;break;}}if(f==1){return i;}}            }return res;}
}

最出名的字符串匹配算法是KMP算法，时间复杂度为O(m+n),关键在于维护一个Next数组，表示前缀和后缀相同的最长长度。

学了KMP算法，还是得把代码记一下
https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

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; }}
}

459 重复的子字符串

很明显这题也是用KMP算法，但是怎么转换呢，我一开始想的是next数组在最后一位的值如果大于等于长度的一半即可，提交了两次错误，因为并不一定是偶数个重复子串，还是看了题解的判断方法

1. 最后一位的next不为0，否则连重复都没有
2. 总长度是 剩余长度的整数倍，即

s.length()%(s.length()-next[s.length()-1])==0

class Solution {public boolean repeatedSubstringPattern(String s) {//50 求next数组 只要最后一位的next>=s.length()/2 即可int j = 0;int[] next = new int[s.length()];next[0] = 0;// if(s.length()==1) return true; 是falsefor(int i=1;iwhile(j>0&&s.charAt(j)!=s.charAt(i)) j = next[j-1];if(s.charAt(j)==s.charAt(i)) j++;next[i] = j;}//System.out.println(Math.ceil((double)3/2));要强制类型转换if(next[s.length()-1]!=0&&s.length()%(s.length()-next[s.length()-1])==0) return true;else return false;}
}

时间和空间复杂度都是O(N)