766. Toeplitz Matrix

LeetCode easy original: C# #array #csharp #easy #hash-table #leetcode #matrix
Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.
LeetCode Static

Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.

Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые elementы.

Beispiel:

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.

C# Lösung

zugeordnet/original 
public class Solution {
    public bool IsToeplitzMatrix(int[][] matrix) {
        Dictionary<int, int> groups = new Dictionary<int, int>();
        for (int r = 0; r < matrix.Length; ++r) {
            for (int c = 0; c < matrix[0].Length; ++c) {
                if (!groups.ContainsKey(r - c))
                    groups[r - c] = matrix[r][c];
                else if (groups[r - c] != matrix[r][c])
                    return false;
            }
        }
        return true;
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsToeplitzMatrix(int[][] matrix) {
        unordered_map<int, int> groups = new unordered_map<int, int>();
        for (int r = 0; r < matrix.size(); ++r) {
            for (int c = 0; c < matrix[0].size(); ++c) {
                if (!groups.count(r - c))
                    groups[r - c] = matrix[r][c];
                else if (groups[r - c] != matrix[r][c])
                    return false;
            }
        }
        return true;
    }
}

Java Lösung

zugeordnet/original 
class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        Map<Integer, Integer> groups = new HashMap<>();
        for (int r = 0; r < matrix.length; ++r) {
            for (int c = 0; c < matrix[0].length; ++c) {
                if (!groups.containsKey(r - c))
                    groups.put(r - c, matrix[r][c]);
                else if (groups.get(r - c) != matrix[r][c])
                    return false;
            }
        }
        return true;
    }
}

JavaScript Lösung

zugeordnet/original 
class Solution {
    isToeplitzMatrix(matrix) {
        const groups = new Map();
        for (let r = 0; r < matrix.length; ++r) {
            for (let c = 0; c < matrix[0].length; ++c) {
                if (!groups.has(r - c))
                    groups.set(r - c, matrix[r][c]);
                else if (groups.get(r - c) !== matrix[r][c])
                    return false;
            }
        }
        return true;
    }
}

Python Lösung

zugeordnet/original 
class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        groups = {}
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if (r - c) not in groups:
                    groups[r - c] = matrix[r][c]
                elif groups[r - c] != matrix[r][c]:
                    return False
        return True

Go Lösung

zugeordnet/original 
func isToeplitzMatrix(matrix [][]int) bool {
    groups := make(map[int]int)
    for r := 0; r < len(matrix); r++ {
        for c := 0; c < len(matrix[0]); c++ {
            if _, ok := groups[r-c]; !ok {
                groups[r-c] = matrix[r][c]
            } else if groups[r-c] != matrix[r][c] {
                return false
            }
        }
    }
    return true
}

Algorithm

Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м

Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.

Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, return false. Если все elementы соответствуют, return true.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen
Es gibt noch keine aktiven Stellen.