LeetCode 笔记 - 1

已经刷了 3 天的 LeetCode 每日一题，感觉还是相当的有趣的。但是为了避免自己把查到的知识不久又忘掉，将结题的一些笔记记录在这里。

543. 二叉树的直径

2020年3月10日每日一题。要求在在一棵二叉树中找到直径，所谓直径就是任意两个节点的最大距离。值得一提的是，直径不一定过根节点，看评论好多人都被这个迷惑了。

感觉题目是很典型的分治思想（虽然还没有好好学过算法就开始大用专业名词了），我们最终是记录每个节点以及其两个子树的整体内的直径；因为对于一棵二叉树，其直径只有可能是：

• 左子树的直径（最大距离根本没有过根节点）
• 右子树的直径（最大距离根本没有过根节点）
• 左子树的深度 + 右子树的深度。（因为既然包括了根节点，那么左边子树中离根节点的最远距离就是左子树的深度，右子树同理，两边连起来正好是两边深度相加）

另外刚刚在搜索资料时甚至对树的深度的定义都开始犹豫，哈哈哈数据结构还给书本了。

定义一棵树的根结点层次为1，其他结点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。

但是归根结底，任何的直径一定是某个节点的 左子树的深度 + 右子树的深度。我们只要一路遍历节点，记录最大值。顺便求出来左子树和右子树的深度即可。所以其实这个问题的核心就转向了求深度。深度直接递归调用自身，然后将左右子树返回结果各自加一，取最大值再返回即可。

另外，对于输入为 [] 的情况，也就是空树，需要 return -1, 否则会出 Exception。

最终 AC 代码。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if root == None:  # None Case
            return 0
        result = -1
        def depth(node: TreeNode):
            nonlocal result
            left = 0
            right = 0
            if node.left != None:
                left = depth(node.left) + 1
            if node.right != None:
                right = depth(node.right) + 1
            result = max(left + right, result)
            return max(left, right)
        depth(root)
        return result

1013. 将数组分成和相等的三个部分

2020年3月11日每日一题。给定一个整数数组，判断该数组是否能找到一种分割，使得分出的三个部分和相等。（顺序不可变化）

由于我们知道如果和不能是 3 的倍数的话，肯定是不能将整型 List 分割成和相等的三份的。所以先判断一下数组的和，然后如果模 3 为 0 的话，就继续并顺便保存一下 sum / 3。因为分出的3个段肯定和都是这个总和的三分之一。接下来遍历数组，每遍历一个就加上他的值，如果加上以后恰好为前面提到的 1/3 ，就清空这个计数，然后记录一下有一段满足条件。只要找到了2端并且后面还有数组元素，就可确定后面的和也必定是之前的1/3 ，停止遍历。

值得一提的是上面的方法经过了优化，其实我最初的想法是遍历完 List，统计和等于1/3 sum 的段，只有这个段的数目正好为 3 时，返回 true，否则就是 false。但是这种算法在遇到输入 为 [1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1] 的时候就出错了，因为算法找到了好几个和等于 1/3 sum （即 0 ） 的段。其实正确的答案是 True，但是算法会返回 False。遇到报错以后我的最直接想法是，直接判断是否大于 3 个段，且 1/3 sum == 0 。因为如果是 0 的话就可以任意组合。这样改算法以后也可以 AC 。但是看了评论后才知道了最精巧的解法，也就是前面一开始说的思路，只要找到 2 端和等于 1/3 的段，且后面还有元素，就说明可以了，可以避免刚刚和为 0 的输入出错。

class Solution:
    def canThreePartsEqualSum(self, A: List[int]) -> bool:
        ListSum = sum(A)
        if ListSum % 3 != 0:
            return False
        oneThird = ListSum / 3
        tmpSum = 0
        validPart = 0
        for num in A:
            if validPart == 2:
                return True
            tmpSum += num
            if tmpSum == oneThird:
                validPart += 1
                tmpSum = 0        
        return False

695. 岛屿的最大面积

2020 年 3 月 15 日 每日一题，前几日的题也不算难，就偷了几日懒没有记录做题笔记。。

这道题是给一个二维数组，里面只有可能是 0，1。设1是陆地，0是海洋，找出最大的岛屿，岛屿只能上下左右连接，不能对角线连接。

解题思路是典型的DFS。拿到一个格子检查其四面的格子是否是陆地，是的话递归调用，每递归一次记录当前陆地数目，最后统计求和即可。值得一提的是，一开始还按着 以前的思路 想搞一个 Visited 数组，然后发现自己居然不会声明二维数组（第一次感觉自己 C 比 python 好），然后看了别人的评论发现不用呀，直接把传入的参数数组对应位清 0 就好了。正好之后就不会再重复调用函数了。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        x_len = len(grid)
        y_len = len(grid[0])
        def dfs(x, y) -> int:
            if x < 0 or y < 0 or x >= x_len or y >= y_len or grid[x][y] == 0:
                return 0
            retValue = 1
            grid[x][y] = 0
            for delta_x, delta_y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                retValue += dfs(x+delta_x,y+delta_y)
            return retValue
        answer = 0
        for i in range(x_len):
            for j in range(y_len):
                answer = max(answer, dfs(i, j))
        return answer

初版的通过代码如上所示，最后速度上只击败了6%的代码…… 参考了最快的代码，原来我是先递归进去判断这个格子是不是陆地，而最快的代码时判断这个格子是不是陆地再递归，这样减少了函数栈的操作，所以能加速运行。

改进的代码如下所示，这回速度超越了93%的代码。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        x_len = len(grid)
        y_len = len(grid[0])

        def dfs(x, y) -> int:
            retValue = 1
            grid[x][y] = 0
            if x - 1 >= 0 and grid[x - 1][y] == 1:
                retValue += dfs(x - 1, y)
            if x + 1 < x_len and grid[x + 1][y] == 1:
                retValue += dfs(x + 1, y)
            if y - 1 >= 0 and grid[x][y - 1] == 1:
                retValue += dfs(x, y - 1)
            if y + 1 < y_len and grid[x][y + 1] == 1:
                retValue += dfs(x, y + 1)
            return retValue

        answer = 0
        for i in range(x_len):
            for j in range(y_len):
                if grid[i][j] == 1:
                    answer = max(answer, dfs(i, j))
        return answer

1160. 拼写单词

2020 年 3 月 17 日 每日一题。给一个单词数组（字符串数组）和一个字符数组（字符串，其实python里没有字符数组的概念了），如果一个单词可以用字符数组里的字符拼出来，就说掌握了这个单词，注意字符数组元素可重复，且每次拼写时其中每个元素只可用一次。最后输出掌握单词总长度。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• 所有字符串中都仅包含小写英文字母

最直接简单的思路是过每个单词，用 Python 内置的 count 函数处理，但是其实用 count 有可能会出现重复的调用。先贴出最初的代码。

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        ret_value = 0
        for word in words:
            for c in word:
                if word.count(c) > chars.count(c):
                    break
            else:
                ret_value += len(word)
        return ret_value

然后我们用哈希表优化，使其不用重复调用 count 。然而跑出来的结果并没有优化多少。

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        ret_value = 0
        chars_count = {}
        for c in chars:
            if c not in chars_count:
                chars_count[c] = chars.count(c)
        for word in words:
            for c in word:
                if c not in chars_count or word.count(c) > chars_count[c]:
                    break
            else:
                ret_value += len(word)
        return ret_value

看了所有解答中，最快的两个答案，第一个答案如下所示，就是不用 count ，自己手写，第二个则是与我前面的最开始的解答完全一样，只不过用的是标志位，我用的是 for … else 。然鹅他时间是我的 1/2 …… 时间第一由算法复杂度决定，第二由运气决定可还行。

class Solution: # 最快的解答
    def countCharacters(self, words: List[str], chars: str) -> int:
        mine = {}
        res = 0
        for c in chars:
            if c not in mine:
                mine[c] = 0
            mine[c] += 1
        for w in words:
            tmp = mine.copy()
            yes = 1
            for t in w:
                if t not in tmp or tmp[t] <= 0:
                    yes=0
                    break
                tmp[t] -= 1
            if yes:
                res+=len(w)
        return res

409. 最长回文串

给定一个包含大写字母和小写字母的字符串，找出由这些字母能组成的最长回文串长度。回文串严格区分大小写。

这道题的核心思路在于统计各个字母的出现频度，如果出现偶数次，则其的每次出现都可以扔到最长回文串中。但若是奇数次（设为n），则只有 (n - 1) 次出现可以扔到最长回文串中。还需注意的一点是，最后所有奇数出现的字符中，可以挑一个扔进最长回文串中（突然想到复活赛什么鬼）。

最开始按照这个思路，编写了代码如下。

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count_dict = {}
        ans = 0
        for c in s:
            if c not in count_dict:
                count_dict[c] = 1
            else:
                count_dict[c] += 1
        for v in count_dict.values():
            if v % 2 == 0:
                ans += v
            else:
                ans += v - 1
        if ans < len(s):
            ans += 1
        return ans

结果发现速度垫底……思来想去觉得已经很好了啊。于是去偷看了速度第一的代码。

class Solution: # 速度最快的实现，LeetCode 不显示作者信息
    def longestPalindrome(self, s: str) -> int:
        # i = 0
        # j = len(s) -1 
        # max_sub_str = []
        # while i < j:
        #     if s[i] == s[j]:
        #         max_sub_str.append()
        a = set(s)
        b = list(a)
        oddc = 0
        flag = 0
        for i in range(len(b)):
            c = s.count(b[i])
            if c % 2 != 0:
                oddc += 1
                flag = 1
        l = len(s) - (oddc - flag)
        return l

前面一堆注释可能是后来改了，看后面，我们发现他的思路是减回去而不是加上去，这样他在遍历 b 时（其实等效于我遍历哈希表），只需要对奇数出现的字符做操作，偶数是没有 else 的，这样可以少做一点操作。最后如果出现过奇数的元素，加一（即flag的作用），减去所有奇数字符个数即可。于是我用类似的思路优化了代码如下。

class Solution:
    def longestPalindrome(self, s: str) -> int:
        count_dict = {}
        odd_count = 0
        flag = 0
        for c in s:
            if c not in count_dict:
                count_dict[c] = 1
            else:
                count_dict[c] += 1
        for v in count_dict.values():
            if v % 2 != 0:
                odd_count += 1
                flag = 1
        return len(s) - odd_count + flag

结果超越了 86% 的用户，可是时间几乎还是他的两倍…… 不过也不强求了，理论上来说，他对每一种出现了的字符调用 count，对于 s 的遍历要更多，而我只遍历了一次 s ，应该这方面更快啊…… 可能的原因是 count API 实现有骚操作？或者我使用 dict，哈希表有额外运算？再或者大概就是测试集差异，纯看运气了……

PS：换成 count 以后创下了几次提交中的最慢记录……