java - 你如何在 Java 中找到这棵树的路径数?
问题描述
我试图找到以这种方式表示的树的路径数:
1 4
2 4
3
4
-1
-1 代表结束,每个数字代表下一个节点。每条线都是一个节点,它们的编号从 0 开始。因此,在这个特定的实例中,有 3 条路径:0>1>2>3>4>-1、0>4>-1 和 0>1>4 >-1。
import java.io.*;
import java.util.*;
public class PathFinder {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayList<ArrayList<String>> wholeList = new ArrayList<ArrayList<String>>();
while (scanner.hasNext()) {
String input = scanner.nextLine();
StringTokenizer st = new StringTokenizer(input, " ");
ArrayList<String> temp = new ArrayList<String>();
while(st.hasMoreTokens()) {
temp.add(st.nextToken());
}
wholeList.add(temp);
}
return count;
}
}
解决方案
我建议您更改数组,使它们包含整数而不是字符串。然后您可以使用递归解决方案:
import java.io.*;
import java.util.*;
public class PathFinder {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<List<Integer>> wholeList = new ArrayList<>();
while (scanner.hasNext()) {
String input = scanner.nextLine();
StringTokenizer st = new StringTokenizer(input, " ");
List<Integer> temp = new ArrayList<>();
while(st.hasMoreTokens()) {
temp.add(Integer.valueOf(st.nextToken()));
}
wholeList.add(temp);
}
countRoutes(wholeList, 0);
System.out.println(count);
}
private static int count = 0;
private static void countRoutes(List<List<Integer>> tree, int nodeFrom) {
for (Integer target : tree.get(nodeFrom)) {
if (-1 == target) {
count++;
} else {
countRoutes(tree, target);
}
}
}
}
如果您想查看路线,可以稍微修改方法:
private static void printRoutes(List<List<Integer>> tree, int nodeFrom, String route) {
for (Integer target : tree.get(nodeFrom)) {
if (-1 == target) {
count++;
System.out.println(route + "->-1");
} else {
printRoutes(tree, target, route + "->" + target);
}
}
}
并从主程序中调用它
printRoutes(wholeList, 0, "0");
2021 年 3 月 3 日更新
一种更有效的方法是缓存从给定节点到终点的路径数量:
private static int countRoutes(List<List<Integer>> tree,
int nodeFrom,
int[] pathsNumber)
{
if (nodeFrom == -1) {
return 1;
}
if (pathsNumber[nodeFrom] >= 0) {
return pathsNumber[nodeFrom];
}
int sum = 0;
for (Integer target : tree.get(nodeFrom)) {
sum += countRoutes(tree, target, pathsNumber);
}
pathsNumber[nodeFrom] = sum;
return sum;
}
然后在 main 方法中初始化数组 pathsNumber 并按如下方式调用此方法(-1 表示我们尚未计算通往该节点出口的路径数):
int[] pathsNumber = new int[wholeList.size()];
Arrays.fill(pathsNumber, -1);
System.out.println(countRoutes(wholeList, 0, pathsNumber));
推荐阅读
- java - 如何在 RazorPay 中获取创建的 orderID?
- excel - 在插入行时动态扩展范围
- java - 是否可以返回数据集而不是 MyBatis 中的任何映射模型类?
- reactjs - 多次反应浅比较工作?
- python - 如何修复 # 问题 400 指定 FLAC 编码以匹配文件头?
- angular - 当我输入超过 3 个字符时如何过滤数据
- xml - What happens when I declare beans and component-scan both in applicationContext.xml?
- php - 服务器返回了意外的 HTTP 状态代码
- podio - 如何在 Podio 字段中计算“下一个生日”
- scala - 将数组(行)的RDD转换为行的RDD?