algorithm004-01 · KvinLiu · Dec 13, 2019 · Dec 15, 2019 · Dec 16, 2019 · Dec 17, 2019
diff --git a/Week 02/id_661/LeetCode_144_661.py b/Week 02/id_661/LeetCode_144_661.py
@@ -0,0 +1,22 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def preorderTraversal(self, root):
+        res = []
+        self.iterative(root, [root], res)
+        return res
+
+    def iterative(self, root, stack, res):
+        while stack:
+            node = stack.pop()
+            if node:
+                res.append(node.val)
+                stack.append(node.right)
+                stack.append(node.left)
+
+    def recursive(self, root, res):
+        if root:
+            res.append(root.val)
+            self.recursive(root.left)
+            self.recursive(root.right)
diff --git a/Week 02/id_661/LeetCode_1_661.py b/Week 02/id_661/LeetCode_1_661.py
@@ -0,0 +1,16 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def twoSum(self, nums, target):
+        dct = {}
+        for k, v in enumerate(nums):
+            if target - v in dct:
+                return [dct[target - v], k]
+            dct[v] = k
+        return []
+
+
+testCase = [2, 7, 11, 15]
+
+print(Solution().twoSum(testCase, 17))
diff --git a/Week 02/id_661/LeetCode_242_661.py b/Week 02/id_661/LeetCode_242_661.py
@@ -0,0 +1,14 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def isAnagram(self, s, t):
+        d1, d2 = {}, {}
+        for c in s:
+            d1[c] = d1.get(c, 0) + 1
+        for c in t:
+            d2[c] = d2.get(c, 0) + 1
+        return d1 == d2
+
+
+print(Solution().isAnagram("anagram", "naagrma"))
diff --git a/Week 02/id_661/LeetCode_49_661.py b/Week 02/id_661/LeetCode_49_661.py
@@ -0,0 +1,18 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def groupAnagrams(self, strs):
+        dct = {}
+        for s in strs:
+            key = "".join(sorted(s))
+            if key in dct:
+                dct[key].append(s)
+            else:
+                dct[key] = [s]
+        return [dct[x] for x in dct]
+
+
+test = ["eat", "tea", "tan", "ate", "nat", "bat"]
+
+print(Solution().groupAnagrams(test))
diff --git a/Week 02/id_661/LeetCode_589_661.py b/Week 02/id_661/LeetCode_589_661.py
@@ -0,0 +1,12 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def preorder(self, root):
+        stack = bool(root) * [root]
+        res = []
+        while stack:
+            root = stack.pop()
+            res.append(root.val)
+            stack += root.children[::-1]
+        return res
diff --git a/Week 02/id_661/LeetCode_590_661.py b/Week 02/id_661/LeetCode_590_661.py
@@ -0,0 +1,16 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def postorder(self, root):
+        res = []
+        if not root:
+            return res
+
+        def _postorder(root, res):
+            for c in root.children:
+                _postorder(c, res)
+            res.append(root.val)
+
+        _postorder(root, res)
+        return res
diff --git a/Week 02/id_661/LeetCode_94_661.py b/Week 02/id_661/LeetCode_94_661.py
@@ -0,0 +1,15 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def inorderTraversal(self, root):
+        res = []
+
+        def _inorder(root):
+            if root:
+                _inorder(root.left)
+                res.append(root.val)
+                _inorder(root.right)
+            return res
+
+        return _inorder(root)
diff --git a/Week 05/id_661/LeetCode_221_661.py b/Week 05/id_661/LeetCode_221_661.py
@@ -0,0 +1,21 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def maximalSquare(self, matrix):
+        if not matrix:
+            return 0
+        m, n = len(matrix), len(matrix[0])
+        dp = [
+            [0 if matrix[i][j] == "0" else 1 for j in range(0, n)] for i in range(0, m)
+        ]
+
+        for i in range(1, m):
+            for j in range(1, n):
+                if matrix[i][j] == "1":
+                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
+                else:
+                    dp[i][j] = 0
+
+        res = max(max(row) for row in dp)
+        return res ** 2
diff --git a/Week 05/id_661/LeetCode_32_661.py b/Week 05/id_661/LeetCode_32_661.py
@@ -0,0 +1,18 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def longestValidParentheses(self, s):
+        dp, stack = [0] * (len(s) + 1), []
+        for i in range(len(s)):
+            if s[i] == "(":
+                stack.append(i)
+            else:
+                if stack:
+                    p = stack.pop()
+                    dp[i + 1] = dp[p] + i - p + 1
+        return max(dp)
+
+
+test = "(()"
+print(Solution().longestValidParentheses(test))
diff --git a/Week 05/id_661/LeetCode_64_661.py b/Week 05/id_661/LeetCode_64_661.py
@@ -0,0 +1,18 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def minPathSum(self, grid):
+        m, n = len(grid), len(grid[0])
+        for i in range(1, n):
+            grid[0][i] += grid[0][i - 1]
+        for i in range(1, m):
+            grid[i][0] += grid[i - 1][0]
+        for i in range(1, m):
+            for j in range(1, n):
+                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
+        return grid[-1][-1]
+
+
+test = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
+print(Solution().minPathSum(test))
diff --git a/Week 05/id_661/LeetCode_72_661.py b/Week 05/id_661/LeetCode_72_661.py
@@ -0,0 +1,17 @@
+#!/usr/bin/env python3.7
+class Solution:
+    def minDistance(self, word1: str, word2: str) -> int:
+        l1, l2 = len(word1) + 1, len(word2) + 1
+        pre = [0 for _ in range(l2)]
+        for j in range(l2):
+            pre[j] = j
+        for i in range(1, l1):
+            cur = [i] * l2
+            for j in range(1, l2):
+                cur[j] = min(
+                    cur[j - 1] + 1,
+                    pre[j] + 1,
+                    pre[j - 1] + (word1[i - 1] != word2[j - 1]),
+                )
+            pre = cur[:]
+        return pre[-1]
diff --git a/Week 05/id_661/LeetCode_91_661.py b/Week 05/id_661/LeetCode_91_661.py
@@ -0,0 +1,13 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def numDecodings(self, s):
+        v, w, p = 0, int(s > ""), ""
+        for d in s:
+            v, w, p = w, (d > "0") * w + (9 < int(p + d) < 27) * v, d
+        return w
+
+
+test = "12"
+print(Solution().numDecodings(test))
diff --git a/Week 06/id_661/LeetCode_130_661.py b/Week 06/id_661/LeetCode_130_661.py
@@ -0,0 +1,22 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def solve(self, board: List[List[str]]) -> None:
+        """
+        Do not return anything, modify board in-place instead.
+        """
+        if not any(board):
+            return
+
+        m, n = len(board), len(board[0])
+        save = [
+            ij for k in range(m + n) for ij in ((0, k), (m - 1, k), (k, 0), (k, n - 1))
+        ]
+        while save:
+            i, j = save.pop()
+            if 0 <= i < m and 0 <= j < n and board[i][j] == "O":
+                board[i][j] = "S"
+                save += (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)
+
+        board[:] = [["XO"[c == "S"] for c in row] for row in board]
diff --git a/Week 06/id_661/LeetCode_208_661.py b/Week 06/id_661/LeetCode_208_661.py
@@ -0,0 +1,41 @@
+#!/usr/bin/env python3.7
+
+
+class Trie:
+    def __init__(self):
+        """
+        Initialize your data structure here.
+        """
+        self.root = {}
+        self.end_of_word = "#"
+
+    def insert(self, word: str) -> None:
+        """
+        Inserts a word into the trie.
+        """
+        node = self.root
+        for char in word:
+            node = node.setdefault(char, {})
+        node[self.end_of_word] = self.end_of_word
+
+    def search(self, word: str) -> bool:
+        """
+        Returns if the word is in the trie.
+        """
+        node = self.root
+        for char in word:
+            if char not in node:
+                return False
+            node = node[char]
+        return self.end_of_word in node
+
+    def startsWith(self, prefix: str) -> bool:
+        """
+        Returns if there is any word in the trie that starts with the given prefix.
+        """
+        node = self.root
+        for char in prefix:
+            if char not in node:
+                return False
+            node = node[char]
+        return True
diff --git a/Week 06/id_661/LeetCode_212_661.py b/Week 06/id_661/LeetCode_212_661.py
@@ -0,0 +1,31 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
+        root = {}
+        for word in words:
+            node = root
+            for c in word:
+                node = node.setdefault(c, {})
+            node[None] = True
+        board = {
+            i + 1j * j: c for i, row in enumerate(board) for j, c in enumerate(row)
+        }
+
+        found = []
+
+        def search(node, z, word):
+            if node.pop(None, None):
+                found.append(word)
+            c = board.get(z)
+            if c in node:
+                board[z] = None
+                for k in range(4):
+                    search(node[c], z + 1j ** k, word + c)
+                board[z] = c
+
+        for z in board:
+            search(root, z, "")
+
+        return found
diff --git a/Week 06/id_661/LeetCode_32_661.py b/Week 06/id_661/LeetCode_32_661.py
@@ -0,0 +1,41 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def solveSudoku(self, board: List[List[str]]) -> None:
+        """
+        Do not return anything, modify board in-place instead.
+        """
+        row = [set(range(1, 10)) for _ in range(9)]  # 行剩余可用数字
+        col = [set(range(1, 10)) for _ in range(9)]  # 列剩余可用数字
+        block = [set(range(1, 10)) for _ in range(9)]  # 块剩余可用数字
+
+        empty = []  # 收集需填数位置
+        for i in range(9):
+            for j in range(9):
+                if board[i][j] != ".":  # 更新可用数字
+                    val = int(board[i][j])
+                    row[i].remove(val)
+                    col[j].remove(val)
+                    block[(i // 3) * 3 + j // 3].remove(val)
+                else:
+                    empty.append((i, j))
+
+        def backtrack(iter=0):
+            if iter == len(empty):  # 处理完empty代表找到了答案
+                return True
+            i, j = empty[iter]
+            b = (i // 3) * 3 + j // 3
+            for val in row[i] & col[j] & block[b]:
+                row[i].remove(val)
+                col[j].remove(val)
+                block[b].remove(val)
+                board[i][j] = str(val)
+                if backtrack(iter + 1):
+                    return True
+                row[i].add(val)  # 回溯
+                col[j].add(val)
+                block[b].add(val)
+            return False
+
+        backtrack()
diff --git a/Week 06/id_661/LeetCode_36_661.py b/Week 06/id_661/LeetCode_36_661.py
@@ -0,0 +1,18 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def isValidSudoku(self, board: List[List[str]]) -> bool:
+        row = [[x for x in y if x != "."] for y in board]
+        col = [[x for x in y if x != "."] for y in zip(*board)]
+        pal = [
+            [
+                board[i + m][j + n]
+                for m in range(3)
+                for n in range(3)
+                if board[i + m][j + n] != "."
+            ]
+            for i in (0, 3, 6)
+            for j in (0, 3, 6)
+        ]
+        return all(len(set(x)) == len(x) for x in (*row, *col, *pal))
diff --git a/Week 06/id_661/LeetCode_547_661.py b/Week 06/id_661/LeetCode_547_661.py
@@ -0,0 +1,20 @@
+#!/usr/bin/env python3.7
+
+
+class Solution:
+    def findCircleNum(self, M: List[List[int]]) -> int:
+        n = len(M)
+        seen = set()
+
+        def dfs(node):
+            for nei, adj in enumerate(M[node]):
+                if adj and nei not in seen:
+                    seen.add(nei)
+                    dfs(nei)
+
+        ans = 0
+        for i in range(n):
+            if i not in seen:
+                dfs(i)
+                ans += 1
+        return ans