정사각형 행렬이 주어지면 [][]와 함께 질서의 N 당신의 임무는 그것이 Toeplitz Matrix인지 확인하는 것입니다.
메모: 대각 상수 행렬이라고도 불리는 테플리츠 행렬은 모든 개별 하강 대각선의 요소가 왼쪽에서 오른쪽으로 동일한 행렬입니다. 모든 항목 mat[i][j]에 대해서는 mat[i-1][j-1] 또는 mat[i-2][j-2]와 동일합니다.
예:
입력: with[][] = [ [6 7 8]
[4 6 7]
[1 4 6] ]
산출: 예
설명: 주어진 행렬의 모든 대각선은 [6 6 6] [7 7] [8] [4 4] [1]입니다. 모든 요소가 동일하므로 모든 대각선에 대해 주어진 행렬은 Toeplitz Matrix입니다.입력: with[][] = [ [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성공하면 true를 반환합니다. - ~ 안에
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 속성을 위반한 것으로 간주되므로 즉시 중지할 수 있습니다. 불일치 없이 전체 행렬을 통과하면 모든 대각선은 일정합니다.
아래 주어진 단계를 따르십시오:
- 허락하다
n = mat.size()그리고m = mat[0].size(). - 반복
i1부터n - 1그리고 그 안에j1부터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) 공간
아이디어는 각 오른쪽 아래 대각선(행 인덱스에서 열 인덱스를 뺀 값)에 고유 식별자를 할당하고 해시 맵을 사용하여 해당 대각선에 표시된 첫 번째 값을 기록하는 것입니다. 전체 행렬을 스캔하면서 각 셀에 대해 이 키를 계산하고 저장된 값과 일치하는지 확인하거나 새 값인 경우 저장합니다. 단일 불일치로 인해 거짓으로 구제될 수 있습니다. 그렇지 않으면 결국에는 사실이라고 결론을 내리게 됩니다.
자바하는 동안 할
아래 주어진 단계를 따르십시오:
- 다음에서 행렬 차원(행 개수와 열 개수)을 결정합니다.
mat. - 빈 해시맵 만들기
mp각 대각선 키를 대표 값에 매핑합니다. - 모든 세포를 살펴보세요.
mat행 인덱스 기준i및 열 인덱스j. - 각 셀에 대해 빼서 대각선 키를 형성합니다.
j~에서i. - 만약에
mp이미 이 키를 보유하고 있으며 현재 요소를 저장된 값과 비교합니다. 다르면 즉시 false를 반환합니다. - 열쇠가 아직 들어가지 않은 경우
mp해당 키 아래에 현재 요소를 기록합니다. - 불일치 없이 순회를 완료하면 true를 반환합니다.
삽화:
아래 다이어그램은 이 아이디어를 더 잘 시각화합니다. 대각선 노란색을 고려하십시오. 이 대각선에 있는 모든 인덱스의 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