领扣LintCode算法问题答案-1565. 飞行棋 I
目录
1565. 飞行棋 I描述样例 1：样例 2：
题解鸣谢
1565. 飞行棋 I
描述
有一个一维的棋盘，起点在棋盘的最左侧，终点在棋盘的最右侧，棋盘上有几个位置是跟其他的位置相连的，即如果A与B相连，则当棋子落在位置A时, 你可以选择是否不投骰子，直接移动棋子从A到B。并且这个连接是单向的，即不能从B移动到A，现在给定这个棋盘的长度length和位置的相连情况connections，你有一个六面的骰子(点数1-6)，最少需要丢几次才能到达终点。
下标从 1 开始length > 1起点不与任何其他位置连接connections[i][0] < connections[i][1]
样例 1：
输入: length = 10 和 connections = [[2, 10]]
输出: 1
解释:
1->2 (投骰子)
2->10(直接相连)
样例 2：
输入: length = 15 和 connections = [[2, 8],[6, 9]]
输出: 2
解释:
1->6 (投骰子)
6->9 (直接相连)
9->15(投骰子)
题解
public class Solution {
public int modernLudo(int length
, int[][] connections
) {
if (length
<= 7) {
return 1;
}
Map
<Integer
, List
<Integer>> map
= new HashMap<>();
for (int[] connection
: connections
) {
List
<Integer> l
= map
.get(connection
[1]);
if (l
== null
) {
l
= new ArrayList<>();
map
.put(connection
[1], l
);
}
l
.add(connection
[0]);
}
int[] steps
= new int[length
+ 1];
for (int i
= 1; i
<= 7; i
++) {
steps
[i
] = 1;
}
for (int i
= 8; i
<= length
; i
++) {
int minStep
= Integer
.MAX_VALUE
;
for (int j
= 1; j
<= 6; j
++) {
int step
= steps
[i
- j
] + 1;
if (step
< minStep
) {
minStep
= step
;
}
}
List
<Integer> connectionList
= map
.get(i
);
if (connectionList
!= null
) {
for (int connection
: connectionList
) {
int step
= steps
[connection
];
if (step
< minStep
) {
minStep
= step
;
}
}
}
steps
[i
] = minStep
;
}
return steps
[length
];
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
