-
https://leetcode.com/problems/count-square-submatrices-with-all-ones/
행렬에서 정사각형 개수 찾기
1. Brute Force
둘레를 따라서 탐색하기 = 대각선으로 탐색하기
오른쪽 아래 방향으로 진행
/**
* @param {number[][]} matrix
* @return {number}
*/
var countSquares = function (matrix) {
let row = matrix[0].length;
let col = matrix.length;
let count = 0;
for (let y = 0; y < col; y++) {
for (let x = 0; x < row; x++) {
outerLoop: for (let i = 0; y + i < col && x + i < row; i++, count++) {
for (let j = 0; j <= i; j++) {
if (matrix[y + i][x + j] === 0 || matrix[y + j][x + i] === 0) break outerLoop;
}
}
}
}
return count;
};
2. 개선
특정 위치에서 만들 수 있는 사각형의 개수를 누적하여 기록
'알고리즘 > 리트코드' 카테고리의 다른 글
210. Course Schedule II (0) 2021.05.24 207. Course Schedule (0) 2021.05.23 152. Maximum Product Subarray (0) 2021.05.23 53. Maximum Subarray (0) 2021.05.23 121. Best Time to Buy and Sell Stock (0) 2021.05.23 댓글