字符串相关

字符串1、 左旋转字符串2、计数二进制子串3、 回文串3.1、 验证回文串3.1、 最长回文子串 4、 求所有碎片的平均长度5、用于匹配模式串的KMP(Knuth-Morris-Pratt)算法5、滑动窗口

字符串

1、 左旋转字符串

不论是左旋转还是右旋转，即把前面的子串往后放还是后面的子串往前放，最简洁的方法都是先把原始串复制一份并拼接起来，然后按需截取。 本题链接在此，代码如下，可以将前面那个字符放到末尾：

public String reverseLeftWords(String s, int n) { String s1 = s + s; return s1.substring(n,s.length()+n); }

如若不能使用substring（）方法，则应使用StringBuilder来重新接受新次序的字符，最后组成一个符合要求的字符串。

方法二 public String reverseLeftWords(String s, int n) { StringBuilder sb = new StringBuilder(); for(int i = n;i < n + s.length();i++){ sb.append(s.charAt(i % s.length())); } return sb.toString(); }

2、计数二进制子串

这个题思路较多，我用的是官方的先将字符串连续相同的段计数，并将计数值储存起来，然后每相邻的两个计数值都能贡献Min{count[i],count[i+1]}次符合要求的子串。本题链接 计数并储存：

List<Integer> counts = new ArrayList<>(); int ptr = 0; int len = s.length(); while(ptr < len){ int cnt = 0; int tmp = s.charAt(ptr); while(ptr < len && tmp == s.charAt(ptr)){ ++ptr; ++cnt; } counts.add(cnt); }

然后统计总次数：

int res = 0; for (int i = 0; i < counts.size()-1; i++) { res += Math.min(counts.get(i),counts.get(i+1)); } return res;

3、 回文串

3.1、 验证回文串

首先，这个题有两个要求：1）只考虑字母和数字字符；2）忽略字母大小写 这里涉及到两个API，一个是包装类的Character.isLetterOrDigit(char a) ，用来判断a字符是否是字母或数字，是则返回true；另一个是Character.toLowerCase(char a)，用来将字符a转换成小写（当然用转换成大写的也可以）。 然后，这里需要一个新的容器来盛装“瘦身”后的字符串，这里选用的是StringBuider，得到新的字符串不妨即为sb串，到这里貌似只需要调用reverse()方法，然后返回两者equals()的值即可。 然而，却犯了两个基本的错误。 错误一：reverse()方法是在原始串上改动，一旦调用执行，原始串就找不到了。 解决方案：调用reverse()之前将原始串储存起来，但要注意新new一个对象，不然调用reverse()后会把唯一的对象反转，同样丢失了原始串。

错误二:StringBuilder类中没有重写equals()方法，调用后执行的是父类Object中的==，比较地址。 解决方案：调用toString()方法，转成String。 代码如下：

public static boolean isPalindrome(String s){ StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if(Character.isLetterOrDigit(s.charAt(i))){ sb.append(Character.toLowerCase(s.charAt(i))); } } StringBuilder sb1 = new StringBuilder(sb); sb.reverse(); return sb1.toString().equals(sb.toString()); }

3.1、 最长回文子串

题目链接 这题的思路就是先统计每一个字符出现的次数，并将次数按不同字符储存起来，然后每一个字符都可以最多使用count/2*2次（/为整数除法），最后若有奇数个的字符，应当加入一个当做中轴线，如此便可达到最长。 官方代码如下：

public int longestPalindrome(String s) { int[] count = new int[58]; for (char c: s.toCharArray()) count[c-'A']++;//从65-122共58个，中间91到96不用即可 int ans = 0; for (int v: count) { ans += v / 2 * 2; if (v % 2 == 1 && ans % 2 == 0) ans++; } return ans; }

4、 求所有碎片的平均长度

题目描述：一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,“aaabbaaac"是由下面碎片组成的:‘aaa’,‘bb’,‘c’。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的平均长度是多少。输入"aaabbaaac”，结果为(3+2+1) / 3 = 2.00。（说明：结果不取整） 此题与上一“最长回文子串”但实则是两种题目，本题每次统计的并不是所有相同字符的数目，比如用例中“aaa”有两个，但只需要一个，而且记为一段碎片。 代码如下：

public static void main(String[] args) { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); List<String> list = new ArrayList<String>(); if (s.length() < 2) { System.out.println(String.format("%.2f", s.length())); return ; } char pre_c = s.charAt(0), cur_c; StringBuffer sb = new StringBuffer(); sb.append(pre_c); for (int i = 1; i < s.length(); i++) { cur_c = s.charAt(i); if (cur_c == pre_c) { sb.append(cur_c); } else { list.add(sb.toString()); sb = new StringBuffer("" + cur_c); } pre_c = cur_c; } list.add(sb.toString()); Set<String> set = new HashSet<>(); for (String s1 : list) { set.add(s1); } int t_len = 0, t_num = 0; for (String s1 : set) { t_len += s1.length(); t_num++; } System.out.println(String.format("%.2f", t_len * 1.0 / t_num)); }

5、用于匹配模式串的KMP(Knuth-Morris-Pratt)算法

Knuth-Morris-Pratt分别代表三个科学家，以铭记他们的贡献。 所以该算法的内涵和名称KMP没有逻辑联系，算法的关键在于构建一个PMT（Partial Match Table，部分匹配数组），例如下方代码中的calPMTvalues（）方法，就是用来构建PMT的。PMT的原理及作用建议从此进入链接，最好多读几个回答，找一个自己能理解的，当然我觉得更为容易理解的方式是在纸面上一步一步推演完全。 得到PMT后，就可以在text中搜索pattern时，一旦遭遇不匹配，text可以不必回退索引，而pattern回退的位置值记录在PMT中，就可以达到O(n)(text长度为n，pattern长度为m)的时间复杂度。可以想象，如果不借助PMT，失配时将达到O(nm)。 代码如下：

/** * 用于搜索text中每一次出现Pattern串的位置（首索引） * @param text（主串） * @param pattern（模式串） * @return 返回一个装有所有位置值的List */ public List<Integer> search(String text,String pattern){ List<Integer> positions = new ArrayList<>(); // int[] PMT_value = new int[pattern.length()];//不建PMT表的话不能找出类似“ababab”，中“abab”的第二个位置 int[] PMT_values = calPMTValues(pattern); int count = 0;//指针 for (int i = 0; i < text.length(); i++) { while(count > 0 && text.charAt(i) != pattern.charAt(count)){ count = PMT_values[count - 1]; } if(text.charAt(i) == pattern.charAt(count)){ count++; } if(count == pattern.length()){ positions.add(i - pattern.length() + 1); count = PMT_values[count -1]; } } return positions; } /** * 用于计算PMT数组所有的值，每一个值代表截取的模式串的最长前、后缀集合的交集的最长子串的长度 * @param pattern * @return 返回PMT数组 */ public int[] calPMTValues(String pattern){ int[] PMT_values = new int[pattern.length()]; int maxlength = 0; for (int i = 1; i < pattern.length(); i++) { while(maxlength > 0 && pattern.charAt(maxlength) != pattern.charAt(i)){ maxlength = PMT_values[maxlength - 1];//如果不相等，当前maxlength值不断地用前面的PMT值进行赋值 } if(pattern.charAt(maxlength) == pattern.charAt(i)){ maxlength++;//如果相等，当前maxlength+1 } //并且将当前maxlength值赋给索引i处的PMT数组中 PMT_values[i] = maxlength; } return PMT_values; }

5、滑动窗口