562. Longest Line of Consecutive One in Matrix
선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.
Дана бинарная матрица размера m x n. Вернуть длину самой длинной последовательной линии из единиц в матрице.
Линия может быть горизонтальной, вертикальной, диагональной или анти-диагональной.
예제:
Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3
C# 해법
매칭됨/원본public class Solution {
public int LongestLine(int[][] mat) {
if (mat == null || mat.Length == 0 || mat[0].Length == 0) {
return 0;
}
int m = mat.Length;
int n = mat[0].Length;
int maxLength = 0;
int[,] horizontal = new int[m, n];
int[,] vertical = new int[m, n];
int[,] diagonal = new int[m, n];
int[,] antiDiagonal = new int[m, n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
horizontal[i, j] = (j > 0 ? horizontal[i, j-1] : 0) + 1;
vertical[i, j] = (i > 0 ? vertical[i-1, j] : 0) + 1;
diagonal[i, j] = (i > 0 && j > 0 ? diagonal[i-1, j-1] : 0) + 1;
antiDiagonal[i, j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1, j+1] : 0) + 1;
maxLength = Math.Max(maxLength, horizontal[i, j]);
maxLength = Math.Max(maxLength, vertical[i, j]);
maxLength = Math.Max(maxLength, diagonal[i, j]);
maxLength = Math.Max(maxLength, antiDiagonal[i, j]);
}
}
}
return maxLength;
}
}C++ 해법
자동 초안, 제출 전 검토#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 int LongestLine(int[][] mat) {
if (mat == null || mat.size() == 0 || mat[0].size() == 0) {
return 0;
}
int m = mat.size();
int n = mat[0].size();
int maxLength = 0;
int[,] horizontal = new int[m, n];
int[,] vertical = new int[m, n];
int[,] diagonal = new int[m, n];
int[,] antiDiagonal = new int[m, n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
horizontal[i, j] = (j > 0 ? horizontal[i, j-1] : 0) + 1;
vertical[i, j] = (i > 0 ? vertical[i-1, j] : 0) + 1;
diagonal[i, j] = (i > 0 && j > 0 ? diagonal[i-1, j-1] : 0) + 1;
antiDiagonal[i, j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1, j+1] : 0) + 1;
maxLength = max(maxLength, horizontal[i, j]);
maxLength = max(maxLength, vertical[i, j]);
maxLength = max(maxLength, diagonal[i, j]);
maxLength = max(maxLength, antiDiagonal[i, j]);
}
}
}
return maxLength;
}
}Java 해법
매칭됨/원본public class Solution {
public int longestLine(int[][] mat) {
if (mat == null || mat.length == 0 || mat[0].length == 0) {
return 0;
}
int m = mat.length;
int n = mat[0].length;
int maxLength = 0;
int[][] horizontal = new int[m][n];
int[][] vertical = new int[m][n];
int[][] diagonal = new int[m][n];
int[][] antiDiagonal = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
horizontal[i][j] = (j > 0 ? horizontal[i][j-1] : 0) + 1;
vertical[i][j] = (i > 0 ? vertical[i-1][j] : 0) + 1;
diagonal[i][j] = (i > 0 && j > 0 ? diagonal[i-1][j-1] : 0) + 1;
antiDiagonal[i][j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1][j+1] : 0) + 1;
maxLength = Math.max(maxLength, horizontal[i][j]);
maxLength = Math.max(maxLength, vertical[i][j]);
maxLength = Math.max(maxLength, diagonal[i][j]);
maxLength = Math.max(maxLength, antiDiagonal[i][j]);
}
}
}
return maxLength;
}
}JavaScript 해법
매칭됨/원본class Solution {
longestLine(mat) {
if (!mat || !mat.length || !mat[0].length) {
return 0;
}
const m = mat.length;
const n = mat[0].length;
let maxLength = 0;
const horizontal = Array.from({ length: m }, () => Array(n).fill(0));
const vertical = Array.from({ length: m }, () => Array(n).fill(0));
const diagonal = Array.from({ length: m }, () => Array(n).fill(0));
const antiDiagonal = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] === 1) {
horizontal[i][j] = (j > 0 ? horizontal[i][j-1] : 0) + 1;
vertical[i][j] = (i > 0 ? vertical[i-1][j] : 0) + 1;
diagonal[i][j] = (i > 0 && j > 0 ? diagonal[i-1][j-1] : 0) + 1;
antiDiagonal[i][j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1][j+1] : 0) + 1;
maxLength = Math.max(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j]);
}
}
}
return maxLength;
}
}Python 해법
매칭됨/원본class Solution:
def longestLine(self, mat: List[List[int]]) -> int:
if not mat or not mat[0]:
return 0
m, n = len(mat), len(mat[0])
max_length = 0
horizontal = [[0] * n for _ in range(m)]
vertical = [[0] * n for _ in range(m)]
diagonal = [[0] * n for _ in range(m)]
anti_diagonal = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if mat[i][j] == 1:
horizontal[i][j] = (horizontal[i][j-1] if j > 0 else 0) + 1
vertical[i][j] = (vertical[i-1][j] if i > 0 else 0) + 1
diagonal[i][j] = (diagonal[i-1][j-1] if i > 0 and j > 0 else 0) + 1
anti_diagonal[i][j] = (anti_diagonal[i-1][j+1] if i > 0 and j < n-1 else 0) + 1
max_length = max(max_length, horizontal[i][j], vertical[i][j], diagonal[i][j], anti_diagonal[i][j])
return max_lengthGo 해법
매칭됨/원본func longestLine(mat [][]int) int {
if len(mat) == 0 || len(mat[0]) == 0 {
return 0
}
m, n := len(mat), len(mat[0])
maxLength := 0
horizontal := make([][]int, m)
vertical := make([][]int, m)
diagonal := make([][]int, m)
antiDiagonal := make([][]int, m)
for i := range mat {
horizontal[i] = make([]int, n)
vertical[i] = make([]int, n)
diagonal[i] = make([]int, n)
antiDiagonal[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if mat[i][j] == 1 {
horizontal[i][j] = 1 + if j > 0 { horizontal[i][j-1] } else { 0 }
vertical[i][j] = 1 + if i > 0 { vertical[i-1][j] } else { 0 }
diagonal[i][j] = 1 + if i > 0 && j > 0 { diagonal[i-1][j-1] } else { 0 }
antiDiagonal[i][j] = 1 + if i > 0 && j < n-1 { antiDiagonal[i-1][j+1] } else { 0 }
maxLength = max(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j])
}
}
}
return maxLength
}
func max(vals ...int) int {
maxVal := vals[0]
for _, val := range vals {
if val > maxVal {
maxVal = val
}
}
return maxVal
}Algorithm
Создайте 3 матрицы для хранения текущей длины последовательных единиц: horizontal, vertical, diagonal и anti_diagonal.
Итерируйте через каждый element матрицы: Если element равен 1, обновите соответствующие значения в матрицах horizontal, vertical, diagonal и anti_diagonal. Обновите максимальную длину последовательной линии.
return максимальную длину.
😎
Vacancies for this task
활성 채용 with overlapping task tags are 표시됨.
아직 활성 채용이 없습니다.