每周学算法/读英文/知识点心得分享 3.11

每周一个 Algorithm，Review 一篇英文文章，总结一个工作中的技术 Tip，以及 Share 一个传递价值观的东西！

Algorithm: 学习算法

题目：Merge k Sorted Lists

描述：

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:

[

1->4->5,

1->3->4,

2->6
]

Output: 1->1->2->3->4->4->5->6

解题过程：一种思路是多个指针指向链表头，将表头元素放入优先队列 pqueue，每次从中取出一个然后添加到新链表的next，并将取出元素的next放入pqueue，直到队列为空。另一种思路是分治法，有时间再补上。

解法：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // define priorityQueue
        PriorityQueue<ListNode> q= new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>(){
            @Override
            public int compare(ListNode o1,ListNode o2){
                if (o1.val<o2.val)
                    return -1;
                else if (o1.val==o2.val)
                    return 0;
                else 
                    return 1;
            }
        });

        // pop queue with list head
        for (ListNode head : lists) {
            if (head != null) {
                q.add(head);
            }
        }

        // pop from queue and append node to new list, add next from poll element to queue
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while (!q.isEmpty()) {
            temp.next = q.poll();
            if (temp.next.next != null) {
                q.add(temp.next.next);
            }
            temp = temp.next;
        }
        return dummy.next;
    }
}

Review: 学习英文

题目：Effective Java Item 6 Eliminate obsolete object references

作者分析三个可能的内存泄漏点：对无用对象保持的引用、缓存和监听器及回调方法。

如果你的程序自己在管理内存 ，分配数组或对象空间，计算区分有用和无用数据的下标，例如Vector.java 这个类，那么就有内存泄露的可能。不仅是存放在数组中的对象，而且被这些对象引用的对象也一概不会被回收，因为只有程序员知道，而JVM并不知道他们已经废弃。对于这种情况，作者建议是对废弃对象作 null 处理。

对于缓存中的内存泄漏，作者建议使用WeakHashMap 作为缓存，方便JVM在内存不够时回收。这种解决方法有一个前提，就是你认为如果存在对于Key的引用，那么缓存就是有效的，因为这样JVM就不回收WeakHashMap中的对象。

对于监听器的内存泄漏，作者的建议同样是使用WeakReference来引用他们，当垃圾回收时就会回收他们。

Tips: 知识点

在JDK8中，HashMap有一个比较大的变动，就是当链表长度过长时，查询/插入/删除的复杂度会退化成O(N)，通过将链表转化成一颗红黑树，使得复杂度保持在O(LogN)

Share: 价值观

复杂的事情简单做，是专家；简单的事情重复做，是行家；简单的事情用心做，你会快乐！