Merge pull request algorithm004-01#411 from Ryanyanglibin/master

melody-li · web-flow · commit 3265fbd41207 · 2019-10-28T11:58:34.000+08:00
091-week 02
diff --git a/Week 02/id_091/LeetCode_17_091.py b/Week 02/id_091/LeetCode_17_091.py
@@ -0,0 +1,43 @@
+from typing import List
+
+
+class Solution:
+    def letterCombinations(self, digits):
+        if not digits:
+            return []
+        dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
+        res = []
+        self.dfs(digits, dic, 0, "", res)
+        return res
+
+    def dfs(self, digits, dic, index, path, res):
+        if len(path) == len(digits):
+            res.append(path)
+            return
+        for i in range(index, len(digits)):
+            for j in dic[digits[i]]:
+                self.dfs(digits, dic, i + 1, path + j, res)
+
+    def letterCombinations2(self, digits: str) -> List[str]:
+        m = {
+            '2': list('abc'),
+            '3': list('def'),
+            '4': list('ghi'),
+            '5': list('jkl'),
+            '6': list('mno'),
+            '7': list('pqrs'),
+            '8': list('tuv'),
+            '9': list('wxyz'),
+        }
+        if not digits: return []
+        ls1 = ['']
+        for i in digits:
+            ls1 = [x + y for x in ls1 for y in m[i]]
+        return ls1
+
+
+if __name__ == '__main__':
+    n = "23"
+    solution = Solution()
+    res = solution.letterCombinations(n)
+    print(res)
diff --git a/Week 02/id_091/LeetCode_242_091.py b/Week 02/id_091/LeetCode_242_091.py
@@ -0,0 +1,29 @@
+class Solution:
+    def isAnagram(self, s: str, t: str) -> bool:
+        dic1, dic2 = {}, {}
+        for item in s:
+            dic1[item] = dic1.get(item, 0) + 1
+        for item in t:
+            dic2[item] = dic2.get(item, 0) + 1
+        return dic1 == dic2
+
+
+def isAnagram2(self, s, t):
+    dic1, dic2 = [0] * 26, [0] * 26
+    for item in s:
+        dic1[ord(item) - ord('a')] += 1
+    for item in t:
+        dic2[ord(item) - ord('a')] += 1
+    return dic1 == dic2
+
+
+def isAnagram3(self, s, t):
+    return sorted(s) == sorted(t)
+
+
+if __name__ == '__main__':
+    s = "anagram"
+    t = "nagaram"
+    solution = Solution()
+    res = solution.isAnagram(s, t)
+    print(res)
diff --git a/Week 02/id_091/LeetCode_51_091.py b/Week 02/id_091/LeetCode_51_091.py
@@ -0,0 +1,62 @@
+from typing import List
+
+
+class Solution:
+
+    def solveNQueens(self, n: int) -> List[List[str]]:
+        def DFS(queens, xy_dif, xy_sum):
+            p = len(queens)
+            if p == n:
+                result.append(queens)
+                return None
+            for q in range(n):
+                if q not in queens and p - q not in xy_dif and p + q not in xy_sum:
+                    DFS(queens + [q], xy_dif + [p - q], xy_sum + [p + q])
+
+        result = []
+        DFS([], [], [])
+        return [["." * i + "Q" + "." * (n - i - 1) for i in sol] for sol in result]
+
+    def solveNQueens2(self, n: int) -> List[List[str]]:
+        res = []
+        if n == 0:
+            return res
+
+        nums = [i for i in range(n)]
+        col = set()
+        master = set()
+        slave = set()
+        stack = []
+
+        self.__backtracking(nums, 0, n, col, master, slave, stack, res)
+        return res
+
+    def __backtracking(self, nums, row, n, col, master, slave, stack, res):
+        if row == n:
+            board = self.__convert2board(stack, n)
+            res.append(board)
+            return
+
+        for i in range(n):
+            if i not in col and row + i not in master and row - i not in slave:
+                stack.append(nums[i])
+                col.add(i)
+                master.add(row + i)
+                slave.add(row - i)
+
+                self.__backtracking(nums, row + 1, n, col, master, slave, stack, res)
+
+                slave.remove(row - i)
+                master.remove(row + i)
+                col.remove(i)
+                stack.pop()
+
+    def __convert2board(self, stack, n):
+        return ["." * stack[i] + "Q" + "." * (n - stack[i] - 1) for i in range(n)]
+
+
+if __name__ == '__main__':
+    n = 5
+    solution = Solution()
+    res = solution.solveNQueens(n)
+    print(res)
diff --git a/Week 02/id_091/LeetCode_94_091.py b/Week 02/id_091/LeetCode_94_091.py
@@ -0,0 +1,54 @@
+class Node():
+
+    def __init__(self, data=None, left=None, right=None):
+        self._data = data
+        self._left = left
+        self._right = right
+
+
+def proOrder(tree):
+    if tree == None:
+        return False
+    print(tree._data)
+    proOrder(tree._left)
+    proOrder(tree._right)
+
+
+def posOrder(tree):
+    if tree == None:
+        return False
+    posOrder(tree._left)
+    posOrder(tree._right)
+    posOrder(tree._data)
+
+
+def inOrder(tree):
+    if tree == None:
+        return False
+    inOrder(tree._left)
+    print(tree._data)
+    inOrder(tree._right)
+
+
+# 层次遍历
+def rowOrder(tree):
+    queue = []
+    queue.append(tree)
+    while True:
+        if queue == []:
+            break
+        print(queue[0]._data)
+        first_tree = queue[0]
+        if first_tree._left != None:
+            queue.append(first_tree._left)
+        if first_tree._right != None:
+            queue.append(first_tree._right)
+        queue.remove(first_tree)
+
+
+if __name__ == '__main__':
+    tree = Node('A', Node('B', Node('D'), Node('E')), Node('C', Node('F'), Node('G')))
+    proOrder(tree)
+# inOrder(tree)
+# posOrder(tree)
+# rowOrder(tree)
