这次比赛有点简单的样子。

第一题Second Minimum Node In a Binary Tree

给定一棵特别的二叉树，这棵二叉树的节点要么有两个子节点，要么没有节点。如果有两个子节点，那么该节点的值为子节点的最小值。求树的第二最小值。

我当时什么都没有想，简单地将树的所有值取下来排序取出第二最小值。

# 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 findSecondMinimumValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        nums = set()
        def dfs(root):
            if not root:
                return
            nums.add(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return -1 if len(nums)<2 else sorted(list(nums))[1]

第二题Trim a Binary Search Tree

给定一棵搜索二叉树，以及两个值L和R（L <= R），要求只保留节点值在L和R之间节点，返回修改之后的树的根节点。

比较简单的DFS。

# 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 trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        if not root:
            return None
        if root.val < L:
            return self.trimBST(root.right, L, R)
        if root.val > R:
            return self.trimBST(root.left, L, R)
        root.left = self.trimBST(root.left, L, R)
        root.right = self.trimBST(root.right, L, R)
        return root

第三题Maximum Swap

给定一个非负整数，现在可以最多交换两个数字的位置一次，返回可能得到的最大值。

贪心算法。从左到右找到第一个要换的数字，然后从剩下的数字中从右到左找出被换数字。比如9937474，从左到右我们找到要被换的数字3，而且我们知道要用7来换。关键的是我们需要从右往左寻找第一个7，用这个7来换3，所以得到答案：9977434

class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num == 0:
            return 0
        ln = []
        while num > 0:
            ln.append(num % 10)
            num /= 10
        ln = ln[::-1]
        tmp = sorted(ln, key=lambda x: -x)
        i = 0
        while i < len(ln) and ln[i] == tmp[i]:
            i += 1
        if i < len(ln):
            j = len(ln)-1
            while ln[j] != tmp[i]:
                j -= 1
            ln[i], ln[j] = ln[j], ln[i]
        ans = 0
        p = 1
        for n in ln[::-1]:
            ans += n*p
            p *= 10
        return ans

其实枚举所有可能性也是可以的：

class Solution(object):
    def maximumSwap(self, num):
        """
        :type num: int
        :rtype: int
        """
        ans = num
        num = str(num)
        for i in xrange(len(num)):
            for j in xrange(i+1, len(num)):
                c = list(num)
                c[i], c[j] = c[j], c[i]
                ans = max(ans, int(''.join(c)))
        return ans

第四题Bulb Switcher II

有n盏灯4个开关，初始状态的时候所有灯都是亮的。这n盏灯编号为[1, 2, ..., n]，4个开关的功能分别为

  1. 改变所有灯的状态；
  2. 改变所有偶数的灯的状态；
  3. 改变所有奇数的灯的状态；
  4. 改变所有(3k+1)的灯的状态。

根据mod 6将所有灯分成6类：1，2，3，4，5，6。所有的开关只会对这6类灯操作。

开关1改变：1，2，3，4，5，6
开关2改变：2，4，6
开关3改变：1，3，5
开关4改变：1，4

根据上面的分析，我们可以进一步将6类缩减成四类：A＝（1），B＝（2，6），C＝（3，5），D＝（4）。这样开关所控制的情况为：

开关1改变：A，B，C，D
开关2改变：B，D
开关3改变：A，C
开关4改变：A，D

一开始的时候我们用b1111=15来表示所有状态ABCD，那么开关分别对应15，5，10，9。开关的操作相当于与运行。现在只要枚举所有情况即可。

class Solution(object):
    def flipLights(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        ans = set([15])
        btn = [15, 10, 9, 5]
        mask = (1 << min(n, 4)) - 1
        for i, n in enumerate(btn):
            btn[i] = n & mask
        for _ in xrange(m):
            tmp = set()
            for n in ans:
                for b in btn:
                    tmp.add(n ^ b)
            ans = tmp
        return len(ans)
leetcode contest