面试题库 › 算法 / 大模型 › 统计全为 1 的正方形子矩阵(LeetCode 1277)

统计全为 1 的正方形子矩阵(LeetCode 1277)

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

字节跳动1

常见岗位:机器学习算法(泛)

答案要点

  1. 状态:dp[i][j] 为以 (i,j) 为右下角的最大全 1 正方形边长
  2. 转移:matrix[i][j]=1 时 dp = min(上, 左, 左上) + 1,否则为 0
  3. 计数:以 (i,j) 为右下角的正方形个数等于 dp[i][j],累加即为答案
  4. 边界:首行首列 dp 等于原矩阵值
  5. 时间 O(mn),空间可原地更新或用一维数组优化

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题