数组中第k大的元素

此文为 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(Agent 355)

特工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由伊达拉·维克托扮演。

阅读更多

Redis 6 中的客户端缓存

本文是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服务器端内存作为代价;你所赢得的是更细粒度的失效。

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

阅读更多

Is the Perfect the Enemy of the Good?

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

本文为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

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

题意

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

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

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

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

题解

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

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

代码

阅读更多

LeetCode:1106. Parsing A Boolean Expression

本文是LeetCode 1106. Parsing A Boolean Expression的题解。

题意

给定一个String类型的布尔表达式expression,返回一个求值的结果。

表达式可以是:

  • "t", 表示为 True;
  • "f", 表示为 False;
  • "!(expr)", 将内部的 expr 结果取反;
  • "&(expr1,expr2,...)", 将内部的expr1, expr2, ...求与;
  • "|(expr1,expr2,...)", 将内部的expr1, expr2, ...求或。

题解

直接递归解释表达式就好,每层负责解释上述的一个规则就可以。

这儿有一个优化点:实现表达式惰性求值。

代码

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
/**
* https://www.robberphex.com/parsing-a-boolean-expression/
* Runtime: 1 ms, faster than 100.00% of Java online submissions for Parsing A Boolean Expression.
* Memory Usage: 38 MB, less than 100.00% of Java online submissions for Parsing A Boolean Expression.
*/
class Solution {
class Result {
/**
* 表达式结果
*/
boolean res;
/**
* 下次解析的起始位置
*/
int end;

Result(boolean res, int end) {
this.res = res;
this.end = end;
}
}

private Result parseBoolExpr(String expression, int start) {
if (expression.charAt(start) == 'f') {
return new Result(false, start + 1);
} else if (expression.charAt(start) == 't') {
return new Result(true, start + 1);
} else if (expression.charAt(start) == '!') {
Result result = parseBoolExpr(expression, start + 2);
result.res = !result.res;
result.end++;
return result;
} else if (expression.charAt(start) == '&') {
Result finalResult = new Result(true, 0), result;
start++;
do {
result = parseBoolExpr(expression, start + 1);
if (!result.res) {
// 在这儿可以实现惰性求值
finalResult.res = false;
}
start = result.end;
// 如果是逗号,继续解析
} while (expression.charAt(result.end) == ',');
finalResult.end = result.end + 1;
return finalResult;
} else if (expression.charAt(start) == '|') {
Result finalResult = new Result(false, 0), result;
start++;
do {
result = parseBoolExpr(expression, start + 1);
if (result.res) {
// 在这儿可以实现惰性求值
finalResult.res = true;
}
start = result.end;
} while (expression.charAt(result.end) == ',');
finalResult.end = result.end + 1;
return finalResult;
} else {
throw new RuntimeException();
}
}

public boolean parseBoolExpr(String expression) {
return parseBoolExpr(expression, 0).res;
}

public static void main(String[] args) {
boolean res = new Solution().parseBoolExpr("!(&(&(!(&(f)),&(t),|(f,f,t)),&(t),&(t,t,f)))");
System.out.println(res);
// 输出 true
}
}
阅读更多

LeetCode:103. Binary Tree Zigzag Level Order Traversal

本文为LeetCode:103. Binary Tree Zigzag Level Order Traversal的题解。

题意

一颗给定的二叉树,返回节点值的之子形的便利结果。即,从左到右,然后下一级别是从右到左,如此交替。

例如:

给定二叉树:[3,9,20,null,null,15,7]

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

程序将会返回之字形遍历顺序:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

题解

对于第一层遍历,从左到右,添加到一个stack中;对于第二层遍历,pop出来的顺序是从右到左,所以要额外考虑先添加right子节点、再添加left子节点到stack中。

阅读更多

LeetCode 1103:Distribute Candies to People

本文为LeetCode 1103:Distribute Candies to People的题解。

题意

我们用下面的方法给num_people个人分发一些糖果:

我们给第一个人1块糖,给第二个人2块糖,以此类推,直到我们给最后一个人n块糖。

然后,我们回到开始,给第一个人n + 1块糖,给第二个人n + 2块糖,以此类推,直到我们给最后一个人2 * n块糖。

这个过程不断重复(当重新走到队首的时候,我们每次比上次多给n个糖果),直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。

返回一个数组(长度为num_people),该数组表示最终每个人得到的糖果数量。

题解

首先我们考虑能完整的分发几轮。

由于分发数量总体上就是从1到n*num_people的等差序列,n符合如下不等式:

阅读更多

LeetCode题解:Path In Zigzag Labelled Binary Tree

本文为LeetCode 1104. Path In Zigzag Labelled Binary Tree 的题解。

题目描述

一棵无穷的二叉树,每个节点都编号(label)了:对于奇数层(第1、3、5等层),从左向右编号。对于偶数层,从右向左编号。但是每层的编号还是最小2^(level-1),最大2^level-1

如图:

给你一个编号(label),输出从顶层到该节点经过的节点编号。

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

阅读更多