Дадена е квадратна матрица заедно с [][] на реда п вашата задача е да проверите дали е Toeplitz Matrix.
Забележка: Матрицата на Тьоплиц - наричана още диагонално-постоянна матрица - е матрица, при която елементите на всеки отделен низходящ диагонал са еднакви отляво надясно. Еквивалентно за всеки запис mat[i][j] е същото като mat[i-1][j-1] или mat[i-2][j-2] и т.н.
Примери:
java string методи
вход: с [][] = [ [6 7 8]
[4 6 7]
[1 4 6] ]
Изход: да
Обяснение: Всички диагонали на дадената матрица са [6 6 6] [7 7] [8] [4 4] [1]. За всеки диагонал, тъй като всички елементи са еднакви, дадената матрица е матрица на Toeplitz.вход: с [][] = [ [6 3 8]
[4 9 7]
[1 4 6] ]
Изход: не
Обяснение: Първичните диагонални елементи на дадената матрица са [6 9 6]. Тъй като диагоналните елементи не са еднакви, дадената матрица не е матрица на Toeplitz.
[Очакван подход - 1] - Проверка на всеки диагонал - O(n * n) време и O(1) пространство
Идеята е да се премине през всеки наклонен надолу диагонал в матрицата, като се използва всеки елемент в първия ред и всеки елемент в първата колона като начална точка и се проверява дали всеки елемент по този диагонал съответства на стойността в началото му.
Следвайте дадените по-долу стъпки:
- Нека
n = mat.size()иm = mat[0].size(). - За всеки индекс на колона
iот0къмm - 1обажданеcheckDiagonal(mat 0 i); ако върне false, веднага връща false отisToeplitz. - За всеки ред индекс
iот0къмn - 1обажданеcheckDiagonal(mat i 0); ако върне false, веднага връща false отisToeplitz. - Ако всички обаждания до
checkDiagonalуспех връщане вярно. - в
checkDiagonal(mat x y)сравнявамmat[i][j]къмmat[x][y]за всекиi = x+1 j = y+1докатоi < n && j < m; връща false при първото несъответствие, в противен случай връща true след достигане на ръба.
По-долу е дадено изпълнение:
база данни за киселинни свойстваC++
#include
import java.util.*; class GfG { // function to check if diagonal elements are same static boolean checkDiagonal(List<List<Integer>> mat int x int y) { int n = mat.size() m = mat.get(0).size(); for(int i = x + 1 j = y + 1; i < n && j < m; i++ j++) { if(!mat.get(i).get(j).equals(mat.get(x).get(y))) return false; } return true; } // Function to check whether given // matrix is toeplitz matrix or not static boolean isToeplitz(List<List<Integer>> mat) { int n = mat.size() m = mat.get(0).size(); // check each descending diagonal starting from // first row and first column of the matrix for(int i = 0; i < m; i++) if(!checkDiagonal(mat 0 i)) return false; for(int i = 0; i < n; i++) if(!checkDiagonal(mat i 0)) return false; // if all diagonals are same return true return true; } public static void main(String[] args) { List<List<Integer>> mat = Arrays.asList( Arrays.asList(6 7 8) Arrays.asList(4 6 7) Arrays.asList(1 4 6) ); if(isToeplitz(mat)) { System.out.println('Yes'); } else { System.out.println('No'); } } }
# function to check if diagonal elements are same def checkDiagonal(mat x y): n m = len(mat) len(mat[0]) i j = x + 1 y + 1 while i < n and j < m: if mat[i][j] != mat[x][y]: return False i += 1 j += 1 return True # Function to check whether given # matrix is toeplitz matrix or not def isToeplitz(mat): n m = len(mat) len(mat[0]) # check each descending diagonal starting from # first row and first column of the matrix for i in range(m): if not checkDiagonal(mat 0 i): return False for i in range(n): if not checkDiagonal(mat i 0): return False # if all diagonals are same return true return True mat = [ [6 7 8] [4 6 7] [1 4 6] ] if isToeplitz(mat): print('Yes') else: print('No')
using System; using System.Collections.Generic; class GfG { // function to check if diagonal elements are same static bool checkDiagonal(List<List<int>> mat int x int y) { int n = mat.Count m = mat[0].Count; for(int i = x + 1 j = y + 1; i < n && j < m; i++ j++) { if(mat[i][j] != mat[x][y]) return false; } return true; } // Function to check whether given // matrix is toeplitz matrix or not static bool isToeplitz(List<List<int>> mat) { int n = mat.Count m = mat[0].Count; // check each descending diagonal starting from // first row and first column of the matrix for(int i = 0; i < m; i++) if(!checkDiagonal(mat 0 i)) return false; for(int i = 0; i < n; i++) if(!checkDiagonal(mat i 0)) return false; // if all diagonals are same return true return true; } static void Main() { var mat = new List<List<int>> { new List<int> {6 7 8} new List<int> {4 6 7} new List<int> {1 4 6} }; if(isToeplitz(mat)) { Console.WriteLine('Yes'); } else { Console.WriteLine('No'); } } }
// function to check if diagonal elements are same function checkDiagonal(mat x y) { let n = mat.length m = mat[0].length; for(let i = x + 1 j = y + 1; i < n && j < m; i++ j++) { if(mat[i][j] !== mat[x][y]) return false; } return true; } // Function to check whether given // matrix is toeplitz matrix or not function isToeplitz(mat) { let n = mat.length m = mat[0].length; // check each descending diagonal starting from // first row and first column of the matrix for(let i = 0; i < m; i++) if(!checkDiagonal(mat 0 i)) return false; for(let i = 0; i < n; i++) if(!checkDiagonal(mat i 0)) return false; // if all diagonals are same return true return true; } let mat = [ [6 7 8] [4 6 7] [1 4 6] ]; if(isToeplitz(mat)) { console.log('Yes'); } else { console.log('No'); }
Изход
Yes
[Очакван подход - 2] - Проверка по диагонал над елемента - O(n * n) време и O(1) пространство
Идеята е да се сканира всяка клетка от втория ред и втората колона нататък, като се сравнява всяка стойност с горния ляв съсед. Ако някой елемент се различава от този по диагонал над него, вие сте открили нарушение на свойството Toeplitz и можете да спрете незабавно; ако преминете през цялата матрица без несъответствие, всеки диагонал е постоянен.
подстриг на javascript
Следвайте дадените по-долу стъпки:
- Нека
n = mat.size()иm = mat[0].size(). - Итерация
iот 1 доn - 1и в рамките на товаjот 1 доm - 1. - Ако
mat[i][j] != mat[i - 1][j - 1]във всяка точка се върнетеfalse. - След като всички двойки са проверени без несъответствия, се връща
true.
По-долу е дадено изпълнение:
C++#include
import java.util.*; class GfG { // Function to check whether given // matrix is toeplitz matrix or not static boolean isToeplitz(List<List<Integer>> mat) { int n = mat.size() m = mat.get(0).size(); // check diagonally above element of // each element in the matrix for(int i = 1; i < n; i++) { for(int j = 1; j < m; j++) { if(mat.get(i).get(j) != mat.get(i - 1).get(j - 1)) return false; } } // if all diagonals are same return true return true; } public static void main(String[] args) { List<List<Integer>> mat = Arrays.asList( Arrays.asList(6 7 8) Arrays.asList(4 6 7) Arrays.asList(1 4 6) ); if(isToeplitz(mat)) { System.out.println('Yes'); } else { System.out.println('No'); } } }
# Function to check whether given # matrix is toeplitz matrix or not def isToeplitz(mat): n m = len(mat) len(mat[0]) # check diagonally above element of # each element in the matrix for i in range(1 n): for j in range(1 m): if mat[i][j] != mat[i - 1][j - 1]: return False # if all diagonals are same return true return True mat = [ [6 7 8] [4 6 7] [1 4 6] ] if isToeplitz(mat): print('Yes') else: print('No')
using System; using System.Collections.Generic; class GfG { // Function to check whether given // matrix is toeplitz matrix or not static bool isToeplitz(List<List<int>> mat) { int n = mat.Count m = mat[0].Count; // check diagonally above element of // each element in the matrix for(int i = 1; i < n; i++) { for(int j = 1; j < m; j++) { if(mat[i][j] != mat[i - 1][j - 1]) return false; } } // if all diagonals are same return true return true; } static void Main() { var mat = new List<List<int>> { new List<int> {6 7 8} new List<int> {4 6 7} new List<int> {1 4 6} }; if(isToeplitz(mat)) { Console.WriteLine('Yes'); } else { Console.WriteLine('No'); } } }
// Function to check whether given // matrix is toeplitz matrix or not function isToeplitz(mat) { let n = mat.length m = mat[0].length; // check diagonally above element of // each element in the matrix for(let i = 1; i < n; i++) { for(let j = 1; j < m; j++) { if(mat[i][j] !== mat[i - 1][j - 1]) return false; } } // if all diagonals are same return true return true; } let mat = [ [6 7 8] [4 6 7] [1 4 6] ]; if(isToeplitz(mat)) { console.log('Yes'); } else { console.log('No'); }
Изход
Yes
[Алтернативен подход] - Използване на хеширане - O(n * n) време и O(n) пространство
Идеята е да се присвои уникален идентификатор на всеки диагонал надолу вдясно (индексът на реда минус индексът на колоната) и да се използва хеш карта, за да се запише първата стойност, видяна за този диагонал. Докато сканирате цялата матрица, вие изчислявате този ключ за всяка клетка и или проверявате дали съответства на съхранената стойност, или ако е нова, запазете я. Едно несъответствие ви позволява да спасите с false; иначе заключаваш, че е вярно накрая.
Следвайте дадените по-долу стъпки:
- Определете размерите на матрицата (брой редове и брой колони) от
mat. - Създайте празна hashmap
mpза съпоставяне на всеки диагонален ключ с неговата представителна стойност. - Преминете през всяка клетка
matпо неговия индекс на редаiи индекс на колонаj. - За всяка клетка формирайте диагоналния ключ чрез изваждане
jотi. - Ако
mpвече държи този ключ сравнява текущия елемент със съхранената стойност; ако се различават, незабавно връща false. - Ако ключът все още не е вътре
mpзапишете текущия елемент под този ключ. - Ако завършите преминаването без никакво несъответствие, върнете true.
Илюстрация:
цяло число към низ в java
Диаграмата по-долу дава по-добра визуализация на тази идея. Помислете за диагонала, оцветен в жълто. Разликата между x-стойността и y-стойността на всеки индекс на този диагонал е 2 (2-0 3-1 4-2 5-3). Същото може да се наблюдава за всички диагонали на тялото.
За червения диагонал разликата е 3. За зеления диагонал разликата е 0. За оранжевия диагонал разликата е -2 и така нататък...
По-долу е дадено изпълнение:
C++#include
// JAVA program to check whether given matrix // is a Toeplitz matrix or not import java.util.*; class GFG { static boolean isToeplitz(int[][] matrix) { // row = number of rows // col = number of columns int row = matrix.length; int col = matrix[0].length; // HashMap to store keyvalue pairs HashMap<Integer Integer> map = new HashMap<Integer Integer>(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int key = i - j; // if key value exists in the hashmap if (map.containsKey(key)) { // we check whether the current value // stored in this key matches to element // at current index or not. If not // return false if (map.get(key) != matrix[i][j]) return false; } // else we put keyvalue pair in hashmap else { map.put(i - j matrix[i][j]); } } } return true; } // Driver Code public static void main(String[] args) { int[][] matrix = { { 12 23 -32 } { -20 12 23 } { 56 -20 12 } { 38 56 -20 } }; // Function call String result = (isToeplitz(matrix)) ? 'Yes' : 'No'; System.out.println(result); } }
# Python3 program to check whether given matrix # is a Toeplitz matrix or not def isToeplitz(matrix): # row = number of rows # col = number of columns row = len(matrix) col = len(matrix[0]) # dictionary to store keyvalue pairs map = {} for i in range(row): for j in range(col): key = i-j # if key value exists in the map if (key in map): # we check whether the current value stored # in this key matches to element at current # index or not. If not return false if (map[key] != matrix[i][j]): return False # else we put keyvalue pair in map else: map[key] = matrix[i][j] return True # Driver Code if __name__ == '__main__': matrix = [[12 23 -32] [-20 12 23] [56 -20 12] [38 56 -20]] # Function call if (isToeplitz(matrix)): print('Yes') else: print('No')
using System; using System.Collections.Generic; class GfG { // Function to check whether given // matrix is toeplitz matrix or not static bool isToeplitz(List<List<int>> mat) { int n = mat.Count m = mat[0].Count; // HashMap to store keyvalue pairs Dictionary<intint> mp = new Dictionary<intint>(); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int key = i - j; // If key value exists in the hashmap if (mp.ContainsKey(key)) { // check if the value is same // as the current element if (mp[key] != mat[i][j]) return false; } // Else we put keyvalue pair in hashmap else { mp[i - j] = mat[i][j]; } } } return true; } static void Main() { var mat = new List<List<int>> { new List<int> {6 7 8} new List<int> {4 6 7} new List<int> {1 4 6} }; if(isToeplitz(mat)) { Console.WriteLine('Yes'); } else { Console.WriteLine('No'); } } }
// Function to check whether given // matrix is toeplitz matrix or not function isToeplitz(mat) { let n = mat.length m = mat[0].length; // HashMap to store keyvalue pairs const mp = new Map(); for(let i = 0; i < n; i++) { for(let j = 0; j < m; j++) { let key = i - j; // If key value exists in the hashmap if (mp.has(key)) { // check if the value is same // as the current element if (mp.get(key) !== mat[i][j]) return false; } // Else we put keyvalue pair in hashmap else { mp.set(i - j mat[i][j]); } } } return true; } let mat = [ [6 7 8] [4 6 7] [1 4 6] ]; if(isToeplitz(mat)) { console.log('Yes'); } else { console.log('No'); }
Изход
Yes