笔试遇到的难题，求大神给个思路

递归，你看 O只有ZERO ONE TWO FOUR 有
只有Six 包含 X
只有zero 包含Z
只有eight 包含 G
只有two包含W
three 包含h
FIVE SEVEN 包含V
one nine 其余的
先遍历字符串，找这几个只包含某个单词的字符，有的话，直接提取出来这个单词，字符串移除掉这个单词，后面就是遍历了，如果找到V那就直接匹配Five ，后面发现匹配不出单词再退回来匹配Seven ，有点类似栈。自然一开始就可以递归遍历，不用分类处理，但是算法效率很低，这样效率高很多，差个几百倍的样子，
类似问题不好下手就是先处理特殊的，在处理通配的，

import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;
public class Test{
public static void main(String[] args){
String content = Source.getContent();
System.out.println(content);
Source.analyze(content);
}
}class Source{
public static String getContent(){
Random random = new Random();
initDatas();
int count = random.nextInt(datas.size()) + 1;
StringBuffer buffer = new StringBuffer();
for(int i = 0 ; i < count ; i ++){
//随机获取字符串组合
buffer.append(datas.remove(random.nextInt(datas.size())));
}
initDatas();
//对结果进行打乱
String result = disrupted(buffer.toString());
return result;
}
public static void analyze(String disrupted){
//获取data中最长字符串长度
int maxLength = Integer.MIN_VALUE;
for(String str : datas){
if(maxLength < str.length()){
maxLength = str.length();
}
}
int minCount = disrupted.length() / maxLength;
int maxCount = datas.size();
String ascending = getAscending(disrupted);
group(datas,ascending,minCount,maxCount);
} private static void group(ArrayList<String> datas,String ascending,int minCount,int maxCount){
for(int count = minCount ; count <= maxCount ; count ++){
group(datas,ascending,0,count,new String[count]);
}
} private static void group(ArrayList<String> datas,String ascending,int index,int count,String[] result){
if(index == count){
String condition = getCondition(result);
if(condition.equals(ascending)){
for(String str : result){
System.out.printf("'%s' ",str);
}
System.out.println();
System.exit(0);
}
return;
}
String perCondition = null;
for(int i = 0 ; i < datas.size() ; i ++){
perCondition = datas.get(i);
if(!filter(ascending,perCondition)){
//如果不可能含有某个字符串的可能性直接跳过
continue;
}
result[index] = perCondition;
group(datas,ascending,index + 1,count,result);
}
} private static boolean filter(String ascending,String perCondition){
//过滤器,用于判断是否含有某个子字符串的可能性.
//加快对于ascending判断是否含有该字符串的可能性.
perCondition = getAscending(perCondition);
String regex = perCondition.replaceAll("(?<=\\w)|(?=\\w)","(.*?)");
return ascending.matches(regex);
} private static String getCondition(String[] array){
//此方法用于对提供的数组中的元素进行组合并升序返回
StringBuffer buffer = new StringBuffer();
for(String str : array){
buffer.append(str);
}
return getAscending(buffer.toString());
}
//升序排列字符串
private static String getAscending(String content){
String[] array = content.split("(?<=\\w)(?=\\w)");
ArrayList<String> list = new ArrayList<>();
for(String str : array){
list.add(str);
}
Collections.sort(list);
StringBuffer buffer = new StringBuffer();
for(String str : list){
buffer.append(str);
}
return buffer.toString();
}

//打乱字符串
private static String disrupted(String source){
String[] array = source.split("(?<=\\w)(?=\\w)");
ArrayList<String> list = new ArrayList<>();
for(String str : array){
list.add(str);
}
Random random = new Random();
StringBuffer buffer = new StringBuffer();
while(list.size() > 0){
buffer.append(list.remove(random.nextInt(list.size())));
}
return buffer.toString();
} private static void initDatas(){
String[] array = {"ZERO","ONE","TWO","THREE","FOUR","FIVE","SIX","SEVEN","EIGHT","NINE"};
for(String str : array){
datas.add(str);
}
} private static ArrayList<String> datas = new ArrayList<>();
}

1）将每个单词存放到list中，所以多个单词就是list数组。同时将所有list的大小放到一个int数组中。
2）将打乱的字符串放到一个list中。得到其长度size
3）找出int数组中元素想加等于size的所有组合。
3.1）若找到，则将list数组中对应的list合并，并与第二步的list比较。

1000 条数据用时: 0ms
1w 条数据用时: 1~2ms
10w 条数据用时: 10ms以内
100w 条数据用时: 40~25ms
1000w 条数据用时: 1000~260ms (主要是分配连续的大块内存空间耗时)
import java.util.Arrays;
import java.util.Random;public class NumberString {
    final static Random random = new Random();
    private static void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }    static int indexOfNumber(String val) {
        char[] index = key_array[val.charAt(0) - 'A'];
        if (index.length == 1) return index[0];
        for (char c : index) {
            if (number[c].equals(val))
                return c;
        }
        return 0;
    }    public static void main(String[] args) {
//        int[] ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 测试数字
//        int[] ints = {0, 0, 0, 0, 0, 0}; // 测试数字
//        int[] ints = {9, 9, 9, 9, 9, 9, 9}; // 测试数字
//        int[] ints = {2, 0, 1, 6, 0, 9, 2, 8}; // 测试数字
//        int[] ints = {2, 0, 1, 6, 0, 9, 2, 8, 1, 1, 2, 3, 3, 3, 3, 5, 6, 7, 7, 7, 8}; // 测试数字
        // 性能测试
        int[] ints = new int[1000000];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = random.nextInt(10);
        }        StringBuilder words = new StringBuilder();
        for (int i : ints) {
            words.append(number[i]).append(",");
        }
//        System.out.println("未打乱顺序(数字)---->" + Arrays.toString(ints));
//        System.out.println("未打乱顺序---->" + words.deleteCharAt(words.length() - 1).toString());
        // 打乱顺序
        char[] values = words.toString().replace(",", "").toCharArray();
        for (int i = values.length; i > 1; i--) {
            swap(values, i - 1, random.nextInt(i));
        }
//        System.out.println("打乱顺序后---->" + new String(values));
        // 以上是准备数据
        // ---------------------------------------------------------------
        long start = System.currentTimeMillis();
        String[] result = new NumberString().revert(new String(values));
        System.out.println(ints.length + " 条数据用时: " + (System.currentTimeMillis() - start));
        // ---------------------------------------------------------------
        // 以上是还原数据
//        System.out.println("恢复结果---->" + Arrays.toString(result));        // 以下为了检测结果的正确性
        int[] numbers = new int[result.length];
        for (int i = 0; i < result.length; i++) {
            numbers[i] = indexOfNumber(result[i]);
        }
//        System.out.println("恢复结果(数字)---->" + Arrays.toString(numbers));        // 便于比较两个数组是否相等先将两个数组进行排序
        Arrays.sort(ints);
        Arrays.sort(numbers);
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] != numbers[i]) {
                System.out.println("结果不正确.");
                System.exit(1);
            }
        }
        System.out.println("结果正确.");
    }//------------------------------------------------------------------------------------------------
//                                          以下是还原逻辑
//------------------------------------------------------------------------------------------------
    final static String[] number = {"ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE"};
    static final char[] base_array = {0, 0, 0, 0, 9, 2, 1, 2, 4, 0, 0, 0, 0, 4, 4, 0, 0, 3, 2, 3, 1, 2, 1, 1, 0, 1};
    static final char[][] key_array = {null, null, null, null, new char[]{0, 1, 3, 5, 7, 8, 9}, new char[]{4, 5}
            , new char[]{8}, new char[]{3, 8}, new char[]{5, 6, 8, 9}, null, null, null, null, new char[]{1, 7, 9}
            , new char[]{0, 1, 2, 4}, null, null, new char[]{0, 3, 4}, new char[]{6, 7}, new char[]{2, 3, 8}
            , new char[]{4}, new char[]{5, 7}, new char[]{2}, new char[]{6}, null, new char[]{0}};    /**
     * 还原
     *
     * @param str
     * @return
     */
    public String[] revert(String str) {
        int[] count_str = new int[26];
        for (char c : str.toCharArray())
            count_str[c - 'A']++;
        String[] numArray = new String[10];
        int index = 0;
        for (int i = 4; i < count_str.length; i++) {
            if (count_str[i] == 0 || base_array[i] != 1)
                continue;
            char[] key_index = key_array[i];
            String[] words = singleMultiply(count_str, key_index[0], count_str[i]);
            numArray = append(numArray, index, words);
            index += words.length;
        }
        if (!hasNumber(count_str))
            return Arrays.copyOf(numArray, index);
        String[] words = dolast(count_str);
        numArray = append(numArray, index, words);
        index += words.length;
        return Arrays.copyOf(numArray, index);
    }    String[] dolast(int[] count_str) {
        String[] subArray = new String[10];
        int index = 0;
        while (hasNumber(count_str))
            for (int i = count_str.length - 5; i >= 4; i--) {
                if (count_str[i] == 0) continue;
                String[] substring = multiply(count_str, key_array[i], count_str[i]);
                if (substring == null) continue;
                if (subArray.length <= index || subArray.length - index < substring.length) {
                    subArray = resize(subArray, sum(count_str) >>> 1);
                }
                for (String str : substring) subArray[index++] = str;
            }
        return Arrays.copyOf(subArray, index);
    }    String[] multiply(int[] count_str, char[] key_index, int size) {
        String[] words = new String[size];
        _tp: for (int i = 0; i < key_index.length; i++) {
            int[] cp_count_str = count_str.clone();
            String word = number[key_index[i]];
            for (char _c : word.toCharArray()) {
                cp_count_str[_c - 'A'] -= size;
                if (cp_count_str[_c - 'A'] < 0)
                    continue _tp;
            }
            System.arraycopy(cp_count_str, 0, count_str, 0, count_str.length);
            for (int j = 0; j < size; j++)
                words[j] = word;
            break;
        }
        if (words[0] == null || words[0].length() == 0)
            return null;
        return words;
    }    boolean hasNumber(int[] count_str) {
        for (int i : count_str) {
            if (i > 0) return true;
        }
        return false;
    }    int sum(int[] count_str) {
        int sum = 0;
        for (int i : count_str)
            sum += i;
        return sum;
    }    String[] resize(String[] subArray, int appendLength) {
        int size = subArray.length + appendLength;
        String[] _subArray = new String[size];
        System.arraycopy(subArray, 0, _subArray, 0, subArray.length);
        return _subArray;
    }    String[] singleMultiply(int[] count_str, char key_index, int size) {
        String[] words = new String[size];
        String word = number[key_index];
        for (char _c : word.toCharArray()) {
            count_str[_c - 'A'] -= size;
        }
        for (int i = 0; i < size; i++)
            words[i] = word;
        return words;
    }    String[] append(String[] buf, int fromIndex, String... values) {
        if (values == null || values.length <= 0)
            return buf;
        int bl = buf.length, vl = values.length;
        if (bl < fromIndex + vl) {
            int l = bl > vl ? bl : vl;
            buf = resize(buf, l);
        }
        for (String str : values)
            buf[fromIndex++] = str;
        return buf;
    }
}

换一个思路其实不用保存字符串，只需要知道原来的数字是由多少个0多少个1组成，还原后有多少个0多少个1即可。比较起来也比较方便。1千万数字还原均在10ms以内
import java.util.Random;public class NumberString {
    final static Random random = new Random();    private static void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }    public static void main(String[] args) {
        int[] total = new int[10];
//        int[] ints = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 测试数字
//        int[] ints = {0, 0, 0, 0, 0, 0}; // 测试数字
//        int[] ints = {9, 9, 9, 9, 9, 9, 9}; // 测试数字
//        int[] ints = {2, 0, 1, 6, 0, 9, 2, 8}; // 测试数字
//        int[] ints = {2, 0, 1, 6, 0, 9, 2, 8, 1, 1, 2, 3, 3, 3, 3, 5, 6, 7, 7, 7, 8}; // 测试数字
        // 性能测试
        int[] ints = new int[10000000];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = random.nextInt(10);
        }        StringBuilder words = new StringBuilder();
        for (int i : ints) {
            total[i]++;
            words.append(number[i]).append(",");
        }
        System.out.println("未打乱前包含---->");
        for (int i = 0; i < total.length; i++) {
            System.out.print(total[i] + "个" + new String(number[i]) + " ");
        }
        System.out.println();        // 打乱顺序
        char[] values = words.toString().replace(",", "").toCharArray();
        for (int i = values.length; i > 1; i--) {
            swap(values, i - 1, random.nextInt(i));
        }
//        System.out.println("打乱顺序后---->" + new String(values));
        // 以上是准备数据
        // ---------------------------------------------------------------
        long start = System.currentTimeMillis();
        int[] result = new NumberString().revert(values);
        System.out.println(ints.length + " 条数据用时: " + (System.currentTimeMillis() - start));
        // ---------------------------------------------------------------
        // 以上是还原数据
        System.out.println("恢复结果---->");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + "个" + new String(number[i]) + " ");
        }
        System.out.println();        for (int i = 0; i < total.length; i++) {
            if (total[i] != result[i]) {
                System.out.println("还原错误.");
                System.exit(1);
            }
        }
        System.out.println("还原正确.");
    }//------------------------------------------------------------------------------------------------
//                                          以下是还原逻辑
//------------------------------------------------------------------------------------------------
    final static char[][] number = {{'Z','E','R','O'},{'O','N','E'},{'T','W','O'},{'T','H','R','E','E'}
    ,{'F','O','U','R'},{'F','I','V','E'},{'S','I','X'},{'S','E','V','E','N'},{'E','I','G','H','T'},{'N','I','N','E'}};
    static final char[] base_array = {0, 0, 0, 0, 9, 2, 1, 2, 4, 0, 0, 0, 0, 4, 4, 0, 0, 3, 2, 3, 1, 2, 1, 1, 0, 1};
    static final char[][] key_array = {null, null, null, null, new char[]{0, 1, 3, 5, 7, 8, 9}, new char[]{4, 5}
            , new char[]{8}, new char[]{3, 8}, new char[]{5, 6, 8, 9}, null, null, null, null, new char[]{1, 7, 9}
            , new char[]{0, 1, 2, 4}, null, null, new char[]{0, 3, 4}, new char[]{6, 7}, new char[]{2, 3, 8}
            , new char[]{4}, new char[]{5, 7}, new char[]{2}, new char[]{6}, null, new char[]{0}};    /**
     * 还原
     *
     * @param values
     * @return
     */
    public int[] revert(char[] values) {
        int[] count_str = new int[26], result = new int[10];
        for (char c : values)
            count_str[c - 'A']++;
        for (int i = 4; i < count_str.length; i++) {
            if (count_str[i] == 0 || base_array[i] != 1)
                continue;
            singleMultiply(count_str, key_array[i][0], count_str[i], result);
        }
        if (hasNumber(count_str)) {
            dolast(count_str, result);
        }
        return result;
    }    void dolast(int[] count_str, int[] result) {
        while (hasNumber(count_str))
        for (int i = count_str.length - 5; i >= 4; i--) {
            if (count_str[i] == 0) continue;
            boolean boo = multiply(count_str, key_array[i], count_str[i], result);
            if (!boo) continue;
        }
    }    boolean multiply(int[] count_str, char[] key_index, int size, int[] result) {
        boolean boo = false;
        _tp:for (int i = 0; i < key_index.length; i++) {
            int[] cp_count_str = count_str.clone();
            char[] word = number[key_index[i]];
            for (char _c : word) {
                cp_count_str[_c - 'A'] -= size;
                if (cp_count_str[_c - 'A'] < 0)
                    continue _tp;
            }
            boo = true;
            System.arraycopy(cp_count_str, 0, count_str, 0, count_str.length);
            result[key_index[i]] += size;
            break;
        }
        return boo;
    }    boolean hasNumber(int[] count_str) {
        for (int i : count_str) {
            if (i > 0) return true;
        }
        return false;
    }    void singleMultiply(int[] count_str, char key_index, int size, int[] result) {
        char[] word = number[key_index];
        for (char _c : word) {
            count_str[_c - 'A'] -= size;
        }
        result[key_index] += size;
    }
}

6666,大神们真的666，刚学完前端的java新手路过，觉得很强！

调试易

笔试遇到的难题，求大神给个思路

解决方案 »