PriorityQueue Comparator Seltsames Verhalten, wenn die Sortierreihenfolge aus HashMap abgerufen wird ⇐ Java

[Anonymous]

Während der Arbeit in Leetcode 675 bin ich auf ein seltsames Verhalten mit PriorityQueue vergleicher gestoßen, das ich nicht erklären kann. Interessierte Parteien können es auf Leetcode ausführlich lesen. Die Frage besteht darin, die minimale Anzahl von Schritten zu finden, die alle Baumzellen in aufsteigender Reihenfolge der Baumhöhen besuchen müssen. Dann berechne ich den minimalen Abstand von jedem Baum zu seinem nächsten, indem ich eine A* -Suche unter Verwendung der heuristischen Funktion: Entfernung von Quelle + Manhattan -Entfernung vom Ziel < /code> < /p>
Die minimale Anzahl von Schritten zum Abschneiden aller Bäume beträgt die Summe aller A* -Diente. class = "Lang-Java PrettyPrint-Override">

Code: Select all

class Solution {
private final int[][] dx = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int cutOffTree(List forest) {
int[] curr = new int[] {0, 0};
int dist = 0;

for (int[] next : getTreesSortedByHeight(forest)) {
int d = minDist(forest, curr, next);
if (d < 0) {
return -1;
}
curr = next;
dist += d;
}

return dist;
}

private List getTreesSortedByHeight(List forest) {
List trees = new ArrayList();
for (int row = 0; row < forest.size(); row++) {
for (int col = 0; col < forest.get(0).size(); col++) {
if (forest.get(row).get(col) > 1) {
trees.add(new int[] {row, col});
}
}
}
trees.sort(Comparator.comparingInt(a -> forest.get(a[0]).get(a[1])));
return trees;
}

int minDist(List forest, int[] start, int[] goal) {
int m = forest.size();
int n = forest.get(0).size();
Map costs = new HashMap();
costs.put(start[0] * n + start[1], manhattanDist(start[0], start[1], goal));
// GOTCHA: Fetching the distance from the cost map using the coordinates doesn't work!
Queue heap = new PriorityQueue(Comparator.comparingInt(a -> a[0]));
heap.offer(new int[] {0, 0, start[0], start[1]}); // [cost, distance, row, column]

while (!heap.isEmpty()) {
int[] curr = heap.poll();
int dist = curr[1];
int row = curr[2];
int col = curr[3];

if (row == goal[0] && col == goal[1]) {
return dist;
}
for (int[] d : dx) {
int r = row + d[0];
int c = col + d[1];
if (r >= 0 && r < m && c >= 0 && c < n && forest.get(r).get(c) > 0) {
int cost = dist + 1 + manhattanDist(r, c, goal);
if (cost < costs.getOrDefault(r * n + c, Integer.MAX_VALUE)) {
costs.put(r * n + c, cost);
heap.offer(new int[] {cost, dist + 1, r, c});
}
}
}
}
return -1;
}

private int manhattanDist(int row, int col, int[] goal) {
return Math.abs(goal[0] - row) + Math.abs(goal[1] - col);
}
}

Beachten Sie, dass jeder Heap -Eintrag die heuristischen Kosten enthält. Logischerweise ist dies unnötig , da der Eintrag auch die Zellkoordinaten (Zeile und Spalte) enthält, in welchem ​​ wir die Entfernung von der Kosten wie folgt abrufen können:

Queue heap = new PriorityQueue(Comparator.comparingInt(a -> costs.get(a[1] * n + a[2]);
< /code>

In Abwesenheit der Kosten besteht der Heap -Eintrag aus [Entfernung, Zeile, Spalte]. < /li>
< /ul>
, aber dieses funktioniert nicht < /strong> und fällt nicht für einen der Testfälle. Der Testfall ist riesig, also sehe ich keinen Sinn, ihn hier zu fügen, da es unwahrscheinlich ist, dass jemand die Zeit hat, ihn zu debuggen.>