<
ARTS 第十二周
>
上一篇

ARTS 第十一周
下一篇

ARTS 第十三周
Toc
ARTS Week-12

Algorithm

1091. 二进制矩阵中的最短路径

在一个 N × N 的方形网格中,每个单元格有两种状态:空(0)或者阻塞(1)。
    
一条从左上角到右下角、长度为 k 的畅通路径,由满足下述条件的单元格 C_1, C_2, ..., C_k 组成:

相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通(此时,C_i 和 C_{i+1} 不同且共享边或角)
C_1 位于 (0, 0)(即,值为 grid[0][0])
C_k 位于 (N-1, N-1)(即,值为 grid[N-1][N-1])
如果 C_i 位于 (r, c),则 grid[r][c] 为空(即,grid[r][c] == 0)
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径,返回 -1 。


示例 1:

输入:[[0,1],[1,0]]

输出:2

示例 2:

输入:[[0,0,0],[1,1,0],[1,1,0]]

输出:4

提示:

1 <= grid.length == grid[0].length <= 100
grid[i][j] 为 0 或 1

这道题一开始我是用dp解的,但是超时了,然后使用 BFS 解法,当 BFS 搜索到终点位置时,就能求得步数:

img1

from collections import deque
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        
        if grid[0][0] == 1 or grid[-1][-1] == 1:
            return -1
        
        queue = deque([((0,0), 1)])
        visited = {(0, 0)}
        
        drs = [-1, 0, 1]
        dcs = [-1, 0, 1]
        
        while queue:
            cur, step = queue.popleft()
            r0, c0 = cur
            
            if r0 == n - 1 and c0 == n - 1:
                return step
            
            for dr in drs:
                for dc in dcs:
                    r, c = r0 + dr, c0 + dc
                    
                    if 0 <= r < n and 0 <= c < n and grid[r][c] == 0 and (r, c) not in visited:
                        visited.add((r, c))
                        queue.append(((r, c), step + 1))
        
        return -1

Review

《97 Things Every Programmer Should Know》- Choose Your Tools with Care

在使用开源项目时要谨慎选择,要从项目是否可维护、是否满足当前业务需求等出发,不可盲目使用开源项目。

Tip

jupyter lab - jupyter notebook 的升级版,兼容 notebook。

img2

Share

《迁移到云原生应用架构》中文版

本书是 Migrating to Cloud Native Application Architectures 的中文版。

云时代的云原生应用大势已来,将传统的单体架构应用迁移到云原生架构,你准备好了吗?

俗话说“意识决定行动”,在迁移到云原生应用之前,我们大家需要先对 Cloud Native(云原生)的概念、组织形式并对实现它的技术有一个大概的了解,这样才能指导我们的云原生架构实践。

Pivotal 是云原生应用的提出者,并推出了 Pivotal Cloud Foundry 云原生应用平台和 Spring 开源 Java 开发框架,成为云原生应用架构中先驱者和探路者。

原书作于2015年,其中的示例主要针对 Java 应用,实际上也适用于任何应用类型,云原生应用架构适用于异构语言的程序开发,不仅仅是针对 Java 语言的程序开发。截止到本人翻译本书时,云原生应用生态系统已经初具规模,CNCF 成员不断发展壮大,基于 Cloud Native 的创业公司不断涌现,kubernetes 引领容器编排潮流,和 Service Mesh 技术(如 Linkerd 和 Istio) 的出现,Go 语言的兴起(参考另一本书 Cloud Native Go)等为我们将应用迁移到云原生架构的提供了更多的方案选择。

Top
Foot