作业

YujueY · YujueY · commit 40f853781d22 · 2020-07-26T16:21:50.000+08:00
diff --git a/Week07/200.py b/Week07/200.py
@@ -0,0 +1,21 @@
+class Solution:
+    def dfs(self, grid, r, c):
+        grid[r][c] = "0"
+        nr = len(grid)
+        nl = len(grid[0])
+        for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
+            if 0 <= x < nr and 0 <= y < nl and grid[x][y] == "1":
+                self.dfs(grid, x, y)
+
+    def numIslands(self, grid: List[List[str]]) -> int:
+        nr = len(grid)
+        if nr == 0:
+            return 0
+        nl = len(grid[0])
+        num_island = 0
+        for r in range(nr):
+            for l in range(nl):
+                if grid[r][l] == "1":
+                    num_island += 1
+                    self.dfs(grid, r, l)
+        return num_island
diff --git a/Week07/433.py b/Week07/433.py
@@ -0,0 +1,25 @@
+class Solution:
+    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
+        bank = set(bank)
+        if end not in bank:
+            return -1
+        change_map = {
+            "A": "CGT",
+            "C": "AGT",
+            "G": "ACT",
+            "T": "ACG"
+        }
+        queue = [(start, 0)]
+        while queue:
+            node, step = queue.pop(0)
+
+            if node == end:
+                return step
+
+            for i, s in enumerate(node):
+                for c in change_map[s]:
+                    new = node[:i] + c + node[i + 1:]
+                    if new in bank:
+                        queue.append((new, step + 1))
+                        bank.remove(new)
+        return -1
