LeetCode 23. Merge k Sorted Lists

LeetCode 23. Merge k Sorted Lists

题意

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

思路

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

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

// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 420 ms Memory Usage: 38.6 MB
Read the rest

Codeforces Round #575 B. Odd Sum Segments

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

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

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

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

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

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

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

数组中第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):

// from https://www.robberphex.com/kth-largest-element-in-an-array/
Read the rest

特工355(Agent 355)

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

生平

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

特工355的真实身份仍然未知,但有关她的一些事实似乎很清楚。作为间谍,她在美国独立战争期间与美国爱国者(或称美国辉格党,革命党)合作。她本会被伍德赫尔招募进间谍组。355这个代码表明她可能具有“某种程度的社会突出性”。她可能生活在纽约市,并且在某些时候与… Read the rest

Redis 6 中的客户端缓存

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

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

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)的空间复杂度。
  • 不可以改变节点的值。

题解

这个题目麻烦的地方在于边界情况太多。但简单而言,可按照如下处理:… Read the rest

LeetCode:991. Broken Calculator

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

题意

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

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

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

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

题解

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

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

代码

/**
 * https://www.robberphex.com/broken-calculator/
Read the rest

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, ...求或。

题解

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

LeetCode:103. Binary Tree Zigzag Level Order Traversal

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

题意

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

例如:

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

    3
   / \
  9  20
    /  \
   15   7

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

[
  [3],
  [20,9],
  [15,7]
]

题解

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