王一夫-20180711.md

leetcode

两数相加

public class Solution {
	private ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        return this.AddTwoNumbers(l1, l2, 0);
    }

    private ListNode AddTwoNumbers(ListNode l1, ListNode l2, int extra) {
        ListNode curNode = l1 == null ? (l2 == null ? null : l2) : l1;
        if (curNode == null) {
            if (extra == 1) {
                curNode = new ListNode(extra);
            }
            return curNode;
        }
        int val1 = l1 == null ? 0 : l1.val;
        int val2 = l2 == null ? 0 : l2.val;
        int result = val1 + val2 + extra;
        extra = result / 10;
        curNode.val = result - extra * 10;
        curNode.next = this.AddTwoNumbers(
            (l1 != null) ? l1.next : null, 
            (l2 != null) ? l2.next : null, 
            extra
        );
        return curNode;
    }
}

Timsort

Timsort 是归并排序的改进算法，最早由 Tim Peters 用 python 语言实现，目前在 python 和 Java 中都成为了默认排序算法。它主要针对归并排序的瓶颈进行了如下优化：

1. 提取有序队列，包括正序和逆序，减少归并的次数，将最好情况从 $O(nlogn)$ 降低到 $O(n)$ 。
2. 设定最小队列 $minrun$ 长度阈值，通常为 32 到 64，小于此阈值时使用插值排序。
3. 优化归并算法，使用了被称作 galloping mode 的归并模型，利用二分插值法提高归并效率，并且降低缓存大小。具体做法为：采用二分在 $A$ 队列中找到比第一个比 $B$ 队列的第一个元素大的元素位置 $locationA$，在 $B$ 队列中找到第一个比 $A$ 队列最后一个元素大的位置 $locatonB$。那么在 $A$ 队列中 $locationA$ 之前的元素，和 $B$ 队列中 $locationB$ 之后的元素在合并后队列中已经处在正确的位置，其中 $A$ 元素个数小于 $B$，剩下的队列再在进行同样的操作。此方法虽然对高度随机的队列优势很小，但在其他情况下具有较好的时间复杂度。

当然 Timsort 的优化不止这几点，例如算法一直尽量在每次遍历中进行更多的操作，来减小整个排序过程的时间复杂度。