数美科技前三题答案

第一题

 /*
     * 思路
     * 1.将keyword 存储到list 中
     * 2.按行读取到input中的数据每一行进行list匹配
     *
     *  这题通过abc查找的bc的时候，没有更好的优化思路 求解
     *
     * */
    public static void main(String[] args) {
        printResult("./input.txt" , "./keyword.conf");
    }

    public static void printResult(String inputPath, String keyword) {
        Set<String> conf = getKeyword(keyword);
        printResult(inputPath, conf);
    }

    /*
     * 匹配并输出打印输出
     * */
    private static void printResult(String inputFilePath, Set<String> keys) {
        try (FileInputStream inputStream = new FileInputStream(inputFilePath);
             BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream))) {
            String str;
            while ((str = bufferedReader.readLine()) != null) {
                //与每行的数据与keyword 进行匹配 求解更优的算法
                for (String key : keys) {
                    if (str.split(" ")[0].contains(key)) {
                        System.out.println(str);
                        break;
                    }
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /*
     * 存储keyword
     * */
    private static Set<String> getKeyword(String filePath) {
        Set<String> set = new HashSet<>();
        try (FileInputStream inputStream = new FileInputStream(filePath);
             BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream))) {
            String str;
            while ((str = bufferedReader.readLine()) != null)
                set.add(str);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return set;
    }

第二题

    /*
     * 思路
     *
     * 创建一个大小为1000 int数组
     * 其中 int[0] 代表 0—99
     * 其中 int[1] 代表 100—199
     * 其中 int[2] 代表 200—299
     * ……
     * 依次类推
     * 时间复杂为 O(n)
     * */
    public static void main(String[] args) {
        printResult("./input.txt");
    }

    private static void printResult(String filePath) {
        int n = 100000;
        int m = 100;
        int[] memo = new int[n / m];
        storageResult(memo, filePath);
        int temp;
        for (int i = 0; i < memo.length; i++) {
            temp = i * 100;
            System.out.println(temp + "—" + (temp + 99) + " " + memo[i]);
        }
    }

    private static void storageResult(int[] memo, String inputFilePath) {
        try (FileInputStream inputStream = new FileInputStream(inputFilePath);
             BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream))) {
            String str;
            while ((str = bufferedReader.readLine()) != null) {
                memo[Integer.parseInt(str) / 100]++;
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

第三题

    /*
     *思路
     * 按行读取每一条数据，将该数据以Map的方式形如下图
     *
         cn             com
                    /       /           \
      com     baidu tencent
       /
      sina
       /
      sports
      将数据进行压缩
      将"roll.sports.sina.com.cn"
      解析为 数组 先找到 cn 的 HashMap 查看是否存在 tempMap，
      在tempMap中查找key为com的HashMap，
      如此查找下去，知道查找的key 不存在，输出找到的结果。

     由于 数据量比较大，可以将通过Hash的方式将数据存储在多个机器上，例如com 和cn，结尾的数据比较多，可以将其分配2台甚至多台机器处理，或者内存更大的机器
     基本的思路还是不变的
     * 时间复杂度O(n)
     * */
    public static void main(String[] args) {
        String data = "roll.sports.sina.com.cn";
        HashMap<String, HashMap> stringHashMapHashMap = storageDate("./input.txt");
        String[] arr = data.split("\\.");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = arr.length - 1; i > 0; i--) {
            if (stringHashMapHashMap.containsKey(arr[i])) {
                stringBuilder.insert(0, "." + arr[i]);
                stringHashMapHashMap = stringHashMapHashMap.get(arr[i]);
            } else {
                break;
            }
        }
        System.out.println(stringBuilder.insert(0, "*"));
    }

    /*
    * 将所有数据压缩插入到map中
    * */
    private static HashMap<String, HashMap> storageDate(String inputFilePath) {
        HashMap<String, HashMap> map = new HashMap<>();
        try (FileInputStream inputStream = new FileInputStream(inputFilePath);
             BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream))) {
            String str;
            while ((str = bufferedReader.readLine()) != null) {
                String[] arr = str.split("\\.");
                addToMap(arr, map, arr.length - 1);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return map;
    }

    /*
     * 将数据插入到Map中
     * */
    private static HashMap<String, HashMap> addToMap(String[] arr, HashMap<String, HashMap> map, int n) {
        if (n >= 1) {
            map.put(arr[n], addToMap(arr, map.containsKey(arr[n]) ? map.get(arr[n]) : new HashMap<>(), n - 1));
        }
        return map;
    }