数据结构算法问题

Question

目前有两个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
请问大家有没有好的算法 请提供以下 最好能附上代码。

Answer 1

用 hash set， 每个元素是一个整数对：import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
 *
 * @date   28/11/2012
 */
public class LinkCheck {
  
  public static void main(String[] args) {
    
    List<Integer> starts = Arrays.asList(1,2,3,4,5,6,7,8,8,9,4,4,10);
    List<Integer> ends = Arrays.asList(2,3,4,5,6,7,8,9,15,8,16,3,11);
    
    int len = Math.min(starts.size(), ends.size());
    
    Set<Link> links = new HashSet<Link>(len);
    for(int i=0; i<len; i++)
      links.add(new Link(starts.get(i), ends.get(i)));
    
    int[][] lists = new int[][] {
      
      {1, 2, 3, 4, 5, 6, 7, 8, 9},
      {1, 2, 3, 4, 16},
      {1, 2, 3, 4, 5, 6, 7, 8, 15},
      {10, 11}
    };
    
    for(int[] list : lists) {
      
      boolean valid = true;
      for(int i=1; valid && i<list.length; i++) {
        
        if( !links.contains(new Link(list[i-1], list[i])) )
          valid = false;
      }
      
      System.out.println(valid);
    }
  }
}class Link {
  
  private final int start;
  private final int end;
  Link(int start, int end) {
    
    this.start = start;
    this.end = end;
  }
  
  @Override
  public int hashCode() {
    
    return (start << 5) - start + end;
  }
  
  @Override
  public boolean equals(Object o) {
    
    if( o instanceof Link ) {
      
      Link t = (Link)o;
      return t.start == this.start && t.end == this.end;
    }
    else {
      
      return false;
    }
  }
}

Answer 2

其实这是一个图的另一种邻接点的存储方式，可以使用图的深度优先搜索遍历。
package com.tur.demo;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class Route {
    public static List<String> paths = new ArrayList<String>();    /**
     * 查找元素在数组中的下标，如果找不到，返回-1
     * @param array
     * @param number
     * @param startIndex
     * @return
     */
    public static int indexInArray(int[] array, int number, int startIndex) {
        for (int i = startIndex; i < array.length; ++i) {
            if (array[i] == number) {
                return i;
            }
        }        return -1;
    }    /**
     * 把List使用String形式表示
     * @param list
     * @param delimeter
     * @return
     */
    public static String listToString(List<Integer> list, String delimeter) {
        StringBuilder sb = new StringBuilder();
        for (int n : list) {
            sb.append(delimeter);
            sb.append(n);
        }        return (sb.length() > 0 ? sb.substring(delimeter.length()) : "");
    }    /**
     * 把路径加到入路径列表，并去掉重复的路径
     * @param path
     */
    public static void addPath(String path) {
        boolean included = false;
        for (int i = 0; i < paths.size(); ++i) {
            String str = paths.get(i);            if (path.contains(str)) {
                paths.set(i, path);
                included = true;
                break;
            } else if (str.contains(path)) {
                included = true;
                break;
            }
        }        if (!included) {
            paths.add(path);
        }
    }    public static void main(String[] args) {
        int[] startPoints = {1, 2, 3, 4, 5, 6, 7, 8, 8,  9, 4,  4,10};
        int[] endPoints =   {2, 3, 4, 5, 6, 7, 8, 9, 15, 8, 16, 3, 11};        List<Integer> path = new LinkedList<Integer>();
        for (int i = 0; i < startPoints.length; ++i) {
            path.add(startPoints[i]);
            travel(startPoints, endPoints, i, path);
            path.remove(new Integer(startPoints[i]));
        }        for (String str : paths) {
            System.out.println(str);
        }
    }    /**
     * 深度优先搜索路径
     *
     * @param startPoints
     * @param endPoints
     * @param startIndex
     * @param path
     */
    public static void travel(int[] startPoints, int[] endPoints, int startIndex, List<Integer> path) {
        if (startIndex == -1) { return; }        int end = endPoints[startIndex];
        path.add(end);        for (int i = startIndex; i < (startPoints.length) && startIndex != -1; ++i) {
            startIndex = indexInArray(startPoints, end, i + 1);
            travel(startPoints, endPoints, startIndex, path); // 深度搜索邻接点
        }        addPath(listToString(path, "-"));
        path.remove(path.size() - 1);
    }
}

Answer 3

首先感谢大家。不过兄弟你的这个算法还是有点问题 比如如下两个List
 Integer[] startPoints1 = {1,2, 3, 4, 5, 6, 7, 8, 8,  9, 4,  10,11,11,2,13,12,13,6,14,8,8};
  Integer[] endPoints1 =   {2, 3, 4, 5, 6, 7, 8, 9, 15, 8, 3, 11, 3,12,12,12,13,5,14,8,14,15};
打印的链路如下 
1-2-3-4-5-6-7-8-9-8-14
1-2-3-4-5-6-7-8-9-8-15
1-2-3-4-5-6-7-8-15
1-2-3-4-5-6-7-8-14
1-2-3-4-5-6-14-8-14
1-2-3-4-5-6-14-8-15
1-2-3-4-3
1-2-12-13-5
10-11-3
10-11-12-13-5
13-12-13-5打印以上链路不太对  没有满足下面两个条件
  第一  13不是链路的第一个节点 所以应存在13-12-13-5这条链路也就是链路的开始节点只能是1或者10 
  第二  1-2-3-4-3 这条链路有点问题  应该仅仅是1-2-3-4 就可以了 不应该再打印3了 应该已经重复了。  

Answer 4

第二  1-2-3-4-3 这条链路有点问题  应该仅仅是1-2-3-4 就可以了 不应该再打印3了 应该已经重复了。 
这个是一个回路，例如可以从4很方便的走回3，不需要可以在path.add(end);这里判断end节点是否已经在path里了，如果在，就直接返回

Answer 5

兄弟 上面那两个逻辑好处理 修改修改就ok了  但是这个深度查询方法 应该不支持这种情况吧  比如下面这两个list
[234=1001, 234=1, 91=1, 150=1, 316=1]
[150=1, 316=1, 270=1, 234=1, 91=1]
用你的代码打印出3条链路如下
第一条:234=1001-150=1-234=1
第二条:234=1-316=1-91=1
第三条:91=1-270=1
但是很明显 这种情况 只能有一条链路啊   234=1001-150=1-234=1-316=1-91=1-270=1

Answer 6

        int[] startPoints = {1, 2, 3, 4, 5, 6, 7, 8, 8,  9, 4, 10, 11, 11, 2,  13, 12, 13, 6,  14, 8, 8};
        int[] endPoints =   {2, 3, 4, 5, 6, 7, 8, 9, 15, 8, 3, 11, 3,  12, 12, 12, 13, 5,  14, 8, 14, 15};第一  13不是链路的第一个节点 所以应存在13-12-13-5这条链路也就是链路的开始节点只能是1或者10
与13对应的是12，13应该是开始结点

Answer 7

[code=javaimport java.util.ArrayList;
import java.util.List;public class ItEyeQues
{
private int[] int1 = {1,2,3,4,5,6,7,8,8,9,4,4,10};
private int[] int2 = {2,3,4,5,6,7,8,9,15,8,16,3,11};

/**
 *  传入一个终点，返回他对应的起点坐标
 * @param i
 * @return
 */
public List<Integer> getIndex(int i) {
List<Integer> index = new ArrayList<Integer>();
for(int j = 0; j < int1.length; j++) {
if(int1[j] == i) {
index.add(j);
}
}
return index;

}

/**
 * 启动程序，初始化值
 */
public void getPath() {
for(int i = 0 ; i < int1.length; i++) {
int startIndex = i;
StringBuffer path = new StringBuffer();
buildPath(startIndex, path);
}
}

/**
 * 防止回路 如 1-2-3-4-5-6-7-8-9-8
 * @param end
 * @param sb
 * @return
 */
public boolean check(int end, StringBuffer sb) {
String[] str = sb.toString().split("-");
for(int i =0; i < str.length; i++) {
if(!"".equals(str[i])) {
if(Integer.parseInt(str[i]) == end) {
return false;
}
}
}
return true;
}

/**
 * 递归算法
 * @param startIndex
 * @param sb
 */
public void buildPath(int startIndex,StringBuffer sb) {
int start = int1[startIndex];
int end = int2[startIndex];
if(check(end,sb) == false) {
System.out.println(sb.toString());
return;
}
if(sb.length() == 0) {
sb.append(start + "-" + end);
} else {
sb.append("-" + end);
}
List<Integer> list = getIndex(end);
if(list.size() == 0) {
System.out.println(sb.toString());
return;
}
for(int n = 0; n < list.size(); n++) {
int startindex = list.get(n);
buildPath(startindex, new StringBuffer(sb.toString()));
}
}

/**
 * test
 * @param args
 */
public static void main(String[] args) {
ItEyeQues it = new ItEyeQues();
it.getPath();
}
}
[/code]

Answer 8

/**
 * 
 */
package qian.iteye;import java.util.ArrayList;
import java.util.List;/**
 * <p>Objective:    </p>
 * <p>Description:    </p>
 * <p>Company: 天津正欣信息技术有限公司 </p>
 * <p>Copyright: Copyright (c) 2010-2012</p>
 * @version 1.0
 * @date: 2012-11-28 下午1:23:24
 * @author Administrator
 * @project Test1
 * @file_name ItEyeQues.java
 * @type_name ItEyeQues
 * @tags 
 */
public class ItEyeQues
{
private int[] int1 = {1,2,3,4,5,6,7,8,8,9,4,4,10};
private int[] int2 = {2,3,4,5,6,7,8,9,15,8,16,3,11};

/**
 *  传入一个终点，返回他对应的起点坐标
 * @param i
 * @return
 */
public List<Integer> getIndex(int i) {
List<Integer> index = new ArrayList<Integer>();
for(int j = 0; j < int1.length; j++) {
if(int1[j] == i) {
index.add(j);
}
}
return index;

}

/**
 * 启动程序，初始化值
 */
public void getPath() {
for(int i = 0 ; i < int1.length; i++) {
int startIndex = i;
StringBuffer path = new StringBuffer();
buildPath(startIndex, path);
}
}

/**
 * 防止回路 如 1-2-3-4-5-6-7-8-9-8
 * @param end
 * @param sb
 * @return
 */
public boolean check(int end, StringBuffer sb) {
String[] str = sb.toString().split("-");
for(int i =0; i < str.length; i++) {
if(!"".equals(str[i])) {
if(Integer.parseInt(str[i]) == end) {
return false;
}
}
}
return true;
}

/**
 * 递归算法
 * @param startIndex
 * @param sb
 */
public void buildPath(int startIndex,StringBuffer sb) {
int start = int1[startIndex];
int end = int2[startIndex];
if(check(end,sb) == false) {
System.out.println(sb.toString());
return;
}
if(sb.length() == 0) {
sb.append(start + "-" + end);
} else {
sb.append("-" + end);
}
List<Integer> list = getIndex(end);
if(list.size() == 0) {
System.out.println(sb.toString());
return;
}
for(int n = 0; n < list.size(); n++) {
int startindex = list.get(n);
buildPath(startindex, new StringBuffer(sb.toString()));
}
}

/**
 * test
 * @param args
 */
public static void main(String[] args) {
ItEyeQues it = new ItEyeQues();
it.getPath();
}
}