LeetCode 笔记 - 2

这几日的 LeetCode 都未搬运到博客上，恰好今天这个题有点意思，就新开一篇博文做个连载吧。（强行增加博文数目）

892. 三维形体的表面积

这一篇的题意是真的稀里糊涂很难懂啊，最后看了大神的评论解读才清晰多了。为了吐槽先扔原题题目。

在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。

每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。

请你返回最终形体的表面积。

示例 1：

输入：[[2]]
输出：10
示例 2：

输入：[[1,2],[3,4]]
输出：34
示例 3：

输入：[[1,0],[0,2]]
输出：16
示例 4：

输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32
示例 5：

输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surface-area-of-3d-shapes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

哈哈哈一开始着实是没看懂输入，但是其实输入的意思是，输入list的每个元素都是一列（如果俯视的话），然后每列的元素分别是这一列每一行的高度。例如 [[1,2],[3,4]] 表示(0,0)有1个，(0,1)有2个, (1,0) 有3个,(1,1) 有4个。

然后最直接的思路遍历正方体，然后看看空间上6个面有没有正方体，然后加上他贡献的总面积即可。

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        # [[1,2],[3,4]] 表示(0,0)有1个，(0,1)有2个, (1,0) 有3个,(1,1) 有4个
        ans = 0
        for col in range(len(grid)):
            for row in range(len(grid[col])):
                for height in range(1, grid[col][row] + 1):
                    # 正在先 x 后 y 最后 z 轴遍历每个小立方体
                    surface_area_to_add = 6  # 六个面没有立方体的正方体可以贡献6个表面积
                    if height + 1 < grid[col][row] + 1:  # 空间上方有正方体
                        surface_area_to_add -= 1
                    if height != 1:  # 空间下方有立方体 
                        surface_area_to_add -= 1
                    if col != 0 and len(grid[col - 1])>= len(grid[col]) and grid[col-1][row] >= height:
                        surface_area_to_add -= 1
                    if col != len(grid) - 1 and len(grid[col + 1])>= len(grid[col]) and grid[col+1][row] >= height:
                        surface_area_to_add -= 1
                    # 因为遍历时，如果遍历到grid[col][row],就说明一定有 grid[col][row-1], 参考循环结构
                    if row != 0 and grid[col][row-1] >= height: 
                        surface_area_to_add -= 1
                    if row != len(grid[col]) - 1 and grid[col][row+1] >= height:
                        surface_area_to_add -= 1
                    ans += surface_area_to_add
        return ans

最后空间和时间都只超过了5%…… 其实上面的代码写到一半就不想写了，感觉太不优雅了，而且读起来也很绕。想到一个表面积其实就是6个面投影的总大小，而且2个对着的面的投影面积还是一样的，所以只用遍历3个角度（想起来三视图了）。这种思路是错误的，没有考虑空心的情况。

# 错误解法！！！
class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        # [[1,2],[3,4]] 表示(0,0)有1个，(0,1)有2个, (1,0) 有3个,(1,1) 有4个
        ans = 0
        row_max_dict = {}  # 记录每一行中最高高度的dict，因为50个元素开
        for col in range(len(grid)):
            for row in range(len(grid[col])):
                if row not in row_max_dict or row_max_dict[row] < grid[col][row]:
                    row_max_dict[row] = grid[col][row]
                if grid[col][row] != 0:
                    ans += 1  # 俯视角度的面积
            ans += max(grid[col])  # 向 x 轴正方形看的角度的面积
            
        for k in row_max_dict:
            ans += row_max_dict[k]  # 向 y 轴正方形看的角度的面积
        ans *= 2            
        return ans

给出一个速度第二快而且思路非常清晰的解法。

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        res, N = 0, len(grid)
        for i in range(N):
            for j in range(N):
                if grid[i][j]:
                    res += grid[i][j] * 4 + 2
                if i > 0:
                    if grid[i][j] > grid[i-1][j]:
                        res -= grid[i-1][j] * 2
                    else:
                        res -= grid[i][j] * 2
                if j > 0:
                    if grid[i][j] > grid[i][j-1]:
                        res -= grid[i][j-1] * 2
                    else:
                        res -= grid[i][j] * 2
        return res
        # 这个版本的思路 加减分明
        # + 如果网格有方块 加上上下2 四面v*4
        # - 如果是有 相邻的摆放 减去重叠的部分 较小的v*2

820. 单词的压缩编码

这一题的题目解释依旧硬核。。先扔原题。

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：

输入: words = [“time”, “me”, “bell”]
输出: 10
说明: S = “time#bell#” ， indexes = [0, 2, 5] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/short-encoding-of-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

大意就是如果一个单词能作为另一个单词的尾部出现，他就可以不用单独写出来，然后每个需要单独写出来的单词之间隔一个 “#” 做标识符，随后统计这个总的长度即可。

看到题解和评论还可以用 Trie 树，大概看了一下基本思路感觉还是会繁琐一点，直接将所有单词倒序，然后将倒序后的列表排个序，由于字符串排序是按照字符位置一个一个排序的，第一位相同的会排在一起，这就很方便了，此外短的在前，长的在后，我们只要比较每个倒序单词是否是下一个倒序单词的开头即可，如果不是，说明当前的单词不能被压缩进别的单词，给他单独存入结果，所以最终结果增加该单词的长度+1（1是 # 的长度）。

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        if len(words) == 1:
            return len(words[0]) + 1
        ans = 0
        char_reversed_words_list = []
        for word in words:
            char_reversed_words_list.append(word[::-1])  # 将每个word倒序存进去
        char_reversed_words_list.sort()
        for i in range(len(char_reversed_words_list) - 1):  # 最后一个不用测试，他肯定不能被包括在其他字符串的尾部
            if not char_reversed_words_list[i + 1].startswith(char_reversed_words_list[i]):
                ans += len(char_reversed_words_list[i]) + 1
        return ans + len(char_reversed_words_list[-1]) + 1

上面的代码最终用时 120 ms ，超过90%+ 的提交。

面试题62. 圆圈中最后剩下的数字

2020.3.20 每日一题。这次的题目非常简单，大致就是 n 个数字围成环，然后从第一个数字开始往后报数，报数到M 时，这个数字出列，从下个数字继续开始报数，最后没出列的数字。

这里有一篇非常清晰的介绍：https://blog.csdn.net/u011500062/article/details/72855826大致原理就是从最后一轮逆推整个过程。假设每次删去一个数字后，下一个数字的索引为0，这就意味着每次删去数字时，所有数字的索引减少M，如果小于0则要加上N（循环的），或者说是$ i = (i - M) mod N$ （设索引为 i ）。那么反过来我们知道当最后一个剩余的数字（我们叫他winner）活下来的时候，他的 i = 0. 我们可以倒退至倒数第二轮，只有两个数字的时候，如果当时 winner 的 索引 为 $i_w$，则有
$$
(i_w - M) \equiv i\ (mod\ 2 )
$$
那么一层一层往上递推的时候，只需要更改 mod 2 为当时的 N 即可。最终的代码如下。

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        winner_index = 0
        for i in range(2,n + 1):
            winner_index = (winner_index + m) % i
        return winner_index

1111. 有效括号的嵌套深度

2020.4.1 每日一题。又是一道读题读好久的题目……

大概就是说，输入字符串肯定是合格的字符串（有效括号字符串），就是每个左括号都有一个右括号。不会出现一个单独的右括号这些非法情况。再引入嵌套深度的概念，’(())’ 就是嵌套两层。这个比较好理解，一直数着左括号的个数，遇到左括号加一，遇到右括号减一就行了。然后题目就是问，一个输入的合法字符串，可以把每个字符分配给A或者B，分配完后必须保证A和B也是合法的，在保证合法的前提下，要让 A 和 B 的最大深度最小。

比如说 s = '(())()'这个例子，很明显如果把它当做一个字符串来看，深度是2。但是如果我把 s[1], s[2] 分给 B ，剩下的字符分给 A，就可以发现 A = ()() ，B = ()。A和B的最大深度变成了1.这就达到目标了，当然要达到目标往往有多种方案，而且A和B互换就是一个新的方案。题目要求随便给个方案就行。输出一个和输入字符串长度一样的列表，每个位置对应字符串的每个字符，如果是 0 分给 A，如果是1表示分给B。

然后解题思路就是，每次遇到左括号就压栈，遇到右括号就出栈，然后对于左括号随着深度增长交替分给A和B，比如 (())这种类型的，深度为1和其他奇数时，左括号分给A，深度为2和其他偶数时，左括号分给B，然后右括号只要分给和对应左括号一样的就可以了。这样交替的来就可以保证总的最大深度最小。因为一个字符串输入进来，本身深度就是给定的，那么极限情况就是一半深度A来分担，另一半深度B来分担，达到深度最小。

最后的代码如下。

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        depth = 0
        result = []
        for c in seq:
            if c == '(':
                result.append(depth % 2)
                depth += 1
            else:
                depth -= 1
                result.append(depth % 2)
        return result

887. 鸡蛋掉落

2020.4.11 每日一题。题目非常经典，就不在这里赘述了。

下面给出 动态规划 的转移方程。
$$
dp(K,N) = 1 + \min_\limits{1\leq X \leq N}{(\max{(dp(K-1,X-1),\ dp(K,N-X))})}
$$
括号从里到外逐层理解，首先我们要求的是一个函数，K是剩余鸡蛋，N是所有的楼层数目，X是测试的楼层号。

对于每一次测试，有两种可能，碎了或者没碎。对于碎了的情况，我们相当于是 $dp(K-1,X-1)$ ，即只考虑剩下的 K - 1 个蛋，以及 X - 1 层楼的情况。对于没碎的情况，则是 $dp(K,N-X)$ ，即还有K个蛋，但是 既然我们确定 X 楼不会碎，我们把 K 楼楼顶当做新的地平面，问题就又回归了，只不过原来的每一层楼的楼层号都减了 X，所以我们所有的楼层数目也是 N - X。由于鸡蛋到底从几楼开始碎是变量，我们是说不准的，所以我们也不知道对于每个 X，鸡蛋是否会碎，但是题目问的是 最坏情况 ，所以我们要取碎了或没碎两种情况的最大值。也就是说我们要让鸡蛋无论在哪楼碎，我们都能够解决最坏的情况。那最后的这个外面的 min 又是什么意思呢？这也正是最终我们这道题的目标，我们不知道把 X 设为几合适，也就是说对于 $dp(K,N)$ 这个问题，我们不知道 X 取什么的时候能够尽可能压低测试次数。所以我们就把 X 从 1 到 N 都试试，无论 X 等于几，其实最后 dp 递归到最后都能求解，但是我们希望能求解出来这个 X。对于任意的 $dp(K,N)$ ，他的 X 是唯一的。

时间复杂度的分析的话，首先由于我们要造一个二维数组，对于每个K和N，所以基准就是 KN，对于这 KN 个元素，我们每个都要跑一遍 X 从 1 到 N，所以最后复杂度是 $O(KN^2)$ 。但是这样复杂度达不到要求，优化方法就是，在找每个 dp 的X的时候，由于 X 是唯一的，就在 N 的这个范围里使用 二分查找，于是可以把每个元素的复杂度从 N 降到 logN。最终总的复杂度是 $O(KN\log(N))$.

说的再详细一点，关于怎么找唯一的 X，我们知道二分查找的前提是有序。而 dp 的 min 函数里面的 $\max{(dp(K-1,X-1),\ dp(K,N-X))}$ 的函数图像很有意思，关于 X，首先是单调递减，然后是单调递增（即 max 先是 后面的 $dp(K,N-X)$ ，然后是前面的。）而这样就一定有一个最低点，我们只要找到最低点或者最低点左边的那个整数就好（最低点有可能不是整数）。