Algorithm

63. 不同路径II

一个机器人位于一个 m ＊ n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

解决方案：

我的解法：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
         int[][] pathCount = new int[obstacleGrid.length][obstacleGrid[0].length];
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1){
            pathCount[0][0] = 0;
        }else{
            pathCount[0][0] = 1;
        }

        for (int i = 1; i < m; i++){
            if (obstacleGrid[i][0] == 1){
                pathCount[i][0] = 0;
            }else {
                pathCount[i][0] = pathCount[i - 1][0];
            }
        }

        for (int j = 1; j < n; j++){
            if (obstacleGrid[0][j] == 1){
                pathCount[0][j] = 0;
            }else {
                pathCount[0][j] = pathCount[0][j - 1];
            }
        }


        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                int left = pathCount[i - 1][j];
                if (obstacleGrid[i - 1][j] == 1){
                    left = 0;
                }

                int up = pathCount[i][j - 1];
                if (obstacleGrid[i][j - 1] == 1){
                    up = 0;
                }
                if (obstacleGrid[i][j] == 1){
                    pathCount[i][j] = 0;
                }else{
                    pathCount[i][j] = left + up;
                }
            }
        }

        return pathCount[m - 1][n - 1];
    }
}

更高效解法：

class Solution {
	
	private int row,column;						//方格的行数和列数
	private int[][] numPath;

   public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
		if(obstacleGrid.length==0)
			return 0;
		
		row=obstacleGrid.length;
		column=obstacleGrid[0].length;
		
		if(column==0||obstacleGrid[row-1][column-1]==1||obstacleGrid[0][0]==1)
			return 0;
		
		numPath=new int[row][column];
		
		for(int i=0;i<row;i++){
			for(int j=0;j<column;j++)
				numPath[i][j]=-1;
		}
		return getPathNum(0,0,obstacleGrid);
    }
	
	//(x,y)到右下角的路径条数
	public int getPathNum(int x,int y,int[][] obstacleGrid){
		
		if(x==row-1&&y==column-1)
			return 1;
		
		if(numPath[x][y]!=-1)
			return numPath[x][y];
		
		int num=0;
		if(x+1<row&&obstacleGrid[x+1][y]==0)
			num+=getPathNum(x+1,y,obstacleGrid);
		if(y+1<column&&obstacleGrid[x][y+1]==0)
			num+=getPathNum(x,y+1,obstacleGrid);
		numPath[x][y]=num;
		
		return num;
	}
}

Review

MAKING OLD APPLICATIONS NEW AGAIN

目标

应用程序现代化有两个主要目标：

1. 尽可能多地使用新应用程序中的现有功能和数据（从旧应用程序中获取新值）。
2. 将新流程，产品和技术的优势带给旧应用程序。

三种现代化软件开发模式

有三种软件开发模式为应用程序现代化提供了统一的方法。 两个扩展了现有应用程序的生命周期和实用性，避免了对整个产品组合的一次性更改，为第三种模式设置了阶段，其中包括逐步的应用程序重构和体系结构更新。 在任何情况下都不要为了从现代化中受益而一次性重写应用程序。 即使是单片应用程序也可以在未被重写的情况下从现代化中受益。

三种模式分别是：平移、增加新层及重写，其成本是逐步递增的。

平移（LIFT AND SHIFT）

平移现代化应用程序的打包和部署方式。 通过平移将现有组件部署在现代化部署平台上。 平移并不改变应用程序的体系结构，相反，它使企业能够运行在现代化部署平台上，以便有足够的缓冲时间来重构应用程序。

典型示例：应用程序虚拟化，其中应用程序与操作系统打包在一起以虚拟机方式运行，而不是局限于专用硬件上。

好处

1. 提高应用程序性能
2. 降低运维成本

不适用的情况

1. 锁定在特定供应商解决方案中的应用程序可能难以重新打包和重新部署。
2. 最新的部署平台可能不支持较旧的操作系统。

增加新层（AUGMENT WITH NEW LAYERS）

许多公司通过在新的渠道（如mobile和Salesforce）上交付应用程序以及与合作伙伴应用程序集成来创造业务价值。增加新层是一种软件开发模式，可以帮助新应用程序和渠道访问现有应用程序功能，从而减少开发时间和成本，因为无需重新开发功能。最好在存在复杂和关键功能的地方使用它，因为它已经过一段时间的全面验证了。

为避免引入过多的复杂性，新增层通常没有额外的业务逻辑，而只是作为新旧应用之间的适配器。

适用情况

1. 当源代码不可用
2. 修改现有应用程序风险太大时
3. 最新的部署平台不支持较旧的操作系统。

增加新层为逐步实现应用程序架构现代化奠定了基础。随着时间的推移，旧的应用程序功能可以被重写，旧的堆栈也会被淘汰。然后可以使用此模式从现有应用程序（称为strangler应用程序）逐步迁移，这通常比一次性重写更好。

案例

1. 现有的业务应用在当前虚拟化或容器平台不支持的操作系统上运行。它可以通过标准API访问。编写了一个访问此API的适配器微服务。然后，新的应用程序和其他微服务使用该微服务来访问业务的功能。

2. 用Visual Basic编写的排序应用在其数据库后端广泛使用复杂的存储过程。正在为手机和平板电脑开发新的移动订购应用程序。使用与新应用程序的微服务接口创建适配器层。适配器隐藏数据库和存储过程。所有新应用程序都访问适配器，适配器将请求转换为对存储过程的调用。

好处

它允许使用当前体系结构的新开发使用现有应用程序。 但另一方面使现有应用程序更易于部署和管理，成本更低

重写（REWRITE）

重写是更新应用程序架构以实现完全现代化技术栈的唯一方法。

缺点

1. 代价昂贵
2. 耗时
3. 可能需要数年才能抵消成本。

适用情况

1. 供应商可能不再支持在操作系统和硬件上运行的旧有的应用程序。
2. 公司不希望在没有供应商支持的安全网的情况下运行其关键业务系统。
3. 已经没有人具备操作旧系统的技能。

实践指导

最好的方法是逐步迁移旧应用程序的功能，增加新层可以实现这一点。延缓重写也是一个好主意，因为某些功能将变得过时，根本不需要迁移。抵制简单迁移旧行为的诱惑，而不是像开发新应用程序那样计划和优先排序。这将有助于创建更灵活的应用程序，并适应将要发生的变化。

模式选择

现代化流程

主要目标是创建计划并多次执行，每次迭代都会产生新的增量值。这降低了翻新和替换的风险。

发现阶段的交互式会话识别当前的应用程序状态和目标。 主要利益相关者探索实现现代化的潜在方式，并开始确定步骤的优先顺序，以实现承诺。

在设计阶段，一系列步骤通过分析，概念验证和试点来完成整个过程。 自动化应用程序代码分析有助于识别潜在问题并估算工作量。 在此步骤中设计所需状态，选择现代化模式，并创建详细的部署计划。

部署计划将在下一步中执行。 该模型使用多次迭代以降低风险并从之前的步骤中学习，应该由一个由迁移专家团队指导。 随着项目的发展和利益相关者的变化，该小组将抓住最佳实践并确保可持续性。

Tip

IDEA的live template无疑对提升开发效率是很有帮助的，以下是一些常用的代码生成快捷键。使用cmd+J可以查看快捷键列表。

Share

最近在开马丁福勒的《重构2》，摘抄了一些重构理念：

重构概念

Refactoring (noun): a change made to the internal structure of software to make it easier to understand and cheaper to modify without changing its observable behavior. 重构（名词）：对软件内部结构的一种调整，目的是在不改变软件可观察行为的前提下，提高其可理解性，降低其修改成本。

Refactoring (verb): to restructure software by applying a series of refactorings without changing its observable behavior. 重构（动词）：使用一系列重构手法，在不改变软件课观察行为的前提下，调整其结构。

重构时机

When you have to add a feature to a program but the code is not structured in a convenient way, first refactor the program to make it easy to add the feature, then add the feature. 在向程序添加功能时，代码不能以方便的方式来构建，首先应重构程序以便于添加功能，然后再添加该功能。

重构的保证

Before you start refactoring, make sure you have a solid suite of tests. These tests must be self-checking. 在开始重构之前，请确保有一套可靠的测试。这些测试必须是能自查的。

Refactoring changes the programs in small steps, so if you make a mistake, it is easy to find where the bug is. 重构会以较小的步骤修改程序，因此如果犯了错误，会很容易找到该错误的位置。

Any fool can write code that a computer can understand. Good programmers write code that humans can understand. 任何傻瓜都可以编写计算机可以理解的代码。优秀的程序员编写人类可以理解的代码。 我不是个伟大的程序员，我只是个有着一些优秀习惯的好程序员。（kent beck）

重构与性能

Most of the time you should ignore it. If your refactoring introduces performance slow-downs, finish refactoring first and do performance tuning afterwards. 大多数时候应该忽略性能问题。如果重构使得性能降低，请先完成重构后再进行性能调整。

Refactoring is always done to make the code “easier to understand and cheaper to modify”. This might speed things up or slow things down. With performance optimization, I only care about speeding up the program, and am prepared to end up with code that is harder to work with if I really need that improved performance. 重构专注于软件结构的优化，它可能加快或减慢软件执行速度，性能优化则只专注于加快软件执行速度，往往会牺牲些软件结构。

重构的原则

Brevity is the soul of wit, but clarity is the soul of evolvable software. 简短是智力的灵魂，但清晰度是可进化软件的灵魂。

When programming, follow the camping rule: Always leave the code base healthier than when you found it. 编程时，请遵循下面的通用规则： 始终保持代码库比最初代码库更健康。（童子军军规）

The true test of good code is is how easy it is to change it. 优秀代码的真正考验是有多容易去改变它。

If someone says their code was broken for a couple of days while they are refactoring, you can be pretty sure they were not refactoring 如果有人说他们的代码在重构后坏了好几天，可以肯定的是他们不是在做重构。

Any bugs that I notice during refactoring should still be present after refactoring (though I can fix latent bugs that nobody has observed yet). 重构过程中我注意到的任何错误在重构后仍然应该存在（尽管我可以修复任何人都没有观察到的潜在错误）。

重构的步骤

THE TWO HATS:adding functionality and refactoring

When I add functionality, I shouldn’t be changing existing code; I’m just adding new capabilities. I measure my progress by adding tests and getting the tests to work. When I refactor, I make a point of not adding functionality; I only restructure the code. I don’t add any tests (unless I find a case I missed earlier); I only change tests when I have to accommodate a change in an interface. 两个帽子：添加功能和重构

当添加功能时，你不应该更改既有代码，只管添加新功能。通过测试（并让测试正常运行），通过测试来衡量我的工作进度。当重构时，你就不能再添加功能，只管改进代码结构。此时你不应添加任何测试（除非发现先前遗漏的用例），只在绝对必要（用以处理接口变化）时才修改测试。

关于重构的目的

重构的全部目的是让开发人员更高效地编程，以更少的努力创造更多的价值。

1. 重构改进了软件设计
2. 重构使软件更容易理解
3. 重构帮助开发人员发现错误
4. 重构帮助开发人员更高效地编程

参考文献

• Previous
  ARTS05
• Next
  ARTS07