algorithm004-04 · strongChicken · Nov 4, 2019 · Nov 5, 2019 · Nov 6, 2019 · Nov 11, 2019
diff --git a/Week 02/id_594/.DS_Store b/Week 02/id_594/.DS_Store
diff --git a/Week 02/id_594/LeetCode_098_594.py b/Week 02/id_594/LeetCode_098_594.py
@@ -0,0 +1,23 @@
+class TreeNode:
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+
+def isValidBST(self, root: TreeNode):
+    return self.recursive(root, -float('-inf'), float('inf'))           # 唯一不懂的是，float里面为啥是字符串呢
+
+
+def recursive(self, root, left_bound, right_bound):
+    if root.val <= left_bound or root.val >= right_bound:
+        return False
+    if not root:
+        return True
+    left = self.recursive(root.left, left_bound, root.val)
+    right = self.recursive(root.right, root.val, right_bound)
+    return left and right
+
+# 左子树的节点val必须小于根节点
+# 右子树的节点val必须大于根节点
+# 所有left_bound和right_bound就作为了左右边界，如果左子树节点大于了root.val=5，就越界，返回false
diff --git a/Week 02/id_594/LeetCode_104_594.py b/Week 02/id_594/LeetCode_104_594.py
@@ -0,0 +1,17 @@
+class TreeNode:
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+
+def maxDepth(self, root: TreeNode):     # 递归
+    def recursive(self, root):
+        if root is None:
+            return 0
+        else:
+            left_depth = self.recursive(root.left)
+            right_depth = self.recursive(root.right)
+        return max(left_depth, right_depth) + 1
+
+
diff --git a/Week 02/id_594/LeetCode_111_594.py b/Week 02/id_594/LeetCode_111_594.py
@@ -0,0 +1,13 @@
+class TreeNode:
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+
+def minDepth(self, root: TreeNode):
+    def recursive(root):
+        if root is None:
+            return 0
+
+        return min()
diff --git a/Week 02/id_594/LeetCode_226_594.py b/Week 02/id_594/LeetCode_226_594.py
@@ -0,0 +1,12 @@
+class TreeNode:
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+
+def invertTree(self, root: TreeNode):
+    if root:
+        invert = self.invertTree
+        root.left, root.right = invert(root.right), invert(root.left)
+    return root
diff --git a/Week 02/id_594/LeetCode_22_594.py b/Week 02/id_594/LeetCode_22_594.py
@@ -0,0 +1,55 @@
+def generateParenthesis1(n: int):
+    res = []
+    recursive("", 0, 0, n, res)
+    return res
+
+
+def recursive(s, left, right, n, res):
+    if (left == n) and (right == n):
+        res.append(s)
+        return res
+
+    if left > right:
+        recursive(s+")", left, right+1, n, res)
+
+    if left < n:
+        recursive(s+"(", left+1, right, n, res)
+
+
+def generateParenthesis2(n: int):
+    def recursive(s, left, right, res=[]):          # 精妙的组员啊，直接在里面设置了res=[]了，在最后的return返回了
+        if left:
+            recursive(s+"(", left-1, right)
+        if left < right:
+            recursive(s+")", left, right-1)
+        if not right:
+            res += s
+        return res
+    return recursive("", n, n)
+
+
+def generateParenthesis3(n: int):           # 好像是把递归的形式用迭代写了出来？
+    if n == 0:
+        return None
+    res = []
+    res.append([None])
+    res.append(["()"])
+    for i in range(2, n+1):
+        stack = []
+        for j in range(i):
+            temp_1 = res[j]
+            temp_2 = res[i-1-j]
+            for k1 in temp_1:
+                for k2 in temp_2:
+                    if k1 == None:
+                        k1 = ""
+                    if k2 == None:
+                        k2 = ""
+                    cur = "(" + k1 + ")" + k2
+                    stack.append(cur)
+        res.append(stack)
+    return res[n]
+
+
+ex = 3
+print(generateParenthesis3(ex))
diff --git a/Week 02/id_594/LeetCode_590_594.py b/Week 02/id_594/LeetCode_590_594.py
@@ -5,14 +5,15 @@ def __init__(self, x, chlidren):
 
 
 def postorder(root: 'Node'):        # 这个解题方式，还不理解是什么意思
-    res = []
-
     if root == None:
-        return res
-
+        return []
+    res = []
     stack = [root]
     while stack:
         root = stack.pop()
-        if not root:
+        if root is not None:
+            res.append(root.val)
+        for i in root.children:
+            stack.append(i)
 
     return res[:: -1]
diff --git a/Week 02/id_594/LeetCode_70_594.py b/Week 02/id_594/LeetCode_70_594.py
@@ -0,0 +1,16 @@
+def climbStairs(n) -> int:          # 这个递归真的太棒了吧
+    res = [n] * -1
+    res[0], res[1] = 1, 2
+    return recursive(n , res)
+
+
+def recursive(n, res):
+    if res[n] == -1:
+        res[n] = res[n-1, res] + res[n-2, res]
+    return res[n]
+
+
+
+ex = 5
+print(climbStairs(ex))
+
diff --git a/Week 03/id_594/LeetCode_127_594.py b/Week 03/id_594/LeetCode_127_594.py
@@ -0,0 +1,40 @@
+from collections import defaultdict
+
+
+def ladderLength(beginWord, endWord, wordList:list):
+    L = len(beginWord)
+    all_word = defaultdict(list)
+    for word in wordList:
+        for i in range(L):
+            # all_word 储存wordlist中单词的不同映射
+            all_word[word[:i] + "*" + word[i+1:]].append(word)
+
+    queue = [(beginWord, 1)]
+    # 当visited的单词，状态转化为True
+    visited = {beginWord: True}
+    while queue:
+        # 先进先出的队列规则
+        cur_word, level = queue.pop(0)
+        for i in range(L):
+            # 从队列获得的word不同条件下的映射
+            temp_word = cur_word[:i] + "*" + cur_word[i+1:]     # 这里元祖拼接会在本地报错，但LC上却没有。。。
+            # 从all_word 字典中匹配 对应的word，也就是说明有符合条件的映射→重点，不过比较好奇的是，这里找不到的
+            for word in all_word[temp_word]:
+                # 判断获得的 word 是否等于 endword，其实就是是否得到最短距离
+                if word == endWord:
+                    return level+1
+                # 这个是判断新词，新词就加到visited，并且增加层级
+                if word not in visited:
+                    visited[word] = True
+                    # 符合条件的word和level加入到队列里面
+                    queue.append((word, level+1))
+            # 如果没有匹配的话，则用空list作为key
+            all_word[temp_word] = []
+    return 0
+
+
+begin = "hit"
+end = "cog"
+words = ["hot", "dot", "dog", "lot", "log", "cog"]
+
+print(ladderLength(begin, end, words))
diff --git a/Week 03/id_594/LeetCode_200_594.py b/Week 03/id_594/LeetCode_200_594.py
@@ -0,0 +1,40 @@
+# DFS
+def DFS_numIslands(grid: list[list[str]]):
+    # 递归找 '0'(海)的坐标
+    def helper(grid, i, j):
+        # 为什么是在[0: len(grid))区间之外，为什么return
+        if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0':
+            return
+        grid[i][j] = '0'
+        helper(grid, i+1, j)
+        helper(grid, i-1, j)
+        helper(grid, i, j+1)
+        helper(grid, i, j-1)
+    count = 0
+    # 遍历二位数组，如果坐标是'1'，则横纵坐标是否被0包围，成功返回，则count+=1
+    for i in range(len(grid)):
+        for j in range(len(grid[0])):
+            if grid[i][j] == '1':
+                helper(grid, i, j)
+                count += 1
+    return count
+
+
+# BFS
+def BFS_numIslands(grid: list[list[str]]):
+    def helper(grid, i, j):
+        deque = [[i, j]]
+        while deque:
+            [i, j] = deque.pop(0)
+            if not 0 <= i < len(grid) or 0 <= j < len(grid[0]) or grid[i][j] == '1':
+                grid[i][j] = '0'
+                deque += [[i+1, j], [i, j+1], [i-1, j], [i, j-1]]
+    count = 0
+    for i in range(grid):
+        for j in range(grid[0]):
+            if grid[i][j] == '0':
+                continue
+                helper(grid, i, j)
+                count += 1
+    return count
+