• • 三角矩阵(Triangle)

• 路径总数(Unique Paths)

• 路径总数2(Unique Paths II)

• 最小路径和(Minimum Path Sum)

三角矩阵(Triangle)

---

• 题目描述:

链接：https://www.nowcoder.com/questionTerminal/2b7995aa4f7949d99674d975489cb7da

来源：牛客网

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，

例如，给出的三角形如下：

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

最小的从顶部到底部的路径和是2 + 3 + 5 + 1 = 11。

• 解题思路

• 方法一代码

/**

• 三角矩阵

• @param triangle

• @return

*/

public int minimumTotal(ArrayList<ArrayList> triangle) {

if (triangle == null) return 0;

if (triangle.isEmpty()) return 0;

if (triangle.size() == 1) return triangle.get(0).get(0); //只有一行数据的时候

//row表示行

for (int row = 1; row < triangle.size(); row++) {

//col表示列

for (int col = 0; col < triangle.get(row).size(); col++) {

if (col == 0) {

//第一个, 直接加上一行第一个就行

triangle.get(row).set(col, triangle.get(row - 1).get(0) + triangle.get(row).get(0));

} else if (col == row) {

//每一行最后一个数据

triangle.get(row).set(col, triangle.get(row - 1).get(row - 1) + triangle.get(row).get(col));

} else {

triangle.get(row).set(col, Math.min(triangle.get(row - 1).get(col - 1), triangle.get(row - 1).get(col))

• triangle.get(row).get(col));

}

}

}

//返回最后一行的最小的那个数字

ArrayList numList = triangle.get(triangle.size() - 1);

int ret = numList.get(0);

for (int i = 1; i < numList.size(); i++) {

ret = Math.min(ret, numList.get(i));

}

return ret;

}

• 方法二代码

public int minimumTotal2(ArrayList<ArrayList> triangle) {

if (triangle == null) return 0;

if (triangle.isEmpty()) return 0;

if (triangle.size() == 1) return triangle.get(0).get(0); //只有一行数据的时候

for (int row = triangle.size() - 1 - 1; row >= 0; row–) {

for (int col = 0; col < row + 1; col++) {

triangle.get(row).set(col, Math.min(triangle.get(row + 1).get(col), triangle.get(row + 1).get(col + 1))

• triangle.get(row).get(col));

}

}

return triangle.get(0).get(0);

}

路径总数(Unique Paths)

---

• 问题描述

链接：https://www.nowcoder.com/questionTerminal/166eaff8439d4cd898e3ba933fbc6358

来源：牛客网

一个机器人在m×n大小的地图的左上角（起点，下图中的标记“start"的位置）。

机器人每次向下或向右移动。机器人要到达地图的右下角。（终点，下图中的标记“Finish"的位置）。

可以有多少种不同的路径从起点走到终点？

上图是3×7大小的地图，有多少不同的路径？

备注：m和n小于等于100

• 解题思路

• 代码

/**

• 路径总数(Unique Paths)

• @param “m行数”

• @param “n列数”

• @return

*/

public int uniquePaths(int m, int n) {

if (m == 0 || n== 0) return 0;

//构建二维数组

int[][] answers = new int[m][n];

//将第一行和第一列初始化为1

for (int i = 0; i < n; i++) {

answers[0][i] = 1;

}

for (int i = 0; i < m; i++) {

answers[i][0] = 1;

}

//从第二行第二列开始动态计算

for (int row = 1; row < m; row++) {

for (int col = 1; col < n; col++) {

先自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则近万的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《Java开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频

如果你觉得这些内容对你有帮助，可以扫码领取！

最后

Java架构学习技术内容包含有：Spring，Dubbo，MyBatis, RPC, 源码分析，高并发、高性能、分布式,性能优化，微服务 高级架构开发等等。

还有Java核心知识点+全套架构师学习资料和视频+一线大厂面试宝典+面试简历模板可以领取+阿里美团网易腾讯小米爱奇艺快手哔哩哔哩面试题+Spring源码合集+Java架构实战电子书+2021年最新大厂面试题。

mg" style=“zoom: 33%;” />

最后

Java架构学习技术内容包含有：Spring，Dubbo，MyBatis, RPC, 源码分析，高并发、高性能、分布式,性能优化，微服务 高级架构开发等等。

还有Java核心知识点+全套架构师学习资料和视频+一线大厂面试宝典+面试简历模板可以领取+阿里美团网易腾讯小米爱奇艺快手哔哩哔哩面试题+Spring源码合集+Java架构实战电子书+2021年最新大厂面试题。
[外链图片转存中…(img-OjpjiFyG-1711510941070)]

需要更多Java资料的小伙伴可以帮忙点赞+关注，点击传送门，即可免费领取！