19旋转词
20 单词的翻转
21神奇的回文串
package Demo16; /** * 5.10 题解：神奇的回文串 * 1000到999回文数 * @param args */ public class 字符串专题十 { public boolean isPalindrame(String src) { if(src.isEmpty()) { return true; } return src.equals(new StringBuilder(src).reverse().toString()); } static void polindromeNumber() { for (int i = 1; i <10; i++) { for (int j = 0; j < 10; j++) { /** * */ System.out.println(i*1000+j*100+j*10+i); } } } public static void main(String[] args) { // TODO Auto-generated method stub polindromeNumber(); } }
22最短摘要的生成
package Demo16; import java.util.Arrays; import java.util.HashMap; import java.util.Map; /** * 5.11 题解：最短摘要的生成 * @author MZFAITHDREAM * */ public class 字符串专题十一 { public static void main(String[] args) { solve1(new String[]{"a", "b", "c", "seed", "h", "e", "f", "c", "c", "seed", "e", "f", "seed", "c"}, new String[]{"c", "e"}); solve2(new String[]{"a", "b", "c", "seed", "c", "e", "f", "c", "c", "seed", "e", "f", "seed", "c"}, new String[]{"c", "c", "e", "f"}); solve2(new String[]{"a", "b", "a", "a", "b", "c", "d", "h", "e", "f", "f"}, new String[]{"b", "c", "d"}); } /** * 所搜关键字 * @param w * @param q */ public static void solve1(String[] w, String[] q) { int length = Integer.MAX_VALUE; int begin = -1; int end = -1; for (int i = 0; i < w.length; i++) { // 求以i开头包含所有关键字的序列 for (int j = i+1; j < w.length; j++) { // 如果全部关键字已经再seq中。 if (containsAll(q,w,i,j)) { // 判断当前这个序列是不是较短的序列 // System.out.println(seq); if (j-i+1<length) { length = j-i+1; begin = i; end = j; } break; } } } print(w,begin,end); } /** * 这种解法解决了keys关键字中有重复的现象 * @param w * @param keys */ public static void solve2(String[] w, String[] keys) { Arrays.sort(keys); // begin和end用于在找到更短的包含全部关键字的子数组时更新 int begin = -1; int end = -1; int j = -1; // 上一次囊括了所有关键字的右边界 int minLen = Integer.MAX_VALUE; for (int i = 0; i < w.length; i++) { // 如果i位置是关键字，求以i开头包含所有关键字的序列 String word1 = w[i]; int index = Arrays.binarySearch(keys, word1); if (-1==index) { continue; }else { // i是一个关键字 // 如果已经全部找到 if (j<w.length&&j>=i&&containsAll(keys, w, i, j)) { if (j-i+1<minLen) { // 更新 minLen = j-i+1; begin = i; end = j; } continue; } } if (j==-1) { j = j+1; // j值初始化 } while(j<w.length){ String word2 = w[j]; // 文章单词 int index1 = Arrays.binarySearch(keys, word2); if (-1==index1) { j++; continue; }else { // 找到关键字 这里应该是第一次扫描的包含所有关键字的 然后继续for循环不断更新边界 if (containsAll(keys, w, i, j)) { //全部到齐 if (j - i + 1 < minLen) {// 更新 minLen = j - i + 1; begin = i; end = j; } break; }else { j++; } } } } print(w, begin, end); } private static boolean containsAll(String[] keywords, String[] w, int i, int j) { Map<String, Integer> map = new HashMap<>(); for (int k = 0; k < keywords.length; k++) { String key = keywords[k]; if (map.get(key)==null) { map.put(key, 1); }else { map.put(key, map.get(key)+1); } } Map<String, Integer> map2 = new HashMap<>(); for (int k = i; k <= j; k++) { String key = w[k]; if (map2.get(key)==null) { map2.put(key, 1); }else { map2.put(key, map2.get(key)+1); } } for(Map.Entry<String, Integer> e:map.entrySet()){ if (map2.get(e.getKey())==null||map2.get(e.getKey())<e.getValue()) { return false; } } return true; } private static void print(String[] w, int begin, int end) { System.out.println(begin+" "+end); for (int i = begin; i <=end; i++) { System.out.print(w[i]+" "); } System.out.println(); } }
23 字符串匹配之RabinKarp（上）
package Demo17; /** * * @author MZFAITHDREAM *5.12 字符串匹配之RabinKarp（上） */ public class 字符串专题十二 { public static void main(String[] args) { String s="ABABABA"; String P="ABCDEF"; new 字符串专题十二().match(P, s); } private static void match(String p,String s) { long hash_p=hash(p); int p_len=p.length(); for (int i = 0; i+p_len <= s.length(); i++) { long hash_i=hash(s.substring(i,i+p_len)); if(hash_i==hash_p) { System.out.println("match"+i); } } } private static long hash(String p) { // TODO Auto-generated method stub return 0; } }
24字符串匹配之后缀数组(上)
package Demo17; /** * @author MZFAITHDREAM * Next数组 * 5.16 字符串匹配之后缀数组(上) * */ public class 字符串专题是13 { public static void main(String[] args) { // TODO Auto-generated method stub String src="babababcbabababb"; int index=indexOf(src,"bababbcdf"); //index =indexOf(src,"bababb"); System.out.println(index); } private static int indexOf(String s, String p) { // TODO Auto-generated method stub if(s.length()==0||p.length()==0) return -1; if(p.length()>s.length()) return -1; int [] next=next(p); int i=0; int j=0; int slen=s.length(); int plen=p.length(); while(i<slen) { if(j==-1||s.charAt(i) ==p.charAt(j)) { i++; j++; }else { j=next[j]; } if(j==plen) { return(i-j); } } return -1; } private static int[] next(String ps) { int plength =ps.length(); int [] next=new int[plength]; char[] p=ps.toCharArray(); next[0]=-1; if(ps.length()==1) return next; next[1]=0; int j=1; int k=next[j]; while(j<plength-1) { if(k<0 ||p[j]==p[k]) { next[++j] =++k; } else { k=next[k]; } } return next; } }
25字符串匹配之KMP(上)
package Demo17; import java.util.List; public class 字符串专题十四 { /** * 5.14 字符串匹配之KMP(上) * @param args * KMPS 思路 */ /** * 暴力解发 * @param args */ public static void main(String[] args) { String src="babababcbabababb"; int index=indexOf(src,"bababb"); System.out.println("暴力破解法解决问题：======"); System.out.println(index); System.out.println("------------------------"); } /** * @i="原数组的指针 * 暴力破解法 * @param src * @param key * @return */ private static int indexOf(String s,String p) { int i=0; int sc=i; int j=0; while(sc<s.length()) { if(s.charAt(sc)==p.charAt(j)) { sc++; j++; if(j==p.length()) return i; } else { i++; sc=i; //以i为起点 j=0; //j为0 } } return -1; } }
26字符串匹配之KMP(下)
package Demo17; /** * 5.15 字符串匹配之KMP(下) * @author MZFAITHDREAM * */ public class 字符串专题十五 { public static void main(String[] args) { // TODO Auto-generated method stub String src="babababcbabababb"; int index=indexOf(src,"baba"); //index =indexOf(src,"bababb"); System.out.println(index); } private static int indexOf(String s, String p) { // TODO Auto-generated method stub if(s.length()==0||p.length()==0) return -1; if(p.length()>s.length()) return -1; int count=0; int [] next=next(p); int i=0; int j=0; int slen=s.length(); int plen=p.length(); while(i<slen) { if(j==-1||s.charAt(i) ==p.charAt(j)) { i++; j++; }else { j=next[j]; } if(j==plen) { count++; i--; j=next[j-1]; //return(i-j); } } return count; } private static int[] next(String ps) { int plength =ps.length(); int [] next=new int[plength]; char[] p=ps.toCharArray(); next[0]=-1; if(ps.length()==1) return next; next[1]=0; int j=1; int k=next[j]; while(j<plength-1) { if(k<0 ||p[j]==p[k]) { next[++j] =++k; } else { k=next[k]; } } return next; } }
27 字符串应用：尺取法例题。
package Demo17; import java.util.Scanner; public class 字符串专题19 { /** * 5.19 字符串应用：尺取法例题 * @param args * 尺取法 */ public static void main(String[] args) { //1.输入字符串 Scanner sc = new Scanner(System.in); char[] w = sc.next().toCharArray();//2.遍历字符串 int min = Integer.MAX_VALUE;//存放当前仅包含2个h、1个i、1个o的最短子串长度 int j=-1;//子数组的尾坐标 for(int i=0;i<w.length;i++) { char w1 = w[i]; if(check(w1)) {//该字符合法，找到当前子数组的第一个位置i，接着j向后查找 if(j==-1) {//j的第一次定位 j=i+1; } //从j开始循环，找到合适的子数组 while(j<w.length) { char w2 = w[j]; if(check(w2) && containAll(w, i, j)) { //如果当前字符合法，并且包含所有字符（出现次数一致），则判断当前子数组是否小于当前最小子数组长度 if(checkAll(w, i, j) && j-i+1 < min) { min = j-i+1; } break;//完成一次查找，接着查找下一个合法子数组(注意，只要包含2个h、1个i、1个o，就退出，出现次数超了也要退出) } j++; }//while }//if }//for //3.输出最小的子数组长度 System.out.println(min==Integer.MAX_VALUE?-1:min); } //1.判断字符c是不是合法，即是不是h、i或o private static boolean check(char c) { return c=='h' || c=='i' || c=='o'; } //2.判断数组w从下标i到下标j中 是否包含2个h，1个i 和 一个o，不能多也不能少 private static boolean checkAll(char[] w,int i,int j) { int c1=0,c2=0,c3=0; for(int k=i;k<=j;k++) { if(w[k]=='h') c1++; if(w[k]=='i') c2++; if(w[k]=='o') c3++; } return c1==2 && c2==1 && c3==1; } //3.判断数组w从下标i到下标j中 是否包含2个h，1个i 和 一个o，可以超 private static boolean containAll(char[] w,int i,int j) { int c1=0,c2=0,c3=0; for(int k=i;k<=j;k++) { if(w[k]=='h') c1++; if(w[k]=='i') c2++; if(w[k]=='o') c3++; } return c1>=2 && c2>=1 && c3>=1; } }
这才是一部分String用法的展示。还有一些要读者自己去学习。
