🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1253. Reconstruct a 2-Row Binary Matrix
Сложность: medium
Даны следующие сведения о матрице с n столбцами и 2 строками: Матрица является двоичной, то есть каждый элемент матрицы может быть 0 или 1. Сумма элементов 0-й (верхней) строки задана как upper. Сумма элементов 1-й (нижней) строки задана как lower.
Сумма элементов i-го столбца (индексированного 0) - colsum[i], где colsum - целочисленный массив длины n. Ваша задача - восстановить матрицу с upper, lower и colsum. Вернуть ее в виде двумерного целочисленного массива. Если существует более одного правильного решения, будет принято любое из них. Если правильного решения не существует, верните пустой двумерный массив.
Пример:
Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
👨💻 Алгоритм:
1⃣Инициализируйте две строки матрицы длины n с нулями.
2⃣Пройдите по массиву colsum и распределите значения 2 по обеим строкам, уменьшая upper и lower.
Пройдите по массиву colsum и распределите значения 1 по строкам, уменьшая соответствующие upper или lower.
3⃣Проверьте, что остатки upper и lower равны нулю.
Если все шаги выполнены успешно, верните восстановленную матрицу, иначе верните пустую матрицу.
😎 Решение:
class Solution {
fun reconstructMatrix(upper: Int, lower: Int, colsum: IntArray): List
• > {
var upper = upper
var lower = lower
val n = colsum.size
val top = IntArray(n)
val bottom = IntArray(n)
for (i in colsum.indices) {
if (colsum[i] == 2) {
if (upper > 0 && lower > 0) {
top[i] = 1
bottom[i] = 1
upper--
lower--
} else {
return emptyList()
}
}
}
for (i in colsum.indices) {
if (colsum[i] == 1) {
if (upper > lower) {
if (upper > 0) {
top[i] = 1
upper--
} else {
return emptyList()
}
} else {
if (lower > 0) {
bottom[i] = 1
lower--
} else {
return emptyList()
}
}
}
}
if (upper == 0 && lower == 0) {
return listOf(top.toList(), bottom.toList())
} else {
return emptyList()
}
}
}
Ставь 👍 и забирай 📚 Базу знаний
