1. 两数相除
题目很简单（但还是错了几十遍）， 思路是将除数翻倍地增大，超出被除数范围后，用被除数本应剩余的值继续重复操作。
需要注意的点： 因为是翻倍操作，很可能会出现除数翻倍后超过int 范围，所以需要用Long 类型
Math.abs() 函数，在使用时要 Math.abs((long) c) 因为最小值的绝对值超过了Int 范围， 所以这样使用才能保证得到准确的值
代码:
2. 合并 K 个有序链表
几种思路： 1. 将所有元素挨个添加到数组中， Arrays.sort() 排序，然后逐个添加进新链表
Arrays.sort() 时间复杂度为 O(NlogN) 比较暴力，效率低
2. 最小堆，保存每个链表的头，依次将最小的添加进新链表，因为堆每次操作时间复杂度为 logk (k 是链表个数，即堆的大小)
一共 N 个节点，要操作N 次， 所以时间复杂度为 NlogK ，效率大大提高
3. 分治法。 因为之前做过将两个有序链表合并的题目，其时间复杂度为 O（N），（N是两个链表的总节点数）
将链表两两合并，每次合并链表数目都会减半，每次合并都会遍历所有节点，即N次
K减半至1 ，需要 LogK 次，所以时间复杂度同样为 O(NlogK)
最小堆代码：
public ListNode mergeKLists(ListNode[] lists) {
MinHeap pq = new MinHeap(lists.length);
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
pq.add(lists[i]);
}
}
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (!pq.isEmpty()) {
ListNode node = pq.extractMin();
cur.next = node;
cur = node;
if (node.next != null) {
pq.add(node.next);
}
}
return dummyHead.next;
}
private class MinHeap {
private ListNode[] data;
private int capacity;
private int size;
public MinHeap(int capacity) {
this.capacity = capacity;
data = new ListNode[capacity];
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public void add(ListNode node) {
if (size == capacity) {
throw new IllegalArgumentException("heap is full.");
}
data[size] = node;
shiftUp(size);
size++;
}
private void swap(int i, int j) {
ListNode temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private void shiftUp(int k) {
while (k > 0 && data[k].val < data[(k - 1) / 2].val) {
int parent = (k - 1) / 2;
swap(k, parent);
k = parent;
}
}
public ListNode extractMin() {
if (size == 0) {
throw new IllegalArgumentException("heap is empty...");
}
ListNode ret = data[0];
data[0] = data[--size];
shiftDown(0);
return ret;
}
private void shiftDown(int k) {
while (2 * k + 1 < size) {
int j = 2 * k + 1;
if (j + 1 < size && data[j + 1].val < data[j].val) {
j++;
}
if (data[k].val <= data[j].val) {
break;
}
swap(k, j);
k = j;
}
}
}
代码来自 leetcode : lmz
分治法代码：
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null||lists.length==0)return null;
//ListNode head = new ListNode(1);
int len = lists.length;
int ind = 1;
while (ind <len) {
for(int i =0;i<len - ind;i+=2*ind){
lists[i] = mergeTwoLists(lists[i],lists[i+ind]);
}
ind *=2;
}
return lists[0];
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) return null;
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head, hd = l1;
if (l1.val > l2.val) {
hd = l2;
l2 = l2.next;
} else l1 = l1.next;
head = hd;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
head.next = l2;
l2 = l2.next;
} else {
head.next = l1;
l1 = l1.next;
}
head = head.next;
}
while (l1 != null) {
head.next = l1;
l1 = l1.next;
head = head.next;
}
while (l2 != null) {
head.next = l2;
l2 = l2.next;
head = head.next;
}
return hd;
}
PS： 之前用 PriorityQueue ，耗时一直是分治法的十几倍，后来才知道 PriorityQueue的复杂度比自己写的最小堆要高，
原文：https://www.cnblogs.com/xfdmyghdx/p/11070023.html