挑戰LeetCode Weekly Contest 50

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

解題心得

這次的題目有兩題都可以用遞迴來寫，但對我來說腦袋真的轉不過來啊！
果然如俗話所說：「遞迴只應天上有，凡人應當用迴圈」，描述的真是貼切，但遞迴之美，總是讓我們這些凡人流連忘返，遞迴啊遞迴，究竟何時才能讓願意人們真正看清您的真面目呢？

第1題 680. Valid Palindrome II

問題

給一個非空的字串s，在最多只能刪除一個字元的條件下，s是否能成為一個回文字串。
字串只包含小寫字母a-z，字串長度不超過50000。

輸入與輸出

Input: "aba"
Output: True

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

方法

使用two pointer的技巧，low與high分別從前面與後面開始走，若遇到不一樣的字元，則檢查在刪除其中任一個字元後是否能滿足回文的條件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def validPalindrome(self, s):
        low = 0
        high = len(s) - 1
        while low < high:
            if s[low] == s[high]:
                low += 1
                high -= 1
            else:
                if self.isPalindrome(s, low+1, high):
                    return True
                if self.isPalindrome(s, low, high-1):
                    return True
                return False
        return True

    def isPalindrome(self, s, low, high):
        while low < high:
            if s[low] != s[high]:
                return False
            low += 1
            high -= 1
        return True

第2題 677. Map Sum Pairs

問題

實作一個字典，能夠插入一對(key, value)，其中key為字串，value為整數。
輸入一個字串prefix，輸出字典中所有以prefix為開頭的所有key所對應的value的和。

輸入與輸出

Input: "aba"
Output: True

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

方法

直接使用python的內建dict。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MapSum:

    def __init__(self):
        self.d = dict()
        

    def insert(self, key, val):
        self.d[key] = val
        

    def sum(self, prefix):
        summation = 0
        length = len(prefix)
        for k, v in self.d.items():
            if k[:length] == prefix:
                summation += v
        return summation

第3題 678. Valid Parenthesis String

問題

輸入一個字串，字串內的元素只包含(,),*三種，判斷此字串是否滿足以下條件： 1. 任何一個左方的(都必須對應到一個右方的) 2. 任何一個右方的)都必須對應到一個左方的( 3. 左方的(必須出現在右方的)之前 4. *可以是(或)或空字串其中一種 5. 空字串是合法的

輸入與輸出

Input: "()"
Output: True

Input: "(*)"
Output: True

Input: "(*))"
Output: True

方法

使用一個變數p紀錄括號的消長，出現一組(,)便可抵消。
至於出現*的話，因為有三種可能，因此用backtracking分支成三種可能，只要其中一種能夠滿足條件就代表合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def checkValidString(self, s):
        return self.backtracking(list(s), 0, 0)
    
    def backtracking(self, c, p, index):
        if p < 0:
            return False
        for i in range(index, len(c)):
            x = c[i]
            if x == '(':
                p += 1
            elif x == ')':
                if p <= 0:
                    return False
                p -= 1
            else:
                return self.backtracking(c, p + 1, i + 1) or self.backtracking(c, p - 1, i + 1) or self.backtracking(c, p, i + 1)
        return p == 0

以上是使用python的解法，可惜跳出 TLE，因此將同樣的方法改寫成C++的版本，就可以通過了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool checkValidString(string s) {
        return backtracking(s, 0, 0);
    }

    bool backtracking(string c, int p, int index) {
        if (p < 0)
            return false;
        for (int i = index; i < c.length(); i++) {
            char x = c[i];
            if (x == '(')
                p++;
            else if (x == ')') {
                if (p <= 0)
                    return false;
                p--;
            }
            else
                return backtracking(c, p+1, i+1) || backtracking(c, p-1, i+1) || backtracking(c, p, i+1);
        }
        return p == 0;
    }
};

第4題 679. 24 Game

問題

給四個範圍1~9的整數，問是否能經過+,-,*,/,(,)的運算後的得到結果為24。

輸入與輸出

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Input: [1, 2, 1, 2]
Output: False

方法

總共有 4 個數字以及 4 個運算子，括號的部份代表運算的先後順序，因此計算的步驟如下：

  1. 從 4 個數字中取 2 個(順序有分)，再從 4 個運算子當中選 1 個，所以有 4 x 5 x 3 種選法
  2. 第 1 步驟運算完後數字剩下 3 個，再從 3 個數字中取 2 個(順序有分)，同樣從 4 個運算子當中選 1 個，所以有 3 x 2 x 4 種選法
  3. 第 2 步驟運算完後數字剩下 2 個，再從 2 個數字當中取 2 個(順序有分)，從 4 個運算子中選一個，所以有 2 x 4 種選法

因此總共有 4 x 3 x 3 x 3 x 2 x 4 x 2 x 4 = 9216 種組合方法

所以用遞迴枚舉出所有的方法就可以將所有答案計算出來。要注意的是除數不能為 0 ，還有由於浮點數運算的誤差，因此計算結果未必剛好等於 24 ，可能會有非常微小的誤差值，所以要給一個容忍值才行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def judgePoint24(self, A):
        if len(A) == 1:
            if abs(A[0] - 24) < 1e-6:
                return True
        for i in range(len(A)):
            for j in range(len(A)):
                if i != j:
                    B = [A[x] for x in range(len(A)) if x != i and x != j]
                    if self.judgePoint24([A[i] + A[j]] + B) or self.judgePoint24([A[i] - A[j]] + B) or self.judgePoint24([A[i] * A[j]] + B):
                        return True
                    if A[j] and self.judgePoint24([A[i] / A[j]] + B):
                            return True
        return False