Leetcode Contest 29 | 叶某人的碎碎念

今晚有鱼、豆腐和西芹。

这次比赛是久违的全一次就AC了，开心😎

第一题Binary Tree Tilt

题目大意：对于一个二叉树节点，定义它的tilt为左子树之和与右子树之和差的绝对值。给定一棵二叉树，求出所有节点tilt值之和。

感觉是简单的dfs套路。对于每个节点，递归算左右子树之和，那么它的tilt值就很容易求出来加到一个全局的变量里，然后返回当前子树之和：左子树+右子树+根节点

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

class Solution(object):
    def findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = [0]

        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            ans[0] += abs(left-right)
            return left+right+root.val

        dfs(root)
        return ans[0]

第二题Array Partition I

题目大意：给定一个长度为2n的整数数组，可以任意将它们分成n对 (a₁, b₁), ..., (a_n, b_n) 求sum(min(a_i, b_i))的最大可能值。

首先将数组排序，然后将第0，2，...，2n－2的位置加起来就行。证明也很简单，这里就忽略了。

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return sum(nums[i] for i in xrange(0, len(nums), 2))

第三题Longest Line of Consecutive One in Matrix

题目大意：给定一个01二维数组M，求数组中在一条线上的连续是1的最大长度。这里的线只允许水平线，垂直线，对角线和反对角线。

我是直接暴力枚举的。枚举行i和列j，如果当前是1，那么就分别算出以其为首的四种线的最大长度，然后更新答案。为了避免重复计算，我开了四个跟M一样大的二维数组。

有另一种只需要O(1)空间枚举方法的。枚举所有的行，列，对角线和反对角线，然后求这些线上的所有连续1的长度，以更新答案。

我当时衡量了一下，用了第一种枚举方法。下面就是第一种枚举方法的实现。

class Solution(object):
    def longestLine(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        n = len(M)
        if n == 0:
            return 0
        m = len(M[0])
        if m == 0:
            return 0

        row = [[False] * m for _ in xrange(n)]
        col = [[False] * m for _ in xrange(n)]
        dia = [[False] * m for _ in xrange(n)]
        ant = [[False] * m for _ in xrange(n)]
        ans = 0
        for i in xrange(n):
            for j in xrange(m):
                if M[i][j] == 0:
                    continue
                if not row[i][j]:
                    k = j
                    while k < m and M[i][k] == 1:
                        row[i][k] = True
                        k += 1
                    ans = max(ans, k-j)
                if not col[i][j]:
                    k = i
                    while k < n and M[k][j] == 1:
                        col[k][j] = True
                        k += 1
                    ans = max(ans, k-i)
                if not dia[i][j]:
                    k, t = i, j
                    while k < n and t < m and M[k][t] == 1:
                        dia[k][t] = True
                        k += 1
                        t += 1
                    ans = max(ans, k-i)
                if not ant[i][j]:
                    k, t = i, j
                    while k < n and t >= 0 and M[k][t] == 1:
                        ant[k][t] = True
                        k += 1
                        t -= 1
                    ans = max(ans, k-i)
        return ans

第四题Find the Closest Palindrome

题目大意：给定代表一个正整数的字符串，返回一个离它最近的回文数（不包括它本身）。两个数的距离是由它们的差的绝对值定义。如果存在两个最佳答案，那么返回较小的答案。

我的想法：分别求出比n小和比n大的回文数，然后从中挑个最佳的。因为求比n小和比n大的回文数的思路是一样的，所以我这里只解释一下怎么求比n小的回文数。

求比n小的回文数步骤：
第一步：将n前一半反序放在n的后一半上，如果新得到的回文数m比n小，返回m，不然进入第二步。
第二步：将n的前一半减去1，后一半全部变成9，如果得到的是一个回文数，那么返回这个回文数，不然回到第一步。

class Solution(object):
    def nearestPalindromic(self, n):
        """
        :type n: str
        :rtype: str
        """
        def smaller(n):
            m = list(n)
            for i in xrange(len(m)/2):
                m[len(n)-1-i] = m[i]
            m = ''.join(m)
            if m < n:
                return m
            n1 = str(int(n[:(len(n)+1)/2])-1)
            n2 = '9' * (len(n) - (len(n)+1)/2)
            if n1 != '0':
                n = n1+n2
            else:
                n = n2
            if n == '':
                return '0'
            if n == n[::-1]:
                return n
            return smaller(n1+n2)

        def bigger(n):
            m = list(n)
            for i in xrange(len(m)/2):
                m[len(n)-1-i] = m[i]
            m = ''.join(m)
            if m > n:
                return m
            n1 = str(int(n[:(len(n)+1)/2])+1)
            n2 = '0' * (len(n) - (len(n)+1)/2)
            n = n1+n2
            if n == n[::-1]:
                return n
            return bigger(n1+n2)

        s = smaller(n)
        b = bigger(n)
        if int(n)-int(s) <= int(b)-int(n):
            return s
        else:
            return b

leetcode contest