今晚肉特别多：红烧羊肉，焖排骨，手撕鸡和罗非鱼。

第一题Reverse Words in a String III

题目大意：给定一个句子，将其中所有单词逆序。
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        lst = s.split(' ')
        for i in xrange(len(lst)):
            if lst[i] == '':
                continue
            lst[i] = ''.join(reversed(lst[i]))
        return ' '.join(lst)

第二题Brick Wall

题目大意：有一面长方形的墙，所有的砖高度一样，但是宽度不一样。现在给定这面墙所有砖的数据：数据的每一行代表一行的砖头，每个数字代表砖头的宽度。问在墙之间劈一刀，问劈到砖头的最少数目。

我的想法：反过来想，我们可以求解劈的时候能避开切断砖头的最大行数，那么劈到砖头的最少数目就是砖的行数减去避开的最大行数。要避开切断砖头，那么就必须从两个砖头之间的缝隙切下去。所以我们就统计缝隙出现的位置就行。

class Solution(object):
    def leastBricks(self, wall):
        """
        :type wall: List[List[int]]
        :rtype: int
        """
        cnt = {}
        for row in wall:
            s = 0
            for w in row[:-1]:
                s += w
                cnt[s] = cnt.get(s, 0) + 1
        m = 0
        for _, v in cnt.items():
            m = max(m, v)
        return len(wall) - m

第三题Next Greater Element III

题目大意：一个32位的正整数n，用n的数字重组一个比n大的最小数。如果这个数不存在，或者不是32位的，则输出－1。

这题不难，就是很多细节要注意。我就是一直没有注意细节，WA了5次 :disappointed: 我以一个例子说明我的做法吧。比如给定12443322，我们从倒数第二个数字出发，找到第一个比后面数字小的数。在这个例子里，应该是第二位的2，因为它比后面的4小。然后从这个2后面挑一个比2大的最小数，是3。然后交换2与3的位置得到13442322，最后将该3后面的数从小到大排序得到13222344。注意的是，新得到的数不能大于或者等于 231！！

class Solution(object):
    def nextGreaterElement(self, n):
        """
        :type n: int
        :rtype: int
        """
        d = []
        m = n
        while m > 0:
            d.append(m % 10)
            m /= 10
        i = 1
        while i < len(d) and d[i] >= d[i-1]:
            i += 1
        if i == len(d):
            return -1
        j = i
        while j - 1 >= 0 and d[j-1] > d[i]:
            j -= 1
        d[i], d[j] = d[j], d[i]
        d[:i] = sorted(d[:i], reverse=True)
        p = 1
        ans = 0
        for i in d:
            ans += i * p
            p *= 10
        return ans if ans < 2 ** 31 else -1

第四题Binary Tree Longest Consecutive Sequence II

题目大意：给定一颗树，在其中找出最大长度的路径使得其路径上的数字是递增或者递减的连续数字。

我的想法：对于每个节点，递归算出从该节点往下的最长递增路径长度inc以及最长递减路径长度dec，那么经过该节点的最大长度是inc+dec-1。在所有的inc+dec-1中挑出最大值就好。

# 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 longestConsecutive(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = [0]
        def dfs(root):
            if not root:
                return 0, 0
            dec = inc = 1
            if root.left:
                d, i = dfs(root.left)
                if root.val == root.left.val + 1:
                    dec = d + 1
                elif root.val == root.left.val - 1:
                    inc = i + 1

            if root.right:
                d, i = dfs(root.right)
                if root.val == root.right.val + 1:
                    dec = max(dec, d+1)
                elif root.val == root.right.val - 1:
                    inc = max(inc, i+1)

            ans[0] = max(ans[0], dec + inc - 1)
            return dec, inc

        dfs(root)
        return ans[0]
contest leetcode