阿里笔试第二题：单边双边车辆优化问题

只过了25%的路过

什么岗呀

没有在阿里的平台测试（没做出来），只是自己后来在本机测试了以下的例子（好使），并不代表其它 例子都好使，给楼主看一下，嘿嘿： 链接：https://www.nowcoder.com/discuss/34905?type=0&order=0&pos=32&page=1 输入: 线路数据，大于2行 每行由6列组成 线路ID;出发分拨中心名称;出发省名称;到达分拨中心名称;到达省名称;车型; 输出: 按照三个优化规则输出的单边车优化结果 输入范例: 350410;嘉兴中心;浙江省;西安中心;陕西省;9.6m; 350424;西安中心;陕西省;嘉兴中心;浙江省;9.6m; 350428;嘉兴中心;浙江省;长沙中心;湖南省;17.5m; 350432;长沙中心;湖南省;武汉中心;湖北省;17.5m; 350448;武汉中心;湖北省;嘉兴中心;浙江省;17.5m; 350476;嘉兴中心;浙江省;潍坊中心;山东省;9.6m; 350479;潍坊中心;山东省;嘉兴中心;浙江省;17.5m; 350481;嘉兴中心;浙江省;成都中心;四川省;9.6m; 输出范例: rule1:350410+350424 rule2:350428+350432+350448 =============================================================================== 思路就是一个一个规则的匹配（最笨的方法了吧），因为规则有优先级，所以就用了好几次的for循环来匹配，匹配成功一个就把匹配的车次标记，并添加到结果中。 import java.util.*; public class Main3 { static boolean[] marked = null; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); List<UnilateralLine> lineList = new ArrayList<UnilateralLine>(); while (scanner.hasNextLine()) { String[] options = scanner.nextLine().split(";"); if (options.length < 5) { break; } lineList.add(new UnilateralLine(options[0], options[1], options[2], options[3], options[4], options[5])); } scanner.close(); // wirte your code here marked = new boolean[lineList.size()];// 标记已经优化的车号 List<String> result = calculateUnilateral(lineList); for (String str : result) { System.out.println(str); } } public static List<String> calculateUnilateral(List<UnilateralLine> lineList) { // 优化的规则参照以上，并且优先级依次降低，合并的时候需要考虑车型（分为17.5m和9.6m两种）： // 1、相同车型才能进行合并 // 2、两辆同方向的9.6m可以与一辆17.5m的对开车型合并优化 List<String> result = new ArrayList<String>(); // 求出满足第一条规则的车次 // A-B单边车，B-A单边车 优化方案：将A-B和B-A的两辆单边车合并为双边； for(int i = 0; i < lineList.size(); i ++){ if(marked[i]) continue; UnilateralLine ul1 = lineList.get(i); for(int j = 1; j < lineList.size(); j ++){ UnilateralLine ul2 = lineList.get(j); if(! marked[j] && ul1.getSCen().equals(ul2.getECen()) && ul1.getECen().equals(ul2.getSCen()) && ul1.getTType().equals(ul2.getTType())){ result.add("rule1:" + ul1.getId() + "+" + ul2.getId()); marked[i] = true; marked[j] = true; } } } // 求出满足第二条规则的车次 // A-B单边车，B-C单边车，C-A单边车 优化方案：将A-B、B-C、C-A的三辆单边车优化为一辆环形往返车； for(int i = 0; i < lineList.size(); i ++){ if(marked[i]) continue; UnilateralLine ul1 = lineList.get(i); int count = 0; if(ul1.getTType().equals("17.5m"))count++; for(int j = 1; j < lineList.size(); j ++){ if(marked[j]) continue; UnilateralLine ul2 = lineList.get(j); if(ul2.getTType().equals("17.5m"))count++; if(ul1.getECen().equals(ul2.getSCen())){ for(int k = 2; k < lineList.size(); k ++){ UnilateralLine ul3 = lineList.get(k); if(ul3.getTType().equals("17.5m")) count++; // count为型号为17.5m车的数量，如果count的值可能为0,1,2,3 // 当count的值为2时，不满足车辆合并规则 // 2、两辆同方向的9.6m可以与一辆17.5m的对开车型合并优化 if(!marked[k] && ul2.getECen().equals(ul3.getSCen()) && ul3.getECen().equals(ul1.getSCen()) && count != 2){ result.add("rule2:" + ul1.getId() + "+" + ul2.getId() + "+" + ul3.getId()); marked[i] = true; marked[j] = true; marked[k] = true; } } } } } // 求出满足第三条规则的车次 // A-B单边车，C-A单边车，B、C同省 优化方案：当B、C同省，将A-B、C-A两辆单边优化为一辆环形往返 for(int i = 0; i < lineList.size(); i ++){ UnilateralLine ul1 = lineList.get(i); if(marked[i]) continue; for(int j = 1; j < lineList.size(); j ++){ UnilateralLine ul2 = lineList.get(j); if(!marked[j] && ul1.getSCen().equals(ul2.getECen()) && ul1.getEPro().equals(ul2.getSPro()) && ul1.getTType().equals(ul2.getTType())){ result.add("rule3:" + ul1.getId() + "+" + ul2.getId()); marked[i] = true; marked[j] = true; } } } return result; } public static class UnilateralLine { private String id; private String sCen;// 出发分拨 private String sPro;// 出发省 private String eCen;// 到达分拨 private String ePro;// 到达省 // 9.6m/17.5m private String tType;// 车型 public UnilateralLine(String id, String sCen, String sPro, String eCen, String ePro, String tType) { this.id = id; this.sCen = sCen; this.sPro = sPro; this.eCen = eCen; this.ePro = ePro; this.tType = tType; } public String getId() { return id; } public void setId(String id) { this.id = id; } public String getSCen() { return sCen; } public void setSCen(String ePro) { this.ePro = ePro; } public String getSPro() { return sPro; } public void setSPro(String sPro) { this.sPro = sPro; } public String getECen() { return eCen; } public void setECen(String eCen) { this.eCen = eCen; } public String getEPro() { return ePro; } public void setEPro(String ePro) { this.ePro = ePro; } public String getTType() { return tType; } public void setTType(String tType) { this.tType = tType; } } }

估计都没看第二题