目前有两个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
请问大家有没有好的算法 请提供以下 最好能附上代码。
其中一个内容是 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
请问大家有没有好的算法 请提供以下 最好能附上代码。
解决方案 »
- java.lang.NoSuchMethodError: javax.persistence.OneToMany.orphanRemoval()Z
- 求一道笔试题,统计页面访问次数?
- java如何实现伪地址栏
- 请救大家eclipse和tomcat5的集成
- 用AXIS自动生成客户端测试文件
- hibernate的连接查询问题
- logic:equal这个标签是什么功能?谢谢啊
- struts的基础配置问题,急,调了两天了......
- 用Ant编译400多个文件,出现内存溢出异常(JDK1.4.2)
- 推荐一些讲java3d的教材或资料吧,谢谢啦
- 将抓取后的网页转码
- 写ajax2 webwervice接口的[.。.receivers.RPCMessageReceiver] null 在线等
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);
}
}
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 16]
[1, 2, 3, 4]
[1, 2, 3, 4, 5, 6, 7, 8, 15]
t.querryStartAt(10),运行结果:
[10, 11]t.querryStartAt(8),运行结果:
[8, 9]
[8, 15]
下面这个程序是正确的。
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);
}
}