Java | LeetCode
Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium
Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.
Пример:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
👨💻 Алгоритм:
1⃣Представить каждую строку и столбец как узлы в графе.
2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.
3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности.
😎 Решение:
import java.util.*;
class Solution {
public int removeStones(int[][] stones) {
Map<Integer, Integer> parent = new HashMap<>();
int find(int x) {
if (!parent.containsKey(x)) {
parent.put(x, x);
}
if (parent.get(x) != x) {
parent.put(x, find(parent.get(x)));
}
return parent.get(x);
}
void union(int x, int y) {
parent.put(find(x), find(y));
}
for (int[] stone : stones) {
union(stone[0], ~stone[1]);
}
Set<Integer> uniqueRoots = new HashSet<>();
for (int key : parent.keySet()) {
uniqueRoots.add(find(key));
}
return stones.length - uniqueRoots.size();
}
}
Ставь 👍 и забирай 📚 Базу знаний
2 · 693 ·