自定义二叉树中的最短路径
这是一个编码竞赛的问题
最初的问题可以在这里找到http://www.olympiad.org.za/olympiad/wp-content/uploads/2014/03/2013-PO-Question-Paper.pdf问题5。
Hulsbos高中的艾伦·斯密瑟穿过大厅的最短路
大厅里堆满了一排排椅子，但每排都有两把椅子不见了。每排椅子的编号从1到100不等。编写一个程序来计算从前面到大厅后面最短路径的长度。每把椅子有一个单位宽，每一行深一个单位(从椅子的前部到后面椅子的前部)。对角移动是不可能的。你可以从前排的任何空隙开始，在最后一行的任何空隙后面结束。你总是在缺口中间穿行。图解是穿过大厅的最短路径，有五排椅子。在插图中，大厅只有10把椅子宽，而不是100把椅子。输入中的第一个数字将包含n--行数。接下来的n行将有两个数字，用空格分隔，表示空隙在哪里。输入示例:5 3 6 2 8 4 5 7 8 3 10
我认为我有一个高效的算法，我认为这个算法可以工作，但我不知道如何将它实现到Java中。
我想要做的是将每个选项分解为一个搜索树，例如，如果用户输入是：
行数:3
舱位:4 7 2 9 8 11
制作2棵搜索树：
4 7
2 9 2 9
8 11 8 11 8 11 8 11然后找出每个节点之间的差异最小的路径，所以在这种情况下，最短的路径是在第二棵树中，7->9->8，总距离为5(x=7-9=8)，所以我的问题是
- 考虑到这个问题，这个算法可以接受吗？
- 如何在java中实现此算法或其他算法？
@JuanLopes，举个例子(0表示一个空格)。
Row6: 0 2 3 4 5 0 8 9
Row5: 0 2 3 4 5 0 8 9
Row4: 1 2 3 0 5 6 0 8 9
Row3: 1 2 3 0 5 6 0 8 9
Row2: 1 2 3 0 5 6 0 8 9
Row1: 1 2 3 0 5 6 0 8 9
我从您的算法中了解到的是，它分别查看每一行。因此，通过第1-4行，每个空格到下一行的距离是相等的，但是当您到达第5行时，如果您沿着所有4s都丢失的路径走，那么与所有7s丢失的路径相比，您所花的时间要长一些，您的解决方案是否考虑到了这一点？
回答 1
Stack Overflow用户
发布于 2015-04-25 18:13:18
您所描述的算法是不可接受的，因为最多可以有100行，所以如果在每一行中，树中的节点数加倍，那么在最坏的情况下，树中将有2^101个节点。
这个问题可以通过一个简单的动态规划来解决，在每个步骤中，您必须在第一个和第二个间隙之间选择最小值：
T(0, j) = 1
T(i, j) = 1+min(
abs(pos(i, j)-pos(i-1, 0)) + T(i-1, 0),
abs(pos(i, j)-pos(i-1, 1)) + T(i-1, 1))其中i是i第四行，j要么是0，要么是1，表示我们在最后一个回合选择了哪个间隙。以下是一些Java实现示例：
import static java.lang.Math.abs;
import static java.lang.Math.min;
public class Main {
public static int solve(int[][] P) {
int a = 1, b = 1;
for (int i = 1; i < P.length; i++) {
int na = 1 + min(
abs(P[i][0] - P[i - 1][0]) + a,
abs(P[i][0] - P[i - 1][1]) + b);
int nb = 1 + min(
abs(P[i][1] - P[i - 1][0]) + a,
abs(P[i][1] - P[i - 1][1]) + b);
a = na;
b = nb;
}
return min(a, b);
}
public static void main(String... args) {
System.out.println(solve(new int[][]{
{3, 6},
{2, 8},
{4, 5},
{7, 8},
{3, 10},
}));
System.out.println(solve(new int[][]{
{4, 7},
{2, 9},
{8, 11}
}));
}
}https://stackoverflow.com/questions/29866915
复制相似问题
腾讯云开发者
