问题描述
2个问题1.有一个邮箱，有一千万条黑名单用户，怎么判断收件箱是不是黑名单用户。据说和字典什么的是属于同一个经典问题。。2.求一个字符串中最长的颠倒字符串。。比如 a123ghfuhg321asd131.(就是a123,321a.)
解决方案
1.有一个邮箱，有一千万条黑名单用户，怎么判断收件箱是不是黑名单用户。 据说和字典什么的是属于同一个经典问题。。 这个肯定是用布隆过滤算法,楼主可以网上去找找算法. 用map的瓶颈就是内存.优点:对比用MAP来存储,内存需要量急剧减少.检索速度超快.缺点:会有一定的误判,会把不是黑名单的判断成黑名单.但是不会漏判断.2.求一个字符串中最长的颠倒字符串。。 比如 a123ghfuhg321asd131.(就是a123,321a.)这个问题不是几句话能搞明白,楼主可以看看这个博客.里面有大量的算法分析.http://blog.csdn.net/v_july_vhttp://blog.csdn.net/v_july_v/article/details/7041827
解决方案二：
public class Test {/** * @param args */public static void main(String[] args) {String a = "jha123ghfs343uhg321asd131";String str1 = null, str2 = null, tmpstr1 = null, tmpstr2 = null, maxstr1 = null, maxstr2 = null;for (int i = 0; i < a.length() - 2; i++) {for (int j = 2 + i; j < a.length() - 1; j++) {if (j > i) {str1 = a.substring(i, j);if (str1 != null && !str1.equals("") && str1.length() > 1) {str2 = (new StringBuilder(str1)).reverse().toString();if (a.indexOf(str2) == -1) {if (tmpstr1 != null && (maxstr1 == null || tmpstr1.length() > maxstr1.length())) {maxstr1 = tmpstr1;maxstr2 = tmpstr2;}break;} else {tmpstr1 = str1;tmpstr2 = str2;}}}}}System.out.println("字符串中最长的颠倒字符串:"+maxstr1 + "," + maxstr2);}}运行输出，字符串中最长的颠倒字符串:a123gh,hg321a
解决方案三：
第二道题codepackage com.test1;/** * 最大长颠倒字符串 它的长度应该小于等于整个字符串（长度为L）的的一半 * 从假设最大颠倒长度为整个的1/2L 然后查这个长度的颠倒字符串是否存在 存在就返回，不存在，则继续往下找1/2L-1,以此类推1/2L-1....一直到0。如果为0说明没有 * */public class ResStrLong {public static void main(String[] args) {String string="a123ghfuhg321asd131"; String revString=getLongString(string);} public static String getLongString(String string) { int maxStr=string.length()/2; int len=string.length(); String revString=null; boolean flag=false; for(int i=maxStr;i>=0;i--){ for (int j = 0; j <len; j++) { if((j+i+1)>(len-1))continue;String subString=string.substring(j,j+i+1); revString=new StringBuffer(subString).reverse().toString();int flag1=string.indexOf(revString);if(flag1!=-1){flag=true;System.out.println(subString+":"+revString+";"+i);break;}} if(flag)break; } return revString; }}
解决方案四：
第一个问题，用hash，把字符串转为数字去比对，数据的存储和查找都会比较快。第二个问题，回文问题，上网找吧！
解决方案五：
第一个问题应该是考，怎么存这一千万条数据，使判断是不是黑名单用户的耗时最少。这也是分词器字典需要使用的数据结构。之前看IK分词的词典是使用树结构存储的；父节点使用hashmap存储子节点对象；每个节点的值是一个char。http://blog.csdn.net/guwenwu285/article/details/9617057第二个http://blog.csdn.net/hopeztm/article/details/7932245的思路二的方法：package snippet;public class Solution {private static int[] next;private static void GetNext(String s)// KMP求next数组{int i, j;i = 0;j = -1;next[0] = -1;while (i < s.length()) {if (j == -1 || s.charAt(i) == s.charAt(j)) {i++;j++;next[i] = j;} else {j = next[j];}}}private static int compare(String pattern, String s) // 用KMP算法做求出最长的前缀匹配{int i, j;i = 0;j = 0;int maxLen = 0;while (i < s.length()) {if (j == -1 || pattern.charAt(j) == s.charAt(i)) {i++;j++;} else {j = next[j];}if (j > maxLen) {maxLen = j;}if (j == pattern.length()) {return maxLen;}}return maxLen;}public static String longestPalindrome(String s) //{// Start typing your Java solution below// DO NOT write main() functionString reverString = new StringBuilder(s).reverse().toString(); // 求得到// 输入string// 的reversenext = new int[s.length() + 1];String maxPal = "";int maxLen = 0;int len;for (int i = 0; i < s.length(); i++) // 枚举所有后缀{String suffix = reverString.substring(i);if (suffix.length() < maxLen) {break;}GetNext(suffix);len = compare(suffix, s);if (len > maxLen) {maxPal = suffix.substring(0, len);maxLen = len;}}return maxPal;}public static void main(String[] args) {System.out.println(longestPalindrome("a123ghfuhg321asd131"));System.out.println(longestPalindrome("a123ghuhg321asd131"));}}