首页 > [LeetCode 120] - 三角形(Triangle)

[LeetCode 120] - 三角形(Triangle)

问题

给出一个三角形,找出从顶部至底部的最小路径和。每一步你只能移动到下一行的邻接数字。

例如,给出如下三角形:

[

     [2],

    [3,4],

   [6,5,7],

  [4,1,8,3]

]

从顶部至底部的最小路径和为11(即2+3+5+1=11)。

注意:

加分项-如果你能只使用O(n)的额外空间,n为三角形中的总行数。

 

初始思路

最直接的思路就是把路径都走一遍。即从顶点出发,分别往左中右移动(如果可能的话);然后对走到的位置继续进行同样移动,直到走到最后一行。这样就可以得到一个递归的方案,而递归的结束条件就是前面所说的走到最后一行。伪代码如下:

[最短路径长度] 查找路径(当前节点坐标,当前路径值)

如果是最后一行,返回当前路径值+当前节点值

否则

  如果可以往左下走,左路径 = 当前路径值 + 查找路径(左下节点坐标,当前路径值)

  如果可以往下走,下路径 = 当前路径值 + 查找路径(下节点坐标,当前路径值)

  如果可以往右下走,右路径 = 当前路径值 + 查找路径(右下节点坐标,当前路径值)

  找出左路径,下路径和右路径中的最小值,返回该最小值

结合范例数据仔细分析一下上面的伪代码, 可以发现其中有不少重复的步骤。如2->3->5和2->4->5后面的处理是完全相同的。回想一下我们在 [LeetCode 132] - 回文分割II(Palindrome Partitioning II) 中的做法,可以使用一个map保存已计算过的路径来应对这种重复。这里我们使用std::map<std::pair<int, int>, int>,将某点的坐标作为map的key,从key出发的最小路径作为值。

按以上思路完成代码提交后发现有些测试用例不能通过,如:

[

      [-1]

     [3,2]

   [-3,1,-1]

]

按以上算法得出的值为-2,而期望的值为-1。-2为-1 -> 2-> -3这条路径得出的值,而-1为路径-1 -> 3 -> -3。看来题目中的邻接(英文原文adjacent)规定只能往下或者右走。修改也很简单,将代码中处理向左下走的那部分逻辑去掉即可。最终通过了Judge Small和Judge Large的代码如下:

 1 class Solution {
 2     public:
 3         int minimumTotal(std::vectorint> > &triangle)
 4         {
 5             pathInfo.clear();
 6             
 7             if(triangle.empty())
 8             {
 9                 return 0;
10             }
11 
12             return FindMinPath(triangle, 0, 0, 0);
13         }
14         
15     private:
16         int FindMinPath(std::vectorint>>& input, int X, int Y, int currentPathValue)
17         {
18             if(X == input.size() - 1)
19             {
20                 return currentPathValue + input[X][Y];
21             }
22             
23             
24             auto iter = pathInfo.find(Coordinate(X, Y));
25             
26             if(iter != pathInfo.end())
27             {
28                 return currentPathValue + iter->second;
29             }
30             
31             
32             //int left = currentPathValue;
33             int down = currentPathValue;
34             int right = currentPathValue;
35             int min = 0;
36             bool minUpdated = false;
37             
38             /*
39             if(Y - 1 >= 0)
40             {
41                 left += FindMinPath(input, X + 1, Y - 1, input[X][Y]);
42                 min = left;
43                 minUpdated = true;
44             }
45             */
46             
47             if(Y < input[X + 1].size())
48             {
49                 down += FindMinPath(input, X + 1, Y, input[X][Y]);
50                 
51                 if(!minUpdated || min > down)
52                 {
53                     min = down;
54                     minUpdated = true;
55                 }
56                 
57                 if(Y + 1 < input[X + 1].size())
58                 {
59                     right += FindMinPath(input, X + 1, Y + 1, input[X][Y]);
60                     if(!minUpdated || min > right)
61                     {
62                         min = right;
63                     }
64                 }
65             }
66             
67                         pathInfo[Coordinate(X, Y)] = min - currentPathValue;
68             
69             return min;
70         }
71 
72         
73         std::mapint, int>, int> pathInfo;
74         
75         typedef std::pair<int, int> Coordinate;
76     };
minimumTotal

 

获得加分的方案

在上面的方案中,我们使用了以每个点坐标为key的map来保存已计算过路径,空间复杂度达到了n^2的级别,即不计map的额外消耗需要1 + 2 + 3 +..... + n = n(n-1) / 2的空间来储存这些信息。

让我们改变一下思路,不考虑某点出发的最短路径,而考虑到达某点的最短路径。给出一个点,怎么得到到该点的最短路径?可以发现有三种情况:

  • 该点为最左边的点,即纵坐标为0。由于我们前面已经知道题目不允许往左下走,所以这种情况没得选择,最短路径就是上面的点的最短路径加当前点的值。
  • 该点为最右边的点,即纵坐标为n-1(n为该行的长度)。由于是三角形,上一行中没有纵坐标为n-1的点。这种情况最短路径只能是左上的点的最短路径加当前点的值。
  • 其他情况。有两种选择,左上的点或者上方的点,需要取其中的小者来加当前点的值。

用上面方法得出第n行的所有点的最短路径后,我们发现第n-1行即上面一行的信息已经不再需要被存储了,因为第n+1行即下一行可以完全通过第n行的信息来算得自己的最短路径值。那么我们需要的最大存储空间就为最后一行的点的个数。不难看出,该数字和行数是相等的。这就符合了加分项中空间复杂度为O(n)的要求。

根据以上算法,我们将第一行中唯一一个值直接存到以纵坐标为下标的一个数组pathInfo中。然后从第二行开始对每行中的每列进行遍历,不断更新直到最后一行最后一列即可得到一个存有最后一行中每个点的最短路径的数组。对数组pathInfo进行一次遍历找出最小值即为题目所求。在处理过程中,还需要注意一个小细节:遍历每行时,需要从最右边的列开始。因为如果从左边开始,我们更新pathInfo[0]时就把上一层的信息覆盖了,而新的pathInfo[1]还需要用到上一层的信息(它需要从上一层的0和1中选一个最小值)。

最终代码如下:

 1 class Solution
 2     {
 3     public:
 4         int minimumTotal(std::vectorint> > &triangle)
 5         {
 6             std::vector<int> pathInfo(triangle.size());
 7             
 8             pathInfo[0] = triangle[0][0];
 9             
10             for(int i = 1; i < triangle.size(); ++i)
11             {
12                 for(int j = i; j >= 0; --j)
13                 {
14                     if(j == 0)
15                     {
16                         pathInfo[j] = pathInfo[j] + triangle[i][j];
17                     }
18                     else if(j == triangle[i].size() - 1)
19                     {
20                         pathInfo[j] = pathInfo[j - 1] + triangle[i][j];
21                     }
22                     else
23                     {
24                         pathInfo[j] = pathInfo[j] < pathInfo[j - 1] ? pathInfo[j] : pathInfo[j - 1];
25                         pathInfo[j] += triangle[i][j];
26                     }
27                 }
28             }
29             
30             int min = *pathInfo.begin();
31             for(auto iter = pathInfo.begin() + 1; iter != pathInfo.end(); ++iter)
32             {
33                 if(min > *iter)
34                 {
35                     min = *iter;
36                 }
37             }
38             
39             return min;
40         }
41     };
minimumTotal_Bonus

使用了新的算法后,不但减少了空间复杂度,递归也不再需要了,过Judge Large的时间由130ms左右降到了40ms左右。

 

转载于:https://www.cnblogs.com/shawnhue/p/leetcode_120.html

更多相关:

  • 大牛们应该对路径都很了解了,这篇文章主要给像我这样的入门小白普及常识用的,啊哈下面的路径介绍针对windows,其他平台的暂时不是很了解。在编写的py文件中打开文件的时候经常见到下面其中路径的表达方式:open('aaa.txt')open('/data/bbb.txt')open('D:\user\ccc.txt')这三种表达式...

  • 1)绝对路径:绝对路径是指目录下的绝对位置,直接到达目标位置,通常是从盘符开始的路径。例如:C:windowssystem32cmd.exe  注意: 在不同系统的情况系 windows下是“”,linux和unix下是“/” ,但在win中没有本质区别。linux和unix系统中绝对路径 以“/”为起始 例:/home/us...

  •     最终运行效果 当然,这个Application context路径可以直接删掉不需要最终访问路径就会变成http://localhost:8080/...

  •     1、在js代码里面 或者 html里面用"v-bind:"或":属性名"绑定路径的时候使用 require('@/assets/home/imgName.png') 2、在css或者scss或者html里面的src中引入图片使用(注意如果是:src=后面用第1种方式引入路径) ~@/assets/components...

  • 寻路算法大总结! 交换机生成树采用的是完全不同的D-V(distance vector)距离矢量算法,并不是很可靠. 并不是任意两点之间的最短路径,因为任意两点之间取最短路径可能有环路:总权更大 交换机STP不一定是最小生成树!!!举例论证 因为它只是所有交换机到根桥最短 贪心算法的味...

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...