开篇记录面试第69天

这次换工作战线确实拉的太长了，连我自己都快不记得最开始的面试是什么状态了。上周五面了瓜子的终面，缺在基础知识不够了，当时问几种排序方法的复杂度和特点，没答好，然后下午面博彦科技，问了各种建模、优化之类的问题，评价是我没有对数据的把控，没有数据的感觉，当时还觉得挺感激面试官的，还跟我说一定要把事情想的难一点，做的难一点，让别人无法短期复制你的工作，建立自己的不可替代性。
说多了。好好准备面试吧。今天年中绩效给了C，估计离劝退不远了。

今天做了两道LeetCode题目：

1. 543#二叉树的直径
   给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
   解答：题目很容易看出来，直径就是根节点的左右子树的深度和，所以用深度优先遍历来计算左右子树的深度的和，再加1就是结果了。递归的方式是dfs调用左右子树，返回左右子树中深度较大的一个加1的结果，作为该子树的深度，用一个变量记录最终的深度和。

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = 0
        
        def dfs(root):
            if root is None:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            self.ans = max(self.ans, left + right)
            return max(left,right) + 1
        dfs(root)
        return self.ans

2. 581# 最短无序连续子数组
   题目：给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。
解答：这个题目最简单的思路是对数组进行排序，然后找出跟排序后数组数字不能一一对应的起始点和终止点，但是这种解法复杂度比较高。有一种O(n)的方法是，用两个指针，一前pre一后after，从两端开始遍历，用两个变量max和min记录遍历到当前时的最大值和最小值，如果pre位置的值小于max，则pre更新，如果after的值大于min，则after更新位置。

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_i, min_i, n = nums[0], nums[-1], len(nums)
        j, k = -1, 0
        for i in range(n):
            max_i = max(max_i, nums[i])
            if nums[i] < max_i:
                j = i
            min_i = min(min_i, nums[n-i-1])
            if nums[n-i-1] > min_i:
                k = n-i-1
        return j-k+1

3.617# 合并二叉树
题目：给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
解答：这个题目也是用到递归，遍历到两个树的对应节点时，如果两个节点都不为空，则相加，如果一个为空，则返回另一个的值。

class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        # 如果两个节点都存在，则相加
        # 如果有一个不存在，则函数返回另一个
        if not t1:
            return t2
        if not t2:
            return t1
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        return t1