Сложность: easy
Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.
Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.
Пример:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.
👨💻 Алгоритм:
1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м
2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.
3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true.
😎 Решение:
class Solution {
func isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
var groups = [Int: Int]()
for r in 0..<matrix.count {
for c in 0..<matrix[0].count {
if groups[r - c] == nil {
groups[r - c] = matrix[r][c]
} else if groups[r - c] != matrix[r][c] {
return false
}
}
}
return true
}
}Ставь 👍 и забирай 📚 Базу знаний