Patrick
BAN USERimport java.util.LinkedList;
import java.util.Queue;
public class GoGame {
public static boolean isSurrounded(int x, int y, char[][] chars) {
if (!isValidLocation(chars, x, y) || chars[x][y] == 'E') {
return false;
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
char sourceColoer = chars[x][y];
boolean[][] visited = new boolean[chars.length][chars[0].length];
while (!queue.isEmpty()) {
int[] location = queue.poll();
int curX = location[0], curY = location[1];
visited[curX][curY] = true;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] dir : dirs) {
int nextX = curX + dir[0], nextY = curY + dir[1];
if (isValidLocation(chars, nextX, nextY) && !visited[nextX][nextY]) {
if (chars[x][y] == 'E') {
return false;
} else if (chars[x][y] == sourceColoer) {
queue.offer(new int[]{nextX, nextY});
}
}
}
}
return true;
}
private static boolean isValidLocation(char[][] chars, int i, int j) {
if (i < 0 || j < 0 || i > chars.length - 1 || j > chars[0].length - 1) {
return false;
}
return true;
}
public static void main(String[] args){
char[][] board = new char[][]{
{'E','W','W','W','W','W','W'},
{'E','W','B','W','W','W','W'},
{'E','W','B','W','W','B','W'},
{'E','W','B','B','W','B','B'},
{'E','W','W','B','B','W','W'},
{'E','B','B','B','W','W','W'},
{'E','W','W','W','B','W','W'},
{'E','W','W','W','W','W','W'}
};
System.out.println(GoGame.isSurrounded(1,3,board));
System.out.println(GoGame.isSurrounded(4,4,board));
System.out.println(GoGame.isSurrounded(7,5,board));
System.out.println(GoGame.isSurrounded(4,6,board));
}
}
import java.util.*;
import java.util.List;
class Hotel {
Integer hotelId;
Integer parentHotelId;
int score;
public Hotel(Integer hotelId, Integer parentHotelId, int score) {
this.hotelId = hotelId;
this.parentHotelId = parentHotelId;
this.score = score;
}
}
public class TopKHotel {
private int[][] getTopKHotel(List<Hotel> hotels, int k) {
Map<Integer, Integer> curToParent = new HashMap<>();
Map<Integer, Integer> curToRoot = new HashMap<>();
for (Hotel h : hotels) {
curToParent.put(h.hotelId, h.parentHotelId);
}
Map<Integer, Integer> scoreMap = new HashMap<>();
for (Hotel h : hotels) {
Integer rootId = null;
if (curToRoot.containsKey(h.hotelId)) {
rootId = curToRoot.get(h.hotelId);
} else {
rootId = findRoot(h.hotelId, curToParent);
curToRoot.put(h.hotelId, rootId);
}
scoreMap.put(rootId, scoreMap.getOrDefault(rootId, 0) + h.score);
}
List<Map.Entry<Integer, Integer>> list = new ArrayList<>(scoreMap.entrySet());
Collections.sort(list, (a, b) -> b.getValue() - a.getValue());
int[][] ans = new int[k][2];
for (int i = 0; i < Math.min(k, list.size()); i++) {
ans[i][0] = list.get(i).getKey();
ans[i][1] = list.get(i).getValue();
}
return ans;
}
private int findRoot(int hotelId, Map<Integer, Integer> curToParent) {
if (curToParent.containsKey(hotelId) && curToParent.get(hotelId) != null) {
return findRoot(curToParent.get(hotelId), curToParent);
} else {
return hotelId;
}
}
public static void main(String[] args) {
List<Hotel> hotels = List.of(
new Hotel(3, 0, 14),
new Hotel(0, null, 10),
new Hotel(4, 0, 44),
new Hotel(6, null, 7),
new Hotel(10, 6, 13),
new Hotel(7, 6, 17),
new Hotel(2, null, 2),
new Hotel(14, 2, 9),
new Hotel(25, 14, 10),
new Hotel(12, 2, 10),
new Hotel(13, 0, 1),
new Hotel(14, 2, 9)
);
TopKHotel solution = new TopKHotel();
Arrays.asList(solution.getTopKHotel(hotels, 2)).forEach(
i -> {
System.out.println(String.format("hotel Id = %d, score = %d" , i[0], i[1]));
}
);
}
}
- Patrick August 06, 2022