时间戳

首页 > 解决方案 > Java从向量中选择最佳匹配元素

java - Java从向量中选择最佳匹配元素

问题描述

我的任务是找到到达目的地的最简单方法。
我找到了所有路径并存储在向量中，例如： 

1. R R R R P P L L P P   
2. R R R R P P R R R R P P L L L L L L   
3. R R R R P P R R R R P P P P L L L L L L P P

其中 R - 右，L - 左，P - 直。
此外，我有遵循路径的优先级： 

rightHanded: straight, right, left   
leftHanded: straight, left, right

我想按优先顺序走到底。
例如，使用上面的右撇子路径示例

R -> R -> R -> R -> P -> P -> (1)R -> R -> R -> R -> P -> P -> (2) P -> end I find the shortest path

ad.1 我看到最好的是 2 和 3，因为我有 R
ad.2 我再次选择了 R 而不是 L，我有最后一条路径，它是最简单的

我不知道怎么写那个程序。

标签： javavector

解决方案

测试了重复路径、开头有另一个路径作为子路径的路径等情况。

public static void main(String[] args) {
    Map<Integer, List<Character>> paths = new LinkedHashMap<>();
    paths.put(1, Arrays.asList('R', 'R', 'R', 'R', 'P', 'P', 'L', 'L', 'P', 'P'));
    paths.put(2, Arrays.asList('R', 'R', 'R', 'R', 'P', 'P', 'R', 'R', 'R', 'R', 'P', 'P', 'L', 'L', 'L', 'L', 'L', 'L'));
    paths.put(3, Arrays.asList('R', 'R', 'R', 'R', 'P', 'P', 'R', 'R', 'R', 'R', 'P', 'P', 'P', 'P', 'L', 'L', 'L', 'L', 'L', 'L', 'P', 'P'));

    System.out.println("Path " + bestPath(paths, DrivingDirection.RIGHT_HANDED) + " is the best for " + DrivingDirection.RIGHT_HANDED);
    System.out.println("Path " + bestPath(paths, DrivingDirection.LEFT_HANDED) + " is the best for " + DrivingDirection.LEFT_HANDED);
}

private static List<Character> getTurnPreferences(DrivingDirection drivingDirection) {
    return drivingDirection == DrivingDirection.RIGHT_HANDED
            ? Arrays.asList('P', 'R', 'L')
            : Arrays.asList('P', 'L', 'R');
}

private enum DrivingDirection {
    RIGHT_HANDED,
    LEFT_HANDED
}

private static int bestPath(Map<Integer, List<Character>> paths, DrivingDirection drivingDirection) {
    List<Character> turnPreference = getTurnPreferences(drivingDirection);
    final AtomicInteger i = new AtomicInteger(0);
    while (paths.size() > 1) {
        Map<Integer, List<Character>> tempMap = eliminateUnpreferredPaths(paths, turnPreference, i);
        if (tempMap.size() == 0) return getShortestPath(paths).getKey(); // when all paths are bad
        i.incrementAndGet();
        Optional<Map.Entry<Integer, List<Character>>> pathWithNoMoreDirections = getPathWithNoMoreDirectionsLeft(i, tempMap);
        if (pathWithNoMoreDirections.isPresent()) return pathWithNoMoreDirections.get().getKey();
        paths = tempMap;
    }
    return paths.keySet().iterator().next();
}

private static Optional<Map.Entry<Integer, List<Character>>> getPathWithNoMoreDirectionsLeft(
        AtomicInteger i, Map<Integer, List<Character>> tempMap) {
    return tempMap.entrySet().stream()
            .filter(e -> e.getValue().size() == i.get())
            .findFirst();
}

private static Map.Entry<Integer, List<Character>> getShortestPath(Map<Integer, List<Character>> paths) {
    return paths.entrySet().stream().min(Comparator.comparingInt(e -> e.getValue().size())).get();
}

private static Map<Integer, List<Character>> eliminateUnpreferredPaths(
        Map<Integer, List<Character>> paths, List<Character> turnPreference, AtomicInteger i) {
    Map<Integer, List<Character>> tempMap = null;
    for (int j = 0; j < turnPreference.size(); j++) {
        final int finalJ = j;
        tempMap = paths.entrySet()
                .stream()
                .filter(e -> e.getValue().size() > i.get() && e.getValue().get(i.get()).equals(turnPreference.get(finalJ)))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
        if (tempMap.size() > 0) break;
    }
    return tempMap;
}

输出

Path 3 is the best for RIGHT_HANDED
Path 1 is the best for LEFT_HANDED

推荐阅读