JAVA代码—算法基础：重建行程-白红宇

JAVA代码—算法基础：重建行程

阅读量：4041 次

发布时间：2019-05-24

本文共 2970 字，大约阅读时间需要 9 分钟。

重建行程

问题描述：

给出一组代表从出发到到达的机票（From，To），重新建立形成顺序。

所有的机票都是属于一个从JFK出发的，所以行程必须从JFK开始。

注意：如果有多个有效的行程，你应该返回的行程，具有最小的词汇顺序当读为一个字符串。

例如：行程[“JFK”, “LGA”] 比行程 [“JFK”, “LGB”]具有最小的字典词汇顺序。

所有机场由三个大写字母（IATA代码）表示。

你可以假设所有的票至少有一个有效的行程表。

例子 1:

tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]

返回： [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

例子 2:

tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]

返回： [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”].

另外一种可能的结构： [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. 但是它的字典词汇顺序不正确。

算法设计：

package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.HashMap;import java.util.List;public class ReconstructionItinerary {    /*     * 算法设计：     * 输入参数：表示行程的二维字符串数组     * 返回值：用List结构表示的行程     *      * */    public List
   
     findItinerary(String[][] tickets) {        ArrayList
    
      result = new ArrayList
     
      ();        if (tickets == null || tickets.length == 0) {            return result;        }        int total = tickets.length + 1;        HashMap
      
       > map = new HashMap
       
        >();        for (int i = 0; i < tickets.length; i++) {            if (map.containsKey(tickets[i][0])) {                ArrayList
        
          tmp = map.get(tickets[i][0]); listAdd(tickets[i][1], tmp); } else { ArrayList
         
           tmp = new ArrayList
          
           (); tmp.add(tickets[i][1]); map.put(tickets[i][0], tmp); } } result.add("JFK"); itineraryHelper("JFK", map, result, total, 1); return result; } public boolean itineraryHelper(String current, HashMap
           
            > map, ArrayList
            
              result, int total, int num) { if (num >= total) { return true; } if (!map.containsKey(current) || map.get(current).size() == 0) { return false; } ArrayList
             
               curList = map.get(current); int i = 0; while (i < curList.size()) { String next = curList.remove(i); result.add(next); // if (itineraryHelper(next, map, result, total, num + 1)) { return true; } result.remove(result.size() - 1); listAdd(next, curList); i++; } return false; } public void listAdd(String value, ArrayList
              
                list){ if(list.size() == 0){ list.add(value); return; } else{ int i = 0; while(i < list.size()){ if(value.compareTo(list.get(i)) <= 0){ list.add(i, value); return; } i++; } list.add(value); return; } }// public void listAdd(String value, ArrayList
               
                 list) { // if (list.size() == 0) { // list.add(value);// return;// } else { // int i = 0;// while (i < list.size()) { // if (value.compareTo(list.get(i)) <= 0) { // list.add(i, value);// return;// }// i++;// }// list.add(value);// return;// }// } public static void main(String[] args) { // TODO Auto-generated method stub //String[][] ticketsDemo= { {"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}}; String[][] ticketsDemo= { { "JFK","SFO"}, { "JFK","ATL"}, { "SFO","ATL"}, { "ATL","JFK"},{ "ATL","SFO"}}; ReconstructionItinerary reItinerary=new ReconstructionItinerary(); List
                
                  listItinerary=reItinerary.findItinerary(ticketsDemo); System.out.println(listItinerary); }}