挑戰LeetCode Weekly Contest 48

2017-09-04
#LeetCode #Python #LeetCode Weekly Contest
程式解題/ LeetCode

再度挑戰

這次的題目稍稍比上次簡單一點，前兩題解完大概還剩 20 分鐘，看看第三題好像也不難，但可惜還是沒寫完，最終成績 1170 / 2668，嗯...好像沒進步 Orz 。

第1題 671. Second Minimum Node In a Binary Tree

問題

給一棵二元樹，每一個node的子節點不是 0 個就是 2 個，輸出所有節點當中第二小的值，若不存在則輸出-1。

輸入

tree 的 root
範例：
    2
   / \
  2   5
     / \
    5   7

輸出

5

方法

遍歷所有的節點，不斷刷新最小值(下界)與第二小的值(上界)，夾擠出真正第二小的數值。

{% codeblock lang:python %} class Solution(object): def findSecondMinimumValue(self, root): if not root or not root.left: return -1 self.smallest = root.val self.second = max(root.left.val, root.right.val) self.find(root) if self.smallest == self.second: return -1 return self.second def find(self, root): if root.left and root.right: if root.left.val < self.smallest: self.smallest = root.left.val if root.right.val < self.smallest: self.smallest = root.right.val if root.left.val > self.smallest and root.left.val <= self.second: self.second = root.left.val if root.right.val > self.smallest and root.right.val <= self.second: self.second = root.right.val self.find(root.left) self.find(root.right) {% endcodeblock %}

第2題 669. Trim a Binary Search Tree

問題

給一個 binary search tree，以及正整數 L 與 R (L <= R)，修剪這棵樹使得所有節點的值介於 [L, R] 。

輸入

tree 的 root 以及 L 與 R 的值
範例：
    3
   / \
  0   4
   \
    2
   /
  1
  
  L = 1
  R = 2

輸出

新的 tree 的 root
     3
    / 
   2
  /
 1

方法

利用二元搜尋樹的特性，左子樹的值一定小於等於 root 的值，右子樹的值一定大於等於 root 的值。因此遍歷每一個節點，若 root 的值小於 L ，捨棄左子樹；若 root 的值大於 R ，捨棄右子樹。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def trimBST(self, root, L, R):
        if not root:
            return None
        if L > root.val:
            return self.trimBST(root.right, L, R)
        elif R < root.val:
            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

第3題 670. Maximum Swap

問題

給一個非負整數，問交換任兩個digit的位置所能得到的最大值為何？
給的值範圍介於 [0, 108] 之間。

輸入

2736

輸出

7236

方法

範圍介於 [0, 108] ，代表最多有 8 個digit，任選兩個的可能性只有 28 種，直接用暴力法窮舉所有的可能性。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def maximumSwap(self, num):
        maximum = num
        n = list(str(num))
        for i in range(len(n) - 1):
            for j in range(i + 1, len(n)):
                new_num = int("".join(n[0:i] + list(n[j]) + n[i+1:j] + list(n[i]) + n[j+1:]))
                if new_num > maximum:
                    maximum = new_num
        return maximum

第4題 672. Bulb Switcher II

問題

給兩個正整數n與m，分別代表燈泡的數量以及操作開關的次數，n 個燈泡依序標記為 1, 2, 3,..., n ，一開始所有的燈泡都是打開的。
有以下四種操作開關的方法：
1. 按下所有開關 2. 按下編號為偶數的開關 3. 按下編號為奇數的開關 4. 按下編號為(3k+1)的開關, k = 0, 1, 2, ...

問 n 個燈泡在操作 m 次之後，這些開關的狀態有哪些的可能性。

輸入

n = 3, m = 1.

輸出

4

方法

3 個燈泡在操作 1 次後可能的狀態為：

[off, on, off], [on, off, on], [off, off, off], [off, on, on].

一開始想說用遞迴來解，枚舉所有的可能，但是居然 TLE ，太可惡了！

{% codeblock lang:python %} class Solution(object): def flipLights(self, n, m): self.lights = [True for i in range(n)] self.times = m self.status = [] self.flipping(self.lights, 0) return len(self.status) def flipping(self, light, time): if time == self.times: if light not in self.status: self.status.append(light) return self.flipping([not v for v in light], time + 1) self.flipping([not v if (i + 1) % 2 == 0 else v for i, v in enumerate(light)], time + 1) self.flipping([not v if (i + 1) % 2 == 1 else v for i, v in enumerate(light)], time + 1) self.flipping([not v if (i + 1) % 3 == 1 else v for i, v in enumerate(light)], time + 1) {% endcodeblock %}

果然 O(2n) 還是行不通嗎，但是請仔細觀察可能的狀態，就會發現最多的可能只有八種。

n = 1, m = 0
[on]
n = 1, m >= 1
[on], [off]
--------------
n = 2, m = 0
[on, on]
n = 2, m = 1
[off, off], [on, off], [off, on]
n = 2, m >= 2
[on, on], [off, off], [on, off], [off, on]
------------------------------------------- 
n = 3, m = 0
[on, on, on]
n = 3, m = 1
[off, off, off], [on, off, on], [off, on, off], [off, on, on]
n = 3, m = 2
[on, on, on], [off, on, off], [on, off, on], [on, off, off], [off, off, off], [off, off, on], [on, on, off]
n = 3, m >= 3
[on, on, on], [off, on, off], [on, off, on], [on, off, off], [off, off, off], [off, off, on], [on, on, off], [off, on, on]
--------------------------------------------------------------------------------------------------------------------------- 
n >= 4 的情況都跟 n = 3 相同

因此根據n與m的值可以歸納出以下的結果：

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def flipLights(self, n, m):
        if n == 0 or m == 0:
            return 1
        if n == 1:
            return 2
        if n == 2:
            return 3 if m == 1 else 4
        if m == 1:
            return 4
        return 7 if m == 2 else 8