求个算法
目前有两个List
其中一个内容是 1,2,3,4,5,6,7,8,8,9,4,4,10
另一个内容是 2,3,4,5,6,7,8,9,15,8,16,3,11
其中第一个list是起点 第二个list是终点 比如起点是1 终点是2 ， 启动2终点是3 ，起点是3 终点是4 ， 启动时4 终点是5， 启点是5 终点是6 ， 。。。。。。。。。。
我想通过这两个list查询出以下链路
链路1:1-2-3-4-5-6-7-8-9
链路2:1-2-3-4-16
链路3:1-2-3-4-5-6-7-8-15
链路4:10-11
请问大家有没有好的算法 请提供以下 最好能附上代码。
[最优解释]
之前贴的程序有bug……但连续3次发帖就不能回帖了。
下面这个程序是正确的。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Test {
private List<Integer> a = new ArrayList<Integer>();
private List<Integer> b = new ArrayList<Integer>();
// 构建结果集
private Map<Integer, List<Integer>> results = new HashMap<Integer, List<Integer>>();
// 静态分支号
private static int BRANCHNO = 1;
public Test() {
this.a = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 4, 10, 11, 11, 2,
13, 12, 13, 6, 14, 8, 8);
this.b = Arrays.asList(2, 3, 4, 5, 6, 7, 8, 9, 15, 8, 3, 11, 3, 12, 12,
12, 13, 5, 14, 8, 14, 15);
// 添加默认结果集
this.results.put(0, new ArrayList<Integer>());
}
/**
* 根据目标值theNum，从list中搜索对应值的索引值。因list中可有重复数字，因此返回值是一个数组。
*
* @param list
* list是需遍历的List
* @param theNum
* 是需要寻找的目标int整数
* @return int[]是list中与theNum相同的数的索引值。
* 如：目标List为{1,2,3,4,5,6,7,8,8,9,4,4,10}，需寻找数字4 nums =
* getNumsFromA(list, 4) 返回的nums内容为{3,10,11}，意思是第3、第10、第11个数为4。
*/
public List<Integer> getNumsFromList(List<Integer> list, int theNum) {
List<Integer> indexNums = new ArrayList<Integer>();
// 遍历整个list，将list中，与theNum相同的数字都找出来，并保存其index值。
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == theNum) {
indexNums.add(i);
}
}
// System.out.println("indexNums" + indexNums);
return indexNums;
}
// 传入的是起始的数值
public void iteratorMethod(List<Integer> aList, List<Integer> bList,
int startNum, int branchNo) {
// System.out.println(branchNo);
int childBranchNo = 0;
// 先从aList中获取与起始数值相匹配的数，形成索引值数组
List<Integer> numsFromA = new ArrayList<Integer>();
numsFromA = getNumsFromList(aList, startNum);
// System.out.println("numsFromA.size()" + numsFromA.size());
// 将遍历的数值放到结果中。
this.results.get(branchNo).add(startNum);
// 如果没有任何匹配数，则返回
if (numsFromA.size() == 0) {
return;
} else if (numsFromA.size() > 1) {
// 若numsFromA.size()>1，说明出现了新分支，需额外创建一个结果集保存链路。
// 子分支编号
childBranchNo = BRANCHNO;
for (int i = 1; i < numsFromA.size(); i++) {
// 添加一个结果集
List<Integer> temp = new ArrayList<Integer>();
temp.addAll(this.results.get(branchNo));
this.results.put(BRANCHNO, temp);
// 静态分支编号+1
BRANCHNO++;
}
}
// 数组长度不为零，有匹配数字，则根据该数组，从bList中获取相应的值
for (int i = 0; i < numsFromA.size(); i++) {
// 从bList中获取相应索引的值。
int numFromB = bList.get(numsFromA.get(i));
// System.out.println("numsFromA.get(i)=" + numsFromA.get(i) +
// ";numFromB=" + numFromB + ";startNum=" + startNum);
// 如果从bList中获取的值小于起始值，则终止
if (numFromB < startNum) {
// System.out.println(this.results.get(branchNo));
continue;
}
if (i > 0) {
// 如果i > 1 ，则需要进入分支。此处传入子分支编号，以遍历几条子分支。
branchNo = childBranchNo - 1;
branchNo += i;
// 进行迭代
iteratorMethod(aList, bList, numFromB, branchNo);
} else {
// 其他情况，进行普通迭代
iteratorMethod(aList, bList, numFromB, branchNo);
}
}
}
// 提供一个初始的入口方法
public void querryStartAt(int startNum) {
this.iteratorMethod(this.a, this.b, startNum, 0);
// 打印结果
for (int i = 0; i < results.size(); i++) {
System.out.println(this.results.get(i));
}
}
public static void main(String[] args) {
Test t = new Test();
t.querryStartAt(10);
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Test {
private List<Integer> a = new ArrayList<Integer>();
private List<Integer> b = new ArrayList<Integer>();
// 构建结果集
private Map<Integer, List<Integer>> results = new HashMap<Integer, List<Integer>>();
// 子分支编号
// private int childBranchNo = 0;
// 静态分支号
private static int BRANCHNO = 1;
public Test() {
this.a = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 4, 4, 10);
this.b = Arrays.asList(2, 3, 4, 5, 6, 7, 8, 9, 15, 8, 16, 3, 11);
// 添加默认结果集
this.results.put(0, new ArrayList<Integer>());
}
/**
* 根据目标值theNum，从list中搜索对应值的索引值。因list中可有重复数字，因此返回值是一个数组。
*
* @param list
* list是需遍历的List
* @param theNum
* 是需要寻找的目标int整数
* @return int[]是list中与theNum相同的数的索引值。
* 如：目标List为{1,2,3,4,5,6,7,8,8,9,4,4,10}，需寻找数字4 nums =
* getNumsFromA(list, 4) 返回的nums内容为{3,10,11}，意思是第3、第10、第11个数为4。
*/
public List<Integer> getNumsFromList(List<Integer> list, int theNum) {
List<Integer> indexNums = new ArrayList<Integer>();
int count = 0;
// 遍历整个list，将list中，与theNum相同的数字都找出来，并保存其index值。
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == theNum) {
indexNums.add(i);
count++;
}
}
return indexNums;
}
// 传入的是起始的数值
public void iteratorMethod(List<Integer> aList, List<Integer> bList,
int startNum, int branchNo) {
int childBranchNo = 0;
// 先从aList中获取与起始数值相匹配的数，形成索引值数组
List<Integer> numsFromA = new ArrayList<Integer>();
numsFromA = getNumsFromList(aList, startNum);
// 将遍历的数值放到结果中。
this.results.get(branchNo).add(startNum);
// 如果没有任何匹配数，则返回
if (numsFromA.size() == 0) {
return;
} else if (numsFromA.size() > 1) {
// 若numsFromA.size()大于1，说明出现了新分支，需额外创建一个结果集保存链路。
// 子分支编号
childBranchNo = BRANCHNO;
for (int i = 1; i < numsFromA.size(); i++) {
// 添加一个结果集
List<Integer> temp = new ArrayList<Integer>();
temp.addAll(this.results.get(branchNo));
this.results.put(BRANCHNO, temp);
// 静态分支编号+1
BRANCHNO++;
}
}
// 数组长度不为零，有匹配数字，则根据该数组，从bList中获取相应的值
for (int i = 0; i < numsFromA.size(); i++) {
// 从bList中获取相应索引的值。
int numFromB = bList.get(numsFromA.get(i));
// 如果从bList中获取的值小于起始值，则终止
if (numFromB < startNum) {
return;
}
// 如果i>0，则需要进入分支。此处传入子分支编号，以使用相应的结果集。
if (i > 0) {
branchNo = childBranchNo;
}
// 进行迭代
iteratorMethod(aList, bList, numFromB, branchNo);
}
}
// 提供一个初始的入口方法
public void querryStartAt(int startNum) {
this.iteratorMethod(this.a, this.b, startNum, 0);
// 打印结果
for(int i = 0; i< results.size(); i++) {
System.out.println(this.results.get(i));
}
}
public static void main(String[] args) {
Test t = new Test();
t.querryStartAt(1);
}
}
