Leetcode【939、1048】

问题描述：【Hash Table】939. Minimum Area Rectangle

解题思路：

最小面积矩形。给一个坐标列表，计算这些坐标可以组成的最小矩形面积，其中矩形平行于 x 轴和 y 轴。

这是一道 Google 面试题。可以使用暴力破解：

1、定义一个集合 set，初始为空，用于记录访问过的点； 2、遍历列表，从中选出第一个访问点 [x1, y1]； 3、遍历 set，从 set 中选出第二个点 [x2, y2]（也就是先确定对角线上的点），然后判断 [x1, y2] 和 [x2, y1] 是不是在 set 中，这样就可以判断出是否存在由 [x1, y1] -> [x2, y2] 形成的矩形，并更新最小面积值； 4、将访问过的 [x1, y1] 添加到一个 set 中；

注意：步骤 4 一定要放到步骤 3 之后，因为 [x1, y1] 和 [x2, y2] 不能是同一个点。

因为要对列表和集合 set 进行双层循环遍历，因此时间复杂度为 O(n^2)，空间复杂度为 O(n)。

Python3 实现：

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        N = len(points)
        min_ = float("inf")
        setp = set()  # 保存访问过的点
        for x1, y1 in points:  # 对于列表中的每一个坐标
            for x2, y2 in setp:  # 对于集合中的每一个坐标
                if (x1, y2) in setp and (x2, y1) in setp:
                    min_ = min(min_, abs(x2-x1)*abs(y2-y1))
            setp.add((x1, y1))  # 将访问过的[x1,y1]添加到set中
        return min_ if min_ != float("inf") else 0

问题描述：【Hash Table+DP】1048. Longest String Chain

解题思路：

最长字符串链。给一个单词列表，找一个词链，使得词链后一个单词由前一个单词增加一个字符得到，求最长词链长度。

1、根据词链的定义，短的单词可以由长的单词减去单词中一个字符得到。因此可以先对单词列表，按照单词的长度从大到小排序。 2、单词的最大长度为 16，因此可以对于每个单词 word（已经按长度从大到小排好序了），遍历 word 所有长度减 1 的子串（共有 len(word) 个）。 3、为了记录最长词链的长度，可以定义一个字典 dic，键为单词，值为以该单词为首的最长词链长度。dic 相当于动态规划中的 dp 数组，接下来要找状态转移方程。 4、对于单词 word 的每一个子串 sub，如果 sub 在单词列表中能够找到（这里为了加快查找速度，要先将单词列表转化为集合 set，查找速度为 O(1)），则该子串 sub 的最长词链长度取决于原来 sub 的最长词链长度与在 word 的最长词链长度基础上加 1 中的最大值，即 dic[sub] = max(dic[sub], dic[word] + 1)。 5、最后，如果 dic 为空，则返回 1；如果不为空，则字典中某个字符串保存的最长词链长度就是最终的答案，即 max(dic.values()) + 1。

如果单词列表长度为 n，单词长度为 m，则时间复杂度为 O(n*m*m)，空间复杂度为 O(n)。

Python3 实现：

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        setw = set(words)
        words.sort(key=lambda x: len(x), reverse=True)  # words.sort(key=len, reverse=True)
        dic = collections.defaultdict(int)  # dp数组，记录每个单词的最长词链长度
        for word in words:
            for i in range(len(word)):
                sub = word[:i] + word[i+1:]  # 对于word的每一个子串sub
                if sub in setw:  # 查找时间为O(1)
                    dic[sub] = max(dic[sub], dic[word] + 1)  # 状态转移方程
        return max(dic.values()) + 1 if dic else 1  # dic可能为空