- 一、字符替换
- 二、翻转字符串里的单词
- 三、左旋转字符串(剑指Offer)
- 四、实现strStr()
- 五、重复的子字符串
来源:leetcode
题目链接
创建StringBuilder对象(StringBuffer也可以),在遍历的时候进行判断,是空格则替换并加到StringBuilder后面,不是空格则直接加入
public static String replaceSpace(String s) { if (s==null){ return null; } StringBuilder str = new StringBuilder(); for (int i=0;i这种方式是普通方式,处理起来比较繁琐,还有一种双指针处理方式,这个是我在看别人文章时看到的处理方式,效果很不错
解题思路,我们先观察一下扩充和没扩充的长度差距解题思路,我们先观察一下扩充和没扩充的长度差距
We are happy. //13We%20are%20happy. //17长度差距4,而我们有两个空格,说明每有一个空格,就会多出两个空间,那我们可否直接计算出扩充至后需要多少空间,利用双指针,一个指向原有字符串尾部,一个指向扩充之后的尾部,对空间进行填充呢
public static String replaceSpace(String s) { if (s==null){ return null; } StringBuffer str = new StringBuffer(); for (int i=0;i二、翻转字符串里的单词=0){ if (cs[left]==' '){ cs[right--]='0'; cs[right--]='2'; cs[right]='%'; }else { cs[right]=cs[left]; } left--; right--; } return new String(cs); }
题目链接首先去掉字符串前后的空格,我们利用双指针算法,区分有空格和无空格的情况即可
public static String reverseWords(String s) { if (s==null){ return null; } String trim = s.trim(); StringBuilder str = new StringBuilder(); int left = trim.length()-1; int right = trim.length()-1; while (left>=0){ if (left>0&&' '==trim.charAt(left-1)){ str.append(trim.substring(left,right+1)); while (' '==trim.charAt(left-1)){ left--; } }else if (' '==trim.charAt(left)){ str.append(" "); left--; right=left; }else if (left==0){ str.append(trim.substring(left,right+1)); left--; } else { left--; } } return new String(str); }三、左旋转字符串(剑指Offer)
题目链接解题思路,不申请额外空间的情况下,我们采用小旋转->大旋转的思路,使每个局部进行翻转,以达到总体翻转的效果
public static String reverseLeftWords(String s, int n) { char[] chars = s.toCharArray(); //局部翻转 for (int i=0,j=n-1;i在leetcode题解中看到一个很骚的解题方式:直接取余
0.0public static String reverseLeftWords(String s, int n) { int len = s.length(); StringBuilder str = new StringBuilder(); for (int i=n;i四、实现strStr()
题目链接直接KMP算法解决
关于KMP算法的介绍使用请看我的上一篇博文KMP算法解决字符串匹配问题(详细步骤图解)
public static int strStr(String haystack, String needle){ if (needle.length()==0){ return 0; } int[] next = new int[needle.length()]; getNext(next,needle); for (int i=0,j=0;i五、重复的子字符串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-j+1; } } return -1; } private static void getNext(int[] next,String needle){ int len = needle.length(); next[0]=0; //ABCDABD for (int i=1,j=0;i 0&&needle.charAt(i)!=needle.charAt(j)){ j=next[j-1]; } if (needle.charAt(i)==needle.charAt(j)){ j++; } next[i]=j; } }
题目链接解题思路:遇到重复字符串的问题,可以考虑KMP算法,本题可以利用KMP中的next池求出最长子串的长度next[len-1],最长子串长度>0并且len%(len-next[len-1])=0则证明字符串可由其子串组成
public static boolean repeatedSubstringPattern(String s){ int len = s.length(); int[] next = new int[len]; getNext(next,s); //最长子字符串长度 int value = next[len-1]; return value>0?len%(len-value)==0:false; } //next池 public static void getNext(int[] next,String s){ next[0]=0; for (int i=1,j=0;i0&&s.charAt(i)!=s.charAt(j)){ j=next[j-1]; } if (s.charAt(i)==s.charAt(j)){ j++; } next[i]=j; } } 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)