挑戰LeetCode Weekly Contest 47

2017-08-28
#LeetCode #Python #LeetCode Weekly Contest
程式解題/ LeetCode

前言

這次心血來潮報名了 LeetCode 每周都會舉辦的比賽，規則是在1.5小時之內要解出4題，這對我來說是一大挑戰啊！因為以往參加的比賽，時間都是3小時左右，這麼短的時間內要解出4題真的不容易，不過既然都報名了就全力以赴吧！

第1題 665. Non-decreasing Array

問題

給定一個長度為 n 的整數陣列，問是否能在最多更改 1 個數的情況下，將陣列變成 non-decreasing array，也就是遞增的陣列。

輸入

[4, 2, 3]

輸出

True

方法

我的策略是分別從頭尾出發走一次，若遇到下一個數 pj 小於/大於目前這個數 pi 的話，就將下一個數的值改為目前這個數，使得目前為止的元素為遞增的狀態，此時修改的次數就會增加一次。若分別從頭尾走，修改的次數都大於一次的話，代表無法符合題目的條件，回傳False，反之回傳True。
那為什麼要分別從頭尾走一次呢？ 以範例的輸入當例子，若只從正方向走， (4, 2) 不符合遞增，將 2 改成 4，陣列變成 [4, 4, 3]，接著遇到 (4, 3) 又不符合遞增，因此只修改一個值並不能使原本的陣列變成遞增數列。
但是錯啦！其實只要把第一個數 4 改成 1 或 2 就可以了，想到從反方向走的話好像可以達到這個效果，所以必須要檢查兩個方向才能確保沒有漏網之魚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def checkPossibility(self, nums):
        n = list(nums)
        edit_time_1 = 0
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                nums[i + 1] = nums[i]
                edit_time_1 += 1

        nums = n
        edit_time_2 = 0
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] < nums[i - 1]:
                nums[i - 1] = nums[i]
                edit_time_2 += 1
        
        if edit_time_1 <= 1 or edit_time_2 <= 1:
            return True
        else:
            return False

第2題 666. Path Sum IV

問題

輸入為一個 Depth < 5 的 tree，每個 node 可用三位數來表示。

  • 百位數D代表這個 node 所在的深度，1 <= D <= 4 。
  • 十位數P代表這個 node 在這個深度的第幾個位置, 1 <= P <= 8 。
  • 個位數V代表這個 node 的值, 0 <= V <= 9 。

找出所有從 root 到 leaf 的路徑和，也就是把路徑上的值相加。

輸入

[113, 215, 221]

輸出

12

方法

以下是範例輸入的解釋：

The tree that the list represents is:
    3
   / \
  5   1

The path sum is (3 + 5) + (3 + 1) = 12.

先將輸入的點分別對應 1 ~ 15 的值(也就是用陣列表示 tree, 但這裡直接用dictionary比較方便)，接著找出所有的 leaf ，再將每個 leaf 到 root 的路徑上所經過的點全部加起來即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def pathSum(self, nums):
        order = ['00', '11', '21', '22', '31', '32', '33', '34', '41', '42', '43', '44', '45', '46', '47', '48']
        tree = dict([(order.index(str(n)[:2]), n % 10) for n in nums])
        summation = 0
        leaves = [n for n in tree.keys() if not (2 * n in tree or 2 * n + 1 in tree)]
        for leaf in leaves:
            while leaf >= 1:
                summation += tree[leaf]
                leaf = int(leaf / 2)
        return summation

第3題 667. Beautiful Arrangement II

問題

輸入整數n與k，找到一個由 1 ~ n 組成的陣列[a1, a2, ..., an]，陣列元素不得重複，
使得 [|a1-a2|, |a2-a3|, ..., |an-1-an|] 剛好由 k 種不同的數組成。

輸入

n = 3, k = 1

輸出

[1, 2, 3]

方法

這題推導了很久，想到了一個方法，[1, 2, ..., n] 的差有 k 種值，1 <= k <= n - 1，只要建立一個規則產生所有的差，接著再想辦法湊出這個數列，舉例：

output: 5 1 4 3 2
diff:   4 3 1 1

假設要使得[1, 2, 3, 4, 5]鄰近的差只有三種，那就先將兩種差設為 n-1 與 n-2，也就是 4 跟 3，剩下的差都填 1 代表第三種差。至於要產生的陣列，先填入最大的數 5，接著根據每個差依序湊出陣列接下來的值，最後就會得到滿足條件的陣列了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def constructArray(self, n, k):
        diff = []
        for i in range(k - 1):
            diff.append(n - i - 1)
        for i in range(n - k):
            diff.append(1)
        nums = [n]
        for i in range(n - 1):
            new_value = abs(nums[i] + diff[i])
            if new_value > n or new_value in nums:
                new_value = abs(nums[i] - diff[i])
            nums.append(new_value)
        return nums

第4題 668. Kth Smallest Number in Multiplication Table

問題

找出在一個 m * n 的乘法表中，第 k 小的數字。

輸入

m = 3, n = 3, k = 5

輸出

3

方法

以 3 * 3 的乘法表舉例：

The Multiplication Table:
1   2   3
2   4   6
3   6   9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

這題我試了很多方法，不管怎麼樣總是不夠周延，最後看了別人的解法，使用 binary search ，實在太厲害了完全想不到。
看懂了之後寫了個 python 的版本，方法簡單來說就是利用二分搜尋法，找出中間值 mid ，接著計算每一列小於等於 mid 的個數的和，若總數小於 k ，代表值太小了還要再多一點；若總數大於 k ，代表值太大了要小一點，迴圈重複直到 low < high 的時候代表找到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findKthNumber(self, m, n, k):
        low, high = 1,  m * n + 1
        while low < high:
            mid = (low + high) // 2
            c = self.count_less_than_middle(mid, m, n)
            if c >= k:
                high = mid
            else:
                low = mid + 1
        return high

    def count_less_than_middle(self, middle, m, n):
        num = 0
        for i in range(1, m + 1):
            num  += min(middle // i, n)
        return num

結果

最後在時間內只有解出一題，排名只有 1157 / 2554，剩下的都是比賽結束後才想出來QQ，太慘烈了。看來在下做的題目還不夠多，看到題目沒辦法馬上有 sense 要用什麼方式解，只好先來閉關修煉一下了QQ 。