120. Triangle(中等)

时间:2022-06-25 12:32:29

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only \(O(n)\) extra space, where n is the total number of rows in the triangle.

先说一个坑:本题绝不是找每行最小元素,然后把它们加起来那么简单.原因是这些元素是有路径的!看下例:

[
[-1],
[2, 3],
[1,-1,-3],
]

结果应为 -1 + 2 + -1 = 0, 而不是 -1 + 2 + -3 = -2.

idea来自 http://www.cnblogs.com/liujinhong/p/5551932.html 中的图片,感谢这位同学.

本 code 属于 方法一: 自上而下,破坏原数组A. \(O(n^2)\) time, \(O(1)\) space

另一种方法 方法二: 自下而上,不破坏数组A. 维护一个长度为 n 的 1-dim 数组. \(O(n^2)\) time, \(O(n)\) space.

方法一的解题思路(请务必参照上面网址中的图片):

从上至下,将值按照"路径"加到下一层
除了A[0][0]这种情况外,还会遇到下列三种(注意判断条件)情况,共 4 cases:
case 1: left, right 上邻居都存在
case 2: left上不存在, right上存在
case 3: left上存在, right上不存在
case 4: A[0][0](它没left上 和 right上邻居), 我们 do nothing, 保留A[0][0]数值不变.

下面的图可以让我们看清上面 4 cases 的判断条件:

下面是元素索引:

	[
[0,0],
[1,0],[1,1] , [row-1,col-1],[row-1,col],
[2,0],[2,1],[2,2], [row, col]
[3,0],[3,1],[3,2],[3,3]
]

人家想法,自个代码(方法一,破坏原数组):

\(O(n^2)\) time, \(O(1)\) space

// idea来自 http://www.cnblogs.com/liujinhong/p/5551932.html
// 本 code 属于方法一:自上而下,破坏原数组A. $O(n^2)$ time, $O(1)$ space
// 另一种方法方法二:自下而上,不破坏数组A. 维护一个长度为 n 的 1-dim 数组.
// $O(n^2)$ time, $O(n)$ space.
int minimumTotal(vector<vector<int>>& A) {
const int n = A.size();
if (n == 0) return 0; // 从上至下,将值按照"路径"加到下一层
// 除了A[0][0]这种情况外,还会遇到下列三种情况,共 4 cases.
for (int row = 0; row < n; row++) {
for (int col = 0; col <= row; col++) {
if ((row - 1 >= 0) && (col - 1 >= 0) && (col <= row - 1)) {
// case 1: left, right 上邻居都存在
int mi = min(A[row - 1][col - 1], A[row - 1][col]);
A[row][col] += mi;
} else if ((row - 1 >= 0) && (col - 1 < 0) && (col <= row - 1)) {
// case 2: left上不存在, right上存在
A[row][col] += A[row - 1][col];
} else if ((row - 1 >= 0) && (col - 1 >= 0) && (col > row - 1)) {
// case 3: left上存在, right上不存在
A[row][col] += A[row - 1][col - 1];
}
// case 4: A[0][0](它没left上 和 right上邻居)
// do nothing, 保留A[0][0]数值不变.
}
} // 返回A中最下面的一行(A[n-1])最小元素
int res = INT_MAX;
for (int i = 0; i < A[n - 1].size(); i++) {
res = min(res, A[n - 1][i]);
}
return res;
}

方法二:

自下而上,不破坏数组A.

关键是找本层和上一层元素的关系,那就是 temp[j] = A[i,j] + min(temp[j], temp[j+1]).

\(O(n^2)\) time, \(O(n)\) space.

// 方法二:
// 自下而上,不破坏数组A. 维护一个长度为 n 的 1-dim 数组.
// $O(n^2)$ time, $O(n)$ space.
int minimumTotal(vector<vector<int>>& A) {
const int n = A.size();
if (n == 0)
return 0;
if (n == 1)
return A[0][0];
vector<int> temp;
// A 最后一行存入temp
for (int j = 0; j < n; j++)
temp.push_back(A[n - 1][j]); // 从倒数第二行到上按路径元素取min的,相加
// 对应关系:
// A[2, 1]
// temp[1] temp[1+1] for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
int smal = min(temp[j], temp[j + 1]);
// 若当前使用temp[0], temp[1]
// temp[0] 被改, 但不影响下次使用temp[1], temp[2]
temp[j] = A[i][j] + smal;
}
}
return temp[0];
}

120. Triangle(中等)的更多相关文章

  1. leetcode 118&period; Pascal&&num;39&semi;s Triangle 、119&period; Pascal&&num;39&semi;s Triangle II 、120&period; Triangle

    118. Pascal's Triangle 第一种解法:比较麻烦 https://leetcode.com/problems/pascals-triangle/discuss/166279/cpp- ...

  2. 【LeetCode】120&period; Triangle 解题报告(Python)

    [LeetCode]120. Triangle 解题报告(Python) 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 题目地址htt ...

  3. LeetCode - 120&period; Triangle

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...

  4. &lbrack;LeetCode&rsqb;题解(python):120 Triangle

    题目来源 https://leetcode.com/problems/triangle/ Given a triangle, find the minimum path sum from top to ...

  5. leetcode 120 Triangle ----- java

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...

  6. 【LeetCode】120 - Triangle

    原题:Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacen ...

  7. 120&period; Triangle

    题目: Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjace ...

  8. LeetCode OJ 120&period; Triangle

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...

  9. LeetCode 120&period; Triangle (三角形)

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent n ...

随机推荐

  1. js倒计时,显示NaN天NaN时NaN分(或显示天时分)

    最近在开发跨平台的应用,在做秒杀功能时,倒计时出现了问题.默认在Chrome浏览器中运行,倒计时没出现问题.而在IE浏览器,火狐浏览器,safari浏览器上运行时,则显示NaN天NaN时NaN分(或显 ...

  2. linux下遍历目录&lpar;转-在于思考&rpar;

    遍历目录的主要思想 由于目录就是一颗树,所以遍历目录就转换为遍历一棵树.谈到树的遍历就再熟悉不过了,有树的前序.层次和后序遍历,我使用的是前序遍历,后序遍历和前序遍历本质上一样,而层次遍历要比前两个麻 ...

  3. 设置HTML表格细边框

    简介:WEB前端|这是关于怎么设置HTML表格细边框的问题,把表格边框设置为细小的线条边框一般我们用表格的时候总会给它个border属性,比如:<tableborder="1&quot ...

  4. 最短路算法模板SPFA、disjkstra、Floyd

    朴素SPFA(链表建边) #include <iostream> #include <cstdio> #include <cstring> #include &lt ...

  5. Leetcode(59)-Count Primes

    题目: Description: Count the number of prime numbers less than a non-negative number, n. 思路: 题意:求小于给定非 ...

  6. iOS开发简记(8):数据持久化

    数据持久化,也就是把数据保存到磁盘,以后可以再读取出来使用(也可以再次更改或删除).很多场景需要数据持久化,比如为了减轻服务器的访问与存储压力,客户端需要在本地做一些数据持久化的工作. iOS的数据持 ...

  7. 把url的参数解析出来

    https://zhidao.baidu.com/question/455797151306205205.html

  8. 排序——冒泡排序&lpar;java描述&rpar;

    百度百科:冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法. 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小.首字母从A到Z)错误就把他们交 ...

  9. vuejs使用FormData对象,ajax上传图片文件

    我相信很多使用vuejs的朋友,都有采用ajax上传图片的需求,因为前后端分离后,我们希望都能用ajax来解决数据问题,传统的表单提交会导致提交成功后页面跳转,而使用ajax能够无刷新上传图片等文件. ...

  10. ubuntun16&period;0 登陆密码忘记

    1. 开机,如下图所示(没有装虚拟机,手机拍的图片凑合这看把): 2. 此时会有一个选项:Advanced Options for Ubuntu, 选中直接回车 ,如下图: 3. 看到里面有很多选项, ...