В этом посте мы собираемся обсудить leetcode 1277 — Count Square Submatrics with All Ones, который задают в интервью Google, Amazon, Meta и Microsoft.

Анализ проблемы

По заданной матрице m * n из единиц и нулей верните, сколько подматриц квадратных содержат все единицы.

Пример 1:

Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 
Output: 15 
Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1…