昨天升级到了macOS Catalina 10.15 Beta (19A526h)，发现Firefox无法打开了…

不得以，只能看下如何在不打开Firefox的情况下，将会话中打开的url拿出来。

首先，得找到Profile的问题，参考 https://support.mozilla.org/en-US/kb/profiles-where-firefox-stores-user-data 找到位置，将Profile目录下的sessionstore-backups文件夹拷出来。

其中，recovery.jsonlz4文件即为会话的恢复信息，但是这个文件不是标准的lz4压缩文件，得使用特殊的工具来解压，在 https://github.com/avih/dejsonlz4 下载dejsonlz4源码，编译。

通过命令将jsonlz4解压成json：

./dejsonlz4 /path/to/recovery.jsonlz4 /path/to/output/recovery.json

接下来就是探索这个recovery.json的内容了，很简单：

• jq keys查看这个json文件中的顶级key，比如cat recovery.json | jq keys
• 查看某一个节点可以通过.来引用，比如jq '.[0].entrys'就是查看第零个元素中的entrys属性

最终，可以通过如下命令输出会话中所有的url：

1

jq -r '.windows[].tabs[].entries[].url' recovery.json 

刷微博，看到一道面试题：

先说一下思路

默认题意为不能取重复的数字

总体来说，就是从可行解空间[1,1]~[20,20]中，逐步过滤，找到最终答案的过程。说一下过滤步骤：

1. 首先A不确定两个数字，所以两数之和sum满足：4<=sum<=38
2. 其次B也不确定，所以两数之积的分解方式可能有多种（本来以为可以用质因子个数>2来判别的，但是后来发现还要考虑两数在1到20之间）
3. A知道数字了，所以sum的所有分解方式中，只有一个是让B不能确定的，即i+j=sum，切i*j的分解方式不止一种
4. 这一步比较难：B知道乘积prod，对于prod分解的所有可能，都能得到其和sum，如果sum的所有分解中，只有一个是让B不能确定的；而且prod的分解只有一个是满足此关系的。则当前的prod，以及对应的让B不能确定的prod分解，即为所求解。

1和2很容易理解。3的话，如果sum的诸多分解方式中，都能被B确定，即ij只能唯一分解，那B就不会说不知道数字了。如果sum的诸多分解方式中，有多个不能被B确定，那A在第三步就不能确定数字了，因为A不确定B是在哪一组ij中。

4，B知道乘积prod，假设可以分解为 I_n, J_n 。对于每一组 I_n, J_n：

和为sum=I_n+J_n，且A知道这个sum，这时B推测sum可以分解为i_n+j_n：
  由于3的结论，所以sum对应的i_n*j_n的分解不唯一的情况只有一个
  如果sum对应的i_n*j_n分解不唯一的情况为0个，那么B在第二步就可以猜出
  如果sum对应的i_n*j_n分解不唯一的情况多于1个，那么A在第三步就猜不出来了
在所有的 I_n, J_n 中，满足如上条件的只有一个
如果都满足上述条件的多于一个，那么B在最后一步就无法确定哪一组I_n,J_n是正确答案了

当然，第四步也是在第三步的结果上过滤的

LeetCode 23. Merge k Sorted Lists

题意

合并k个链表，每个链表内部都是排好序的（从小到大），但是k个链表之间是无序的。

思路

首先，最简单的办法就是链表之间选择排序，取第一个链表的第一个节点插到结果中。然后如果链表还有节点，放回到数组中。如此往复，直到没有节点剩余。

时间复杂度O(k*n)，空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 420 ms Memory Usage: 38.6 MB
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        ListNode head = null;
        int hi = -1;
        // 选出一个head
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null && (head == null || lists[i].val < head.val)) {
                head = lists[i];
                hi = i;
            }
        }

        if (head == null)
            return head;
        lists[hi] = lists[hi].next;
        ListNode prev = head;

        while (true) {
            ListNode cur = null;
            int ci = 0;
            // 选出最小的node
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null && (cur == null || lists[i].val < cur.val)) {
                    cur = lists[i];
                    ci = i;
                }
            }
            if (cur == null)
                break;
            // 插入到链表中
            lists[ci] = lists[ci].next;
            prev.next = cur;
            cur.next = null;
            prev = cur;
        }

        return head;
    }
}

显然，多次对k个链表排序是很浪费的，这时候就想到了堆，只需要将k个链表构成一个堆即可。时间复杂度O(N*log(k))，空间复杂度O(1)：

构建堆有两种，一种是从底向上不断调整堆，一种是依次将元素放入堆中。显然，前一种比较省时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 2 ms Memory Usage: 43.2 MB
class Solution {
    private int len;

    public void adjust(ListNode[] lists, int startIndex) {
        ListNode start = lists[startIndex];
        int currIndex = startIndex;
        while (currIndex < len) {
            int nextIndex = currIndex * 2 + 1;
            if (nextIndex + 1 < len && lists[nextIndex + 1].val < lists[nextIndex].val) {
                nextIndex += 1;
            }
            if (nextIndex < len && start.val > lists[nextIndex].val) {
                lists[currIndex] = lists[nextIndex];
                currIndex = nextIndex;
            } else {
                break;
            }
        }
        lists[currIndex] = start;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        len = lists.length;
        // 剔除null
        for (int i = 0; i < len; ) {
            if (lists[i] == null) {
                lists[i] = lists[--len];
            } else {
                i++;
            }
        }
        ListNode head = null;
        ListNode tail = null;
        // i==0时的调整交给下面的while循环
        for (int i = len / 2; i > 0; i--) {
            adjust(lists, i);
        }
        while (len > 0) {
            adjust(lists, 0);
            if (tail == null) {
                head = tail = lists[0];
            } else {
                tail.next = lists[0];
                tail = tail.next;
            }
            if (tail.next != null) {
                lists[0] = tail.next;
            } else {
                lists[0] = lists[len - 1];
                len--;
            }
            tail.next = null;
        }
        return head;
    }
}

题目：https://codeforces.com/contest/1196/problem/B

将长度为n的数组a划分成k个非空组，确保所有的组内之和都为奇数。

本来以为是要输出所有的可行解，所以想了一个O(n^k)的解法，结果超时。后来发现只需要输出一组解即可。

首先计算数组中奇数个数，如果奇数个数等于k，则每组一个奇数，满足需求。

如果奇数个数比k大奇数个，则这些奇数一定会导致一个组的和变成偶数，不满足。如果奇数个数比k大偶数个，则满足要求。

然后就是如何构造序列的问题了。

首先，对于前k-1个序列，每个序列仅包含一个奇数，最后剩下的一个组包含剩下的数字，很容易可以想到，最后一个组一定包含了奇数个奇数。

另外，java.util.Scanner有性能问题，还是使用自己实现的FastReader

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    private static void process(int[] arr, int segs) {
        int[] indexes = new int[arr.length];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 1) {
                indexes[index++] = i;
            }
        }
        if (index < segs || (index - segs) % 2 == 1) {
            System.out.println("NO");
            return;
        }
        System.out.println("YES");
        for (int i = 0; i < segs - 1; i++) {
            System.out.print(indexes[i] + 1);
            System.out.print(" ");
        }
        System.out.println(arr.length);
    }

    public static void main(String[] args) {
        FastReader scn=new FastReader();
        int tn = scn.nextInt();
        while (tn-- > 0) {
            int n = scn.nextInt();
            int seg = scn.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = scn.nextInt();
            }
            process(arr, seg);
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

此文为 LeetCode 215. Kth Largest Element in an Array 的题解。

题意

在一个未排序的数组中，寻找第k大的元素。

分析

这个题目其实很简单，但是踩了一些坑，所以记录一下：

首先是用PriorityQueue，然后poll k次即可（5 ms，37.5 MB）。但是属于API caller，略去不表。

其次就是堆排序，很久不写了，第一次把堆排序写成了选择排序，导致时间很长：101 ms，37.2 MB。

后来复习了下堆排序，写出来了（2 ms，36.6 MB）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// from https://www.robberphex.com/kth-largest-element-in-an-array/
// 2 ms，36.6 MB
class Solution {
    // 调整current子树，将其整理成最小堆
    private void adjust(int[] nums, int current, int length) {
        // 将堆顶取出来
        int num = nums[current];
        // 将子树中比顶大的数依次弹上来
        for (int i = current * 2 + 1; i < length; i = 2 * i + 1) {
            if (i + 1 < length && nums[i + 1] < nums[i]) {
                i++;
            }
            if (nums[i] < num) {
                nums[current] = nums[i];
                current = i;
            } else {
                break;
            }
        }
        // 不能弹，则将该数放到对应的位置
        nums[current] = num;
    }

    public int findKthLargest(int[] nums, int k) {
        for (int i = (nums.length - 1) / 2; i >= 0; i--) {
            // 从第一个非叶子结点开始，构建堆
            adjust(nums, i, nums.length);
        }
        for (int i = 1; i <= nums.length - k+1; i++) {
            // 将堆顶交换到数组尾部
            int tmp = nums[nums.length - i];
            nums[nums.length - i] = nums[0];
            nums[0] = tmp;
            // 然后继续构建堆
            adjust(nums, 0, nums.length - i);
        }

        return nums[k - 1];
    }
}

当然，很容易想到，最优解就是快速选择算法：快速排序划分区间的时候，忽略所有不包含k的区间即可（1 ms，37.3 MB）：

特工355（1780年后去世）是美国革命期间女性间谍的代名，是库尔珀组（Culper Ring）的一部分。 特工355是美国的第一批间谍之一，真实身份未知。355这个数字是库尔珀组中的加密系统用来表示“女士”的数字。

生平

在库尔珀组的公文中，唯一直接提及特工355的是亚伯拉罕·伍德赫尔给乔治·华盛顿将军的信。伍德赫尔形容她是“对这封信有帮助的人”。

特工355的真实身份仍然未知，但有关她的一些事实似乎很清楚。作为间谍，她在美国独立战争期间与美国爱国者（或称美国辉格党，革命党）合作。她本会被伍德赫尔招募进间谍组。355这个代码表明她可能具有“某种程度的社会突出性”。她可能生活在纽约市，并且在某些时候与约翰·安德烈少校和贝内迪克特·阿诺德有过接触。 一个可能是特工355的人是伍德赫尔的邻居安娜·斯特朗（Anna Strong）。另一个说法是，特工355可能是罗伯特汤森事实上的妻子。有传说表明汤森爱上了特工355。约翰·伯克和安德里亚·梅耶尔通过间接证据证明她可能与约翰·安德烈少校和本杰明·塔尔马奇关系密切，从而保护伍德赫尔不被指控为间谍，这为355参与间谍活动提出了不同的理由。特工355的其他可能候选人包括Sarah Horton Townsend和Elizabeth Burgin。

偶尔也有一些说法，说根本没有特工355，355仅仅代指一名知道有用信息的女人，并没有与特工组正式关联。代码355仅仅表示“一个女人”，而不是一个女性特工。

探员355被认为是揭露阿诺德和逮捕少校约翰·安德烈的主要角色，后者在纽约塔潘被绞死。她可能是一个著名的保皇派（或称托利党）家庭的成员，这个家庭背景使她很容易接近英国指挥官。

1780年，本尼迪克特·阿诺德（Benedict Arnold）前往保皇派那里，这时特工355被逮捕。她被囚禁在泽西号军舰上，这是一艘监狱船，在那里她可能生下了一个名叫小罗伯特·汤森的男孩。她后来死在监狱船上。然而，亚历山大·罗斯不同意这种说法，他说“女性没有被关在监狱船上”，“没有任何出生的记录”。这强化了355号特工可能是安娜·斯特朗的观点，因为她的丈夫塞拉·斯特朗被囚禁在泽西岛，她应该可以给丈夫带食物。她出现在船上使人们传言特工355被囚禁在那里。

在流行文化中

特工355已经成为通俗小说的一部分。她是《Y：世上最后一个男人》中一个主要角色。她也是现代间谍355的灵感来源，并收录在《刺客信条3》的游戏内历史事实数据库中，她的信息对于帮助主角发现要捕获的英国阴谋至关重要。

在电视剧《逆转奇兵》（Turn: Washington’s Spies）中，特工355是一位名叫阿比盖尔（Abigail）的前奴隶，安娜·斯特朗曾是她的主人。英国军队在安娜·斯特朗入狱后没收了他的财产。虽然名义上阿比盖尔是自由的，但她被迫为约翰·安德烈工作。阿比盖尔把她在安德烈家中无意中听到消息藏在给儿子的礼物中，这个儿子被迫留下交给安娜照顾。剧中，特工355由伊达拉·维克托扮演。

本文是Client side caching in Redis 6_的翻译，文中的“我”皆是Redis作者 Salvatore Sanfilippo。_如有翻译不妥之处，请不吝指教！

纽约 Redis 日结束后，我五点半在酒店醒来，仍然与意大利的时区保持着相当的同步，然后立刻走在了曼哈顿的大街上，完全爱上了这儿的景观和自己只是数以百万人中的普通人这种感觉。但我仍然在回想Redis 6发布的感觉，作为最重要的特性，新的Redis协议（RESP3），将会有很慢的采用曲线，而这也有重复的理由：聪明的人不会无理由的切换手头上的工具。说回来，我为什么如此迫切的想要改进协议呢？主要有两个原因，为了给客户端提供更加语义化的回复，也为了给哪些旧协议很难实现的功能打开大门；其中一个特性对我来说尤其重要：客户端缓存。

回到大约一年前。我去旧金山的Redis Conf 2018时，有一个坚定的想法：客户端缓存是未来Redis最重要的特性。如果我们需要快速存储和快速缓存，那么我们就需要在客户端存储数据的子集。这是为了提供小延迟、大规模数据的想法的自然延伸。事实上，几乎所有的大公司都已经这么做了，因为这几乎是唯一的办法。然而，Redis无法在这个过程中帮助客户端。一个幸运的巧合是，Ben Malec在Redis Conf上做了一个关于客户端缓存的演讲，仅仅使用了Redis提供的工具和一些非常聪明的想法。

Ben采取的办法确实打开了我的想象。为了实现自己的想法，Ben相处两个关键性的主意。第一个是使用Redis集群中的“哈希槽”的概念，以便将key划分为16k个组。这样，客户机就不需要跟踪每个key的有效性，而是可以为一组key使用单个元数据条目。Ben使用Pub/Sub在key发生更改时发送通知，因此他需要应用程序在各个部分提供一些功能，但是整个过程非常可靠。修改一个key？发布一条invalidation消息使其无效。在客户端，是否缓存了这个key？客户端记住每个缓存key的时间戳，以及在接收invalidation消息的时间戳，以记住每个哈希槽的失效时间。使用一个key的时候，通过检查key所在的哈希槽的缓存时间戳是不是早于失效时间戳，来做一个懒驱逐（eviction）：在这种情况下key在客户端缓存中是旧数据，客户端必须向服务器请求。

观看了演讲之后，我意识到这是一个非常好的主意，它能让Redis做一部分客户端的事情，并且让客户端缓存更加简单和高效，所以我回到家就开始写文档来描述我的设计。

但是为了让我的设计能实现，我必须集中精力改进Redis协议，所以我开始写RESP3的规范和代码，以及Redis 6的其它特性，比如ACL等。而且，客户端缓存占据了其它想法的资源，所以我不得不放弃一些别的想法和特性。

我当时正在纽约街头思考这个想法。后来和参会的朋友们一起吃午饭，喝咖啡休息。当我回到我的酒店房间，距离我的航班起飞，我还有当天晚上和第二天大半个白天，所以我开始为Redis 6实现客户端缓存，和我一年前写给开发组的提议基本一样：过了一年，它仍然看起来很棒。

Redis服务器辅助客户端缓存，最终称为“追踪(tracking)”（但我可能会改变主意），是一个非常简单的功能，由几个关键的想法组成。

key空间整体被分为几个哈希槽，但不仅仅是Ben的那种哈希槽。我们用24比特位作为CRC64的输出，所以会有1600多万个不同的哈希槽。为什么这么多？因为我觉得你可能会有1亿个key，而在客户端缓存中，一个失效消息不应该影响过多的key。Redis用于存储invalidation表的内存开销为130MiB，一个1600万个条目，每个条目8字节的数组。这对我来说没问题，如果你想要这个功能，你就要充分利用客户端所有的内存，所以使用130MB服务器端内存作为代价；你所赢得的是更细粒度的失效。

客户端缓存是默认关闭的，你可以使用如下简单的命令来开启这个特性：

Voltaire once said, “perfect is the enemy of the good.” And as a perfectionist in recovery, I can say without hesitation, the boy was he right!

Having high standards motivates us to work hard and to excel in life.

However, the desire to be perfect only handicaps us. It stops us from doing what we’d really like to do. And if it doesn’t, it deprives us of the pleasure of enjoying what we pursue.

Here’s what happens when we reach for perfection:

We become Haunted by Failure

Under the false illusion that our path in life should be a straight line, we become terrified of curves and detours. Nothing sounds more catastrophic than the idea of making a mistake. So we become scared to death of taking risks. Of going beyond the unknown to try something new.

We don’t see failure as an opportunity to learn and to grow. But only as the most intimidating threat to be feared. So we do everything in our power to avoid it at all costs. Even if it means we stop living.

We Fail to Enjoy Success

If we see failure as our enemy then success would be our foremost ally, right? Well no. Even if we succeed, our expectations are such that any success is perceived as trivial. When we accomplish a goal we underestimate it. And fail to savor it.

There’s always something that could have been done better. A mistake that could have been avoided. A detail that shouldn’t have been missed. In the end, there’s always something that we failed to do, even if we succeeded. Because we failed to be perfect.

本文为LeetCode 25. Reverse Nodes in k-Group的题解。

题意

给定一个链表，k个一组反转链表。

k 是一个正数，且小于链表长度。如果按照k个一组，最后剩下的不组k，则不反转剩下的元素。

例子:

对于链表: 1->2->3->4->5

若 k = 2, 应返回: 2->1->4->3->5

若 k = 3, 应返回: 3->2->1->4->5

注意:

• 只允许O(1)的空间复杂度。
• 不可以改变节点的值。

此文为LeetCode 991. Broken Calculator的题解。

题意

有一台坏掉的计算器，能够显示一个数字，我们可以对这个数字做两个操作：

• 乘二: 将显示的数字乘以2, 或者;
• 减一: 将显示的数字减1.

初始时，计算器显示数字 X.

返回要得到数字Y需要的最小操作次数。

题解

如果X>Y，则只能执行减一操作。否则，如果Y是奇数，则上一步操作一定是X减一；如果Y是偶数，则上一步操作只能是X乘二。

只需要通过上述规则，由Y反推X即可。

代码