主机名排序--华为2018校招笔试题

 题目：

主机名由多级域名组成，自右向左，依次是*域名、二级域名、三级域名…..以此类推
例，主机名：google.com.hk
hk是*域名
com是二级域名
google是三级域名

现在我们需要实现一个主机名的排序功能

排序规则
1）主机名按照域名等级排序，即先按照*域名排序，*域名相同的再按照二级域名排序，*和二级域名均相同的再按照三级域名排序，以此类推，直到整个主机名排序完毕
2）如果短主机名是由长主机名从*域名开始的连续一个或多个域名组成，短主机名排在长主机名前面。例：google.com 排在gmail.google.com 之前
3）每一级域名按照字典顺序排序，字典顺序定义见下页

输入确保符合以下规则（无需检查）
1）主机名以字符串形式给出，非空串
2）主机名中仅包含小写英文字母和分隔符’.’
3）主机名中没有连续的’.’，不以’.’开始，也不以’.’结束
3）主机名不存在重复

字典顺序定义

1、两个单词(字母按照自左向右顺序)先以第一个字母作为排序的基准，如果第一个字母相同，就用第二个字母为基准，如果第二个字母相同就以第三个字母为基准。依此类推，如果到某个字母不相同，字母顺序在前的那个单词顺序在前。例：abc 排在 abf 之前

2、如果短单词是长单词从首字母开始连续的一部分，短单词顺序在前。例：abc 排在 abcd 之前

import java.util.Scanner;

public class Main {
    /**
     * 主机名比较
     * @param hostname1
     * @param hostname2
     * @return
     */
    private int compareHostname(String hostname1, String hostname2) {
        int rlt = 0;
        String[] domainArr1 = hostnameSplit(hostname1);
        String[] domainArr2 = hostnameSplit(hostname2);
        for(int i=0; i< Math.min(domainArr1.length, domainArr2.length); i++) {
            rlt = domainArr1[i].compareTo(domainArr2[i]);
            if(rlt != 0) {
                return rlt;
            }
        }
        if(domainArr1.length > domainArr2.length) {
            rlt = 1;
        } else if (domainArr1.length == domainArr2.length) {
            rlt = 0;
        } else {
            rlt = -1;
        }
        return rlt;
    }

    /**
     * 主机名拆分成域名，且按*域名、二级域名、三级域名……的顺序
     * @param hostname
     * @return
     */
    private String[] hostnameSplit(String hostname) {
        String[] domainArr = hostname.split("\\.");
        String[] reverseDomainArr = new String[domainArr.length];
        for(int i=0; i<domainArr.length; i++) {
            reverseDomainArr[domainArr.length-1-i] = domainArr[i];
        }
        return reverseDomainArr;
    }

    /**
     * 交换数组元素
     * @param arr
     * @param i
     * @param j
     */
    private void swap(String[] arr, int i, int j) {
        String tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 主机名快速排序
     * @param hostnameArr
     */
    private void quickSort(String[] hostnameArr, int left, int right) {
        if(left >= right) {
            return;
        }
        int low = left, high = right;
        String key = hostnameArr[low];
        while(low < high) {
            while(low < high && compareHostname(hostnameArr[high], key) > 0) {
                high--;
            }
            swap(hostnameArr, low, high);
            while(low < high && compareHostname(hostnameArr[low], key) < 0) {
                low++;
            }
            swap(hostnameArr, low, high);
        }
        quickSort(hostnameArr, left, low-1);
        quickSort(hostnameArr, low+1, right);
    }

    public static void main(String[] args) {
        Main m = new Main();
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {//注意while处理多个case
            String str = in.next();
            String[] hostnameArr = str.split("\\|");
            m.quickSort(hostnameArr, 0, hostnameArr.length-1);
            StringBuilder sb = new StringBuilder();
            for(int i=0; i< hostnameArr.length; i++) {
                sb.append(hostnameArr[i]);
                if(i != hostnameArr.length - 1) {
                    sb.append("|");
                }
            }
            System.out.println(sb.toString());
        }
        in.close();
    }
}