Add files via upload

linwt · web-flow · commit fe0ff9f0640a · 2019-10-27T11:04:54.000+08:00
diff --git a/leetcode2/1007.行相等的最少多米诺旋转.py b/leetcode2/1007.行相等的最少多米诺旋转.py
@@ -0,0 +1,21 @@
+# 如果最终能整排值相同，那么两排各自的第一个多米诺骨牌至少有一个是目标值
+# 取两排第一个值分别进行判断，检查其他多米诺骨牌是否出现该值，若都出现则求出最小翻转次数
+class Solution(object):
+    def minDominoRotations(self, A, B):
+        def check(x, n):
+            a, b = 0, 0
+            for i in range(n):
+                if A[i] != x and B[i] != x:
+                    return -1
+                elif A[i] != x:
+                    a += 1
+                elif B[i] != x:
+                    b += 1
+            return min(a, b)
+
+        n = len(A)
+        res = check(A[0], n)
+        if res != -1:
+            return res
+        else:
+            return check(B[0], n)
diff --git a/leetcode2/1091.二进制矩阵中的最短路径.py b/leetcode2/1091.二进制矩阵中的最短路径.py
@@ -0,0 +1,23 @@
+class Solution(object):
+    def shortestPathBinaryMatrix(self, grid):
+        # 左上角和右下角不是0
+        if grid[0][0] or grid[-1][-1]:
+            return -1
+        n, queue, d = len(grid), [(0, 0, 2)], [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
+        if n <= 2:
+            return n
+        # 从起点开始，广度优先搜索
+        for x, y, res in queue:
+            # 搜索八个方向
+            for dx, dy in d:
+                nx, ny = x+dx, y+dy
+                if 0 <= nx < n and 0 <= ny < n and not grid[nx][ny]:
+                    # 有一条路径已经到达终点，返回路径长度
+                    if nx == n-1 and ny == n-1:
+                        return res
+                    # 未到达终点，添加中间位置到队列
+                    queue += [(nx, ny, res+1)]
+                    # 搜索过的位置置1，防止重复搜索
+                    grid[nx][ny] = 1
+        # 没有路径到达终点
+        return -1
diff --git a/leetcode2/1162.地图分析.py b/leetcode2/1162.地图分析.py
@@ -0,0 +1,25 @@
+# 广度优先搜索，从1开始，向四周搜索0，并记录每个0的搜索步数，返回最大的搜索步数
+class Solution(object):
+    def maxDistance(self, grid):
+        m, n = len(grid), len(grid[0])
+        if sum([sum(grid[i]) for i in range(m)]) in [0, m * n]:
+            return -1
+
+        q, res = [], [[-1] * n for _ in range(m)]
+        d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
+
+        for i in range(m):
+            for j in range(n):
+                if grid[i][j] == 1:
+                    res[i][j] = 0
+                    q.append((i, j))
+
+        while q:
+            x, y = q.pop(0)
+            for dx, dy in d:
+                nx, ny = x + dx, y + dy
+                if 0 <= nx < m and 0 <= ny < n and res[nx][ny] == -1:
+                    res[nx][ny] = res[x][y] + 1
+                    q.append((nx, ny))
+
+        return max([max(res[i]) for i in range(m)])
