04-SortedLists

1. Comparator

/**
 * 比较器
 */
public class _01_Comparator {

    public static class Student {
        public String name;
        public int id;
        public int age;

        public Student(String name, int id, int age) {
            this.name = name;
            this.id = id;
            this.age = age;
        }

        @Override
        public String toString() {
            return "{" + this.name + ", " + this.id + ", " + this.age + "}";
        }
    }

    /**
     * 谁id大，谁放前！
     * <p>
     * 负数：第一个参数排在前面
     * 正数：第二个参数排在前面
     * 0：谁放前面无所谓
     */
    public static class IdComparator implements Comparator<Student> {
        @Override
        public int compare(Student o1, Student o2) {
            // if (o1.id < o2.id) {
            //     return 1;
            // } else if (o2.id < o1.id) {
            //     return -1;
            // } else {
            //     return 0;
            // }
            return Integer.compare(o2.id, o1.id);
        }
    }

    /**
     * 谁age大，谁放前！
     */
    public static class AgeComparator implements Comparator<Student> {
        @Override
        public int compare(Student o1, Student o2) {
            return Integer.compare(o2.age, o1.age);
        }
    }

    @Test
    public void test1() {
        // 默认：从小到大排序
        int[] arr = {8, 1, 4, 1, 6, 8, 4, 1, 5, 8, 2, 3, 0};
        System.out.println("arr = " + Arrays.toString(arr));
        Arrays.sort(arr);
        System.out.println("arr = " + Arrays.toString(arr));

        Student s1 = new Student("张三", 5, 27);
        Student s2 = new Student("李四", 1, 17);
        Student s3 = new Student("王五", 4, 29);
        Student s4 = new Student("赵六", 3, 9);
        Student s5 = new Student("左七", 2, 34);

        Student[] students = {s1, s2, s3, s4, s5};
        System.out.println(Arrays.toString(students));
        System.out.println("=======");
        // 没有自定义比较器（cannot be cast to java.lang.Comparable）
        Arrays.sort(students, new IdComparator());
        System.out.println(Arrays.toString(students));
        System.out.println("=======");

        ArrayList<Student> arrList = new ArrayList<>();
        arrList.add(s1);
        arrList.add(s2);
        arrList.add(s3);
        arrList.add(s4);
        arrList.add(s5);
        // 默认：加入的顺序打印
        System.out.println("arrList = " + arrList);

        arrList.sort(new AgeComparator());
        System.out.println("arrList = " + arrList);
    }

    // --------------------------------------------------------------------------------

    public static class IntComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }

    @Test
    public void test2() {
        // 默认小根堆
        // PriorityQueue<Integer> heap = new PriorityQueue<>();
        PriorityQueue<Integer> heap = new PriorityQueue<>(new IntComparator());
        heap.add(6);
        heap.add(2);
        heap.add(3);
        heap.add(1);
        heap.add(7);
        System.out.println("heap.peek() = " + heap.peek());
        heap.add(0);
        System.out.println("heap.peek() = " + heap.peek());

        System.out.println("=====================");
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }
    }

    // ----------------------------------------------------------------------

    /**
     * PriorityQueue, TreeMap, TreeSet
     */
    @Test
    public void test3() {
        // 本质是堆，优先级队列
        PriorityQueue<Student> heap = new PriorityQueue<>(new IdComparator());
        Student s1 = new Student("张三", 5, 27);
        Student s2 = new Student("李四", 1, 17);
        Student s3 = new Student("王五", 4, 29);
        Student s4 = new Student("赵六", 3, 9);
        Student s5 = new Student("左七", 2, 34);
        heap.add(s1);
        heap.add(s2);
        heap.add(s3);
        heap.add(s4);
        heap.add(s5);
        System.out.println("=========");
        // O(logN)
        while (!heap.isEmpty()) {
            Student s = heap.poll();
            System.out.println(s.name + ", " + s.id + ", " + s.age);
        }

        // 和有序有关的结构要用到比较器：1. TreeMap 2. TreeSet
        TreeSet<Student> studentTreeSet = new TreeSet<>(new IdComparator());
    }

    /**
     * 字符串的比较（字典序）
     * 1. 长度一样，字符当作数来比较
     * 2. 长度不一样，短的字符串后面补0
     */
    @Test
    public void test4() {
        double pow = Math.pow(2, 16);
        System.out.println(pow);

        String str1 = "abc";
        String str2 = "b";
        System.out.println(str1.compareTo(str2));
    }

}

2. MergeKSortedLists

/**
 * M条有序链表，合并成一条
 * https://leetcode.com/problems/merge-k-sorted-lists/
 */
public class _02_MergeKSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static class ListNodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }

    /**
     * O(nlogN)
     * 小根堆大小为M，要处理n个数
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        // 优先级队列，自定义排序规则。O(logN)
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());

        for (ListNode list : lists) {
            if (list != null) {
                heap.add(list);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        ListNode head = heap.poll();
        ListNode pre = head;
        if (pre.next != null) {
            heap.add(pre.next);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;
    }

}