Java | LeetCode
Задача: 782. Transform to Chessboard
Сложность: hard
Дана бинарная сетка размером n x n. В каждом ходе можно поменять местами любые две строки или любые два столбца.
Верните минимальное количество ходов, чтобы преобразовать сетку в шахматную доску. Если задача невыполнима, верните -1.
Шахматная доска — это доска, на которой ни один 0 и ни одна 1 не соприкасаются друг с другом по вертикали и горизонтали.
Пример:
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation: One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.
👨💻 Алгоритм:
1⃣Для каждого набора строк (и столбцов соответственно) убедитесь, что существует только 2 вида линий в правильных количествах, которые являются противоположностями друг друга.
2⃣Затем для каждой возможной идеальной трансформации этой линии найдите минимальное количество перестановок, чтобы преобразовать эту линию в её идеальную и добавьте это к ответу. Например, [0, 1, 1, 1, 0, 0] имеет два идеала [0, 1, 0, 1, 0, 1] или [1, 0, 1, 0, 1, 0]; но [0, 1, 1, 1, 0] имеет только один идеал [1, 0, 1, 0, 1].
3⃣В Java мы используем целые числа для представления строк как двоичных чисел. Мы проверяем количество различий с [1, 0, 1, 0, 1, 0, ...] с помощью побитового исключающего ИЛИ с 0b010101010101.....01 = 0x55555555. Чтобы убедиться, что мы не добавляем излишне большие элементы.
😎 Решение:
import java.util.*;
class Solution {
public int movesToChessboard(int[][] board) {
int N = board.length;
int ans = 0;
for (Map<int[], Integer> count : Arrays.asList(
getCount(board),
getCount(transpose(board))
)) {
if (count.size() != 2 || !count.values().containsAll(Arrays.asList(N / 2, (N + 1) / 2))) {
return -1;
}
Iterator<int[]> iterator = count.keySet().iterator();
int[] line1 = iterator.next();
int[] line2 = iterator.next();
if (!allOpposite(line1, line2)) {
return -1;
}
List<Integer> starts = N % 2 == 0 ? Arrays.asList(0, 1) : Arrays.asList(line1[0] * 2 > N ? 1 : 0);
int minSwaps = Integer.MAX_VALUE;
for (int start : starts) {
int swaps = 0;
for (int i = 0; i < N; i++) {
if ((line1[i] - i % 2) % 2 != 0) {
swaps++;
}
}
minSwaps = Math.min(minSwaps, swaps / 2);
}
ans += minSwaps;
}
return ans;
}
private Map<int[], Integer> getCount(int[][] board) {
Map<int[], Integer> count = new HashMap<>();
for (int[] row : board) {
count.put(row, count.getOrDefault(row, 0) + 1);
}
return count;
}
private int[][] transpose(int[][] board) {
int N = board.length;
int[][] transposed = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
transposed[j][i] = board[i][j];
}
}
return transposed;
}
private boolean allOpposite(int[] line1, int[] line2) {
for (int i = 0; i < line1.length; i++) {
if ((line1[i] ^ line2[i]) == 0) {
return false;
}
}
return true;
}
}
Ставь 👍 и забирай 📚 Базу знаний
2 · 420 ·