java在这个查找唯一路径数算法中我做错了什么?
问题陈述:https://pastebin.com/LzvZecyQ
我有2个输入文件来测试这个算法
第一: https://pastebin.com/BtsiZqqn
我得到了这个输出:
Case #1: 5
(这个不错)
第二: https://pastebin.com/fTbdbpnW
我得到了这个输出:
Case #1: 1
Case #2: 1
Case #3: 9
Case #4: 4
Case #5: 101
Case #6: 3.125
问题:所有案例都可以,但第6个案例是错误的
我正在使用以下代码:
public class DemoApplication {
private static final Logger LOGGER = Logger.getLogger("com.example.demo.DemoApplication");
private static final String TEMPLATE = "Case #{0}: {1}\r\n";
private static final String PLANET_START = "Galactica";
private static final String PLANET_END = "New Earth";
public static void main(String args[]) {
String inputFilePath = "testInput.txt";
String outputFilePath = "output.txt";
try (BufferedReader reader = Files.newBufferedReader(Paths.get(inputFilePath))) { //Create the reader with the file path of testInput.txt
try (BufferedWriter writer = Files.newBufferedWriter(Paths.get(outputFilePath))) { //Create the writer with the file path we want the output
String line = reader.readLine();//skip first row
int i = 0;//Counter of lines
Map<String, String[]> planets = null;
int caseNumber = 0;
while ((line = reader.readLine()) != null) {//Get the value of the current line
if (!isNumeric(line)) {
String[] split = line.split(":");//Split planet name and the paths
String planetName = split[0];
String[] connections = split[1].split(",");//Split different planets
planets.put(planetName, connections);
i++;
} else {
if (i > 0) {
writeFile(writer, planets, ++caseNumber);
}
planets = new HashMap<>();//reset
i = 0;//reset
}
}
writeFile(writer, planets, ++caseNumber);
}
} catch (IOException e) {
LOGGER.log(Level.WARNING, MessageFormat.format("IOException: {0}", e));
}
}
private static boolean isNumeric(String input) {
Pattern p = Pattern.compile("\\d+\\.?\\d*");
return p.matcher(input).matches();
}
private static int differentPaths(Map<String, String[]> planets, String planetName) {
if (planetName.equals(PLANET_END)) {//Last planed to arrive
return 1;
} else {
int accumulator = 0;
String[] paths = planets.get(planetName);
for (int i = 0; i < paths.length; i++) {
accumulator += differentPaths(planets, paths[i]);
}
return accumulator;
}
}
private static void writeFile(BufferedWriter writer, Map<String, String[]> planets, int caseNumber) throws IOException {
int result = differentPaths(planets, PLANET_START);//First planet from we start
writer.write(MessageFormat.format(TEMPLATE, caseNumber, result));//Write in file
}
}
我做错了什么?如果可能的话,我更愿意解释为什么这不适用于案例6,而不是给我解决方案。这是因为我正在努力学习算法
这个问题是tuenti挑战(https://contest.tuenti.net/Contest)的第二个问题。如果有人感兴趣,我想你仍然可以参加
提前谢谢
解决方案:
更改将输出强制转换结果写入字符串的方法,执行此操作时使用MessageFormat。格式不将点添加为十进制分隔符
private static void writeFile(BufferedWriter writer, Map<String, String[]> planets, int caseNumber) throws IOException {
int result = differentPaths(planets, PLANET_START);//First planet from we start
writer.write(MessageFormat.format(TEMPLATE, caseNumber, Integer.toString(result)));//Write in file
}
# 1 楼答案
你的算法似乎运行得很好,也许问题出在MessageFormat上。格式化方法,3.125可能是3125,点就是千分位