随笔

今天主要是想了一天算法，其他也没怎么学习。一会再去看一会csapp。我发现最近每天晚上睡五个半小时就自动醒了，再长也睡不着了，很奇怪。今天吃了两顿鱼香肉丝，好久没吃了，挺好吃的。闲话就到这里吧，下面进入正体。

优先队列/堆

一直对heap不是很熟悉，主要还是没有亲手写过一个。今天写了一个，感觉理解深刻了很多。果然，看再多遍不如写一遍。
堆最主要的两个操作是上浮和下沉，用来调整堆。java实现中叫siftUp & siftDown。Up没什么坑，反复找父节点就可。但是down有点意思。这里我重写一下，加深印象。

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;
    while (k < half) { // loop while a non-leaf
        int chlid = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        if (right < size && ((Comparable< ? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0) break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

这里有几个需要注意的地方。

• 当下标大于half时就表示叶子结点，也就不需要继续下沉了。
• 下沉时是和左右子结点中较小的一个交换位置，这里比较巧妙，当不能交换时即可退出循环。
• 没有必要一直交换。（类比冒泡排序和插入排序），可以先把位置空出来，找到最终位置之后再插进去。
  优先队列寻找最大最小值是比较快的，也比较平均（插入和查找）。

Java 与 C++

最近在看C++，也一直试图用c++做题。但是一直做的不是很顺手，主要是对c++不熟悉，包括各种语法和库函数。二来用java写不用担心内存之类，心智负担小了很多。关键是配合IDEAjava太好写了，概念也简单很多。C++怎么初始化变量至今我还没搞清。括号初始化，花括号初始，new等等，我看可以看懂，但是具体到写的时候就忘记了。要是都像java一样统一就好了。
这一段的代码，我就先用c++，要是不行就转Java。最终我还是偏向C++一点，这么长时间的cs教育让我对零成本抽象和高性能有一点宗教式的追求。我知道绝大多数时候性能够用就好，而且为了这些性能还要背上很重的心智负担，但总还是想要尽可能高的性能，除非语言像scheme一样优雅。
郁闷的是，我费了半天写优先队列，结果随手用c++写了个分治，不但性能翻了20多倍，内存也只有一半，而且都没debug一次就过了。也不知道是语言的原因，还是我写的heap太差了。把c++代码放到这里

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge2List(ListNode *a, ListNode *b) {
        ListNode *ans = new ListNode(0), *p = ans;
        while (true) {
            if (a == nullptr) {
                p->next = b;
                break;
            } 
            if (b == nullptr) {
                p->next = a;
                break;
            }
            if (a->val <= b->val) {
                p->next = a;
                a = a->next;
            } else {
                p->next = b;
                b = b->next;
            }
            p = p->next;
        }
        return ans->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        else return merge(lists, 0, lists.size());
    }

    ListNode* merge(vector<ListNode*>& l, int start, int end) {
        if ((end - start) == 1) {
            return l[start];
        } else if (end == start) {
            return nullptr;
        }
        int mid = (end - start) / 2 + start;
        ListNode *left = merge(l, start, mid);
        ListNode *right = merge(l, mid, end);
        return merge2List(left, right);
    }
};

从0开始与左闭右开

link
看到这个经典文章。文章也不长，我直接粘贴了

Why numbering should start at zero
To denote the subsequence of natural numbers 2, 3, ..., 12 without the pernicious three dots, four conventions are open to us
a) 2 ≤ i < 13
b) 1 < i ≤ 12
c) 2 ≤ i ≤ 12
d) 1 < i < 13
Are there reasons to prefer one convention to the other? Yes, there are. The observation that conventions a) and b) have the advantage that the difference between the bounds as mentioned equals the length of the subsequence is valid. So is the observation that, as a consequence, in either convention two subsequences are adjacent means that the upper bound of the one equals the lower bound of the other. Valid as these observations are, they don't enable us to choose between a) and b); so let us start afresh.
There is a smallest natural number. Exclusion of the lower bound —as in b) and d)— forces for a subsequence starting at the smallest natural number the lower bound as mentioned into the realm of the unnatural numbers. That is ugly, so for the lower bound we prefer the ≤ as in a) and c). Consider now the subsequences starting at the smallest natural number: inclusion of the upper bound would then force the latter to be unnatural by the time the sequence has shrunk to the empty one. That is ugly, so for the upper bound we prefer < as in a) and d). We conclude that convention a) is to be preferred.
Remark The programming language Mesa, developed at Xerox PARC, has special notations for intervals of integers in all four conventions. Extensive experience with Mesa has shown that the use of the other three conventions has been a constant source of clumsiness and mistakes, and on account of that experience Mesa programmers are now strongly advised not to use the latter three available features. I mention this experimental evidence —for what it is worth— because some people feel uncomfortable with conclusions that have not been confirmed in practice. (End of Remark.)
When dealing with a sequence of length N, the elements of which we wish to distinguish by subscript, the next vexing question is what subscript value to assign to its starting element. Adhering to convention a) yields, when starting with subscript 1, the subscript range 1 ≤ i < N+1; starting with 0, however, gives the nicer range 0 ≤ i < N. So let us let our ordinals start at zero: an element's ordinal (subscript) equals the number of elements preceding it in the sequence. And the moral of the story is that we had better regard —after all those centuries!— zero as a most natural number.
Remark Many programming languages have been designed without due attention to this detail. In FORTRAN subscripts always start at 1; in ALGOL 60 and in PASCAL, convention c) has been adopted; the more recent SASL has fallen back on the FORTRAN convention: a sequence in SASL is at the same time a function on the positive integers. Pity! (End of Remark.)
The above has been triggered by a recent incident, when, in an emotional outburst, one of my mathematical colleagues at the University —not a computing scientist— accused a number of younger computing scientists of "pedantry" because —as they do by habit— they started numbering at zero. He took consciously adopting the most sensible convention as a provocation. (Also the "End of ..." convention is viewed of as provocative; but the convention is useful: I know of a student who almost failed at an examination by the tacit assumption that the questions ended at the bottom of the first page.) I think Antony Jay is right when he states: "In corporate religions as in others, the heretic must be cast out not because of the probability that he is wrong but because of the possibility that he is right."
Plataanstraat 5
5671 AL NUENEN
The Netherlands 11 August 1982
prof.dr. Edsger W. Dijkstra
Burroughs Research Fellow

但在我上个题中的c++中，似乎还是左右都闭区间好用一点。我再想想这个问题。
想了想，觉得差不多。贴个左右都闭的merge

   ListNode* merge(vector <ListNode*> &lists, int l, int r) {
       if (l == r) return lists[l];
       if (l > r) return nullptr;
       int mid = (l + r) >> 1;
       return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
   }

梦

昨晚和今天中午做了噩梦，昨晚梦见被长剑穿过胸口。今天中午又梦到之前梦到的一个场景，又像是大学，又像是二中，我梦到过它好多次了，让我怀疑是不是梦那边有另一个世界😂。感觉好久没做梦了，也不知道现在做梦是休息好了还是没休息好。感觉自己鼠标坏了，总是莫名奇妙点两下。睡了。