LeetCode 真好玩,我永远喜欢 LeetCode。
Github 链接: FrozenYogurtPuff/Leetcode

#1 Two Sum 两数之和 (Easy)

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

我以为这个不算太容易,后来做了第二题,发现这题的 Easy 大概是针对 $O(n^2)$ 说的。暴力搜索的话,嵌套循环遍历就可以拿到结果。还是说说哈希法吧。

哈希表

Python 的 dict 其实就是哈希表实现的,所以对 Python 来说使用哈希表很容易;我最开始是这样实现的:如 a + b = target,对于每个取出的元素 a,都将 hashtable[a]hashtable[b] 标记 id。边界条件是一个数字出现两次,有可能是无关数据,也有可能恰是 target 的一半。C++ 的实现与之类似,使用的是 STL 的 unordered_map,同样是哈希表实现,写法相对较 Python 繁复一些,代码见此

后来受题解启发,发现只存 hashtable[a],对于每个数字都搜索 hashtable[target - a] 的方法可以避免边界检测,实现代码见此。一个 Pythonic 的技巧是使用 enumerate() 同时拿到遍历内容的 indexvalue

双指针

另外一种值得一提的方法是双指针;先排序(没想到吧,排序也行)得到一个递增有序数列。然后两个指针从两侧开始向内收敛,当和为目标值时输出该值在原数组中的位置;右指针左移其和减小,左指针右移其和增大。一个特例出现在存在负数的情况:此时左右指针不断移动至完全交错位置,最终仍能得到结果。两数值相同时会搜索到相同坐标,所以需要先弹出前者,再搜索后者,具体代码实现是这样的。

其实还想手写 C 语言哈希实现的,但是有点没有把握,等学到了回来更新这段。


#2 Add Two Numbers 两数相加 (Medium)

给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

这题挺好,数字还是逆序的,正好与个位开始的进位实现相同,就很方便。看了几个题解的代码都写得极致漂亮,心动了。

链表迭代

首先,和与进位可以优化为一个变量;在创造完节点后自除以 10,即可作为进位累加至下一位。大边界条件是两链表数字位数不同,其中一方早于另一方结束,应视为 0;小边界条件是诸如 50 + 50 = 100,最后一个单独的进位应当考虑到,与非空判断一同写进循环停止条件会很好看。具体实现见此:CC++Python

链表递归

递归,永远的神;用了递归后除了日常爆栈之外,别的都很舒服。具体代码在这里

在题解中学到一招 Comma Operator,大概是这样:对于 (E1, E2),会执行完 E1 后执行 E2,并返回 E2 内容。所以,对于该题的代码:

if (l1 != nullptr) {
    sum += l1->val;
    l1 = l1->next;
}
if (l2 != nullptr) {
    sum += l2->val;
    l2 = l2->next;
}

可以简化为:

l1 = l1 != nullptr ? (sum += l1->val, l1->next) : l1;
l2 = l2 != nullptr ? (sum += l2->val, l2->next) : l2;

#3 Longest Substring Without Repeating Characters 无重复字符的最长子串 (Medium)

给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

线性探查的时间复杂度是 $O(n^2)$,比较好写,就不考虑了。记得当初做过一道滑动窗口的题,貌似是用的 deque 实现,可如今翻来覆去都想不起来怎么解了。看了题解之后终于恍然大悟,是用两个指针来维持一个窗口的大小,在左至右移动的过程中始终保持窗口内容为无重复子串。

左指针遍历

左指针遍历稍显臃肿,大概是这样的:左指针固定,每次循环中必右移一位,以此锁定新的目标子串。送走最左侧元素后,加上原串本身不含重复字符,可让右指针继续向右遍历查看能否扩张范围,从而得到左指针固定位置情况下的最大子串。具体代码见此,使用 C++ unordered_set 左指针遍历实现。

右指针遍历

右指针遍历与左指针类似,不同在于右指针每次循环必右移一位,此时被包含的新字符可能出现重复;若有重复,则移动左指针到左侧重复处的下一个位置,抛弃最左侧的一系列字符。

哈希表

遍历过程中,需要记录已包含字符的信息并以高效率检索;加之在右指针遍历时,可以使用一些技巧记录首字符出现的位置,从而直接跳到新的位置,避免循环内重复查询。具体代码见此,使用 C++ unordered_map 右指针遍历实现。

哈希集合

最简单的情况,只需要记录子串内是否有此字符即可,不必记录位置。右指针遍历时查集发现重复只需要持续收缩左指针即可,左指针遍历时查集发现无重复只需要持续扩张右指针即可。具体代码见 Python 右指针C++ 左指针C++ 右指针

数组桶

本题中为了兼容 C 语言,实际上是采用的 ASCII 码字符串,因此可以列举一个 128 大小的数组桶,实现快速查询。具体代码见 PythonC

最后发一个让我感动得哭了的代码。很 Pythonic,像是流动的诗篇。这是 LeetCode 上执行消耗内存为 12600 kb 的范例:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        b, l = 0, 0
        for i, x in enumerate(s):
            if x in s[b:i]:
                b += s[b:i].index(x) + 1
            l = max(l, i - b + 1)
        return l

萧绎是这样评价文学的审美性质的:「至如文者,惟须绮縠纷披,宫徵靡曼,唇吻遒会,情灵摇荡。」(《金楼子·立言》)

我想代码也应如是。


#4 Median of Two Sorted Arrays 寻找两个正序数组的中位数 (Hard)

四天之后才更新,本题完全败北。
题目描述是这样的:

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。
请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

我第一反应想到的是归并排序,两个队列开头的指针比较大小后并入新的数组,并且不用做完,执行到一半拿到中位数就可以了;但这样的时间复杂度是 $O(m+n)$,并不是对数级别。

说到对数级别,我就想到:二分法的时间是对数,这个想法事实上是正确的,但是怎么同时在两个数组中应用二分法呢?我最开始的思路是两个数组分别做二分,将每次的结果与另一组的结果对比大小,以此为下一次收敛搜索区域的根据。这样一来,二者的数值就会逐渐接近,最终收敛。听上去很合理,但仔细思考后会发现,这样仍然无法确定最终的内容。

其实真相很简单:两个数组两条分割线,分割线处的两个数是接近的;将这两条分割线连接起来,左侧的所有数字都小于等于右侧。并且,由于是整体的中位数,因此两侧的数字个数是相同的。这样,在对第一个数组进行二分的时候,用 $m + n$ 减去第一个数组的分割线位置则是第二个数组的分割线位置。比较麻烦的就是边界检测问题,具体的代码见此