文章目录最大正方形一、题目在说什么二、动态规划思路1. dp 数组的含义2. 状态转移怎么来的3. 边界怎么处理三、代码实现总结二叉树的最近公共祖先一、题目描述二、思路与代码1. 思路2. 代码实现总结最大正方形最大正方形是 LeetCode 第 221 题考的是动态规划。题目给出一个只含 0 和 1 的矩阵要你找出最大的全 1 正方形。暴力枚举四个角会非常慢用 DP 可以一趟扫完。本文只讲一种解法就是二维 DP 打表。一、题目在说什么题意不复杂矩阵里每个格子是字符 ‘0’ 或者 ‘1’。矩阵里只有 0 和 1正方形不能带着 0 混进去。你要在里面找一块全是 ‘1’ 的正方形区域。返回的是面积不是边长这点容易记混。二、动态规划思路1. dp 数组的含义dp[i][j] 表示以 (i, j) 为右下角的最大正方形边长。注意是右下角这个定位很关键。2. 状态转移怎么来的如果当前格子是 ‘0’那它不可能作为正方形的右下角。所以这种情况下 dp 直接是 0不用管。如果当前格子是 ‘1’就要看它左边、上边和左上角。这三个位置里最小的那个边长加一就是当前位置的边长。为什么取最小因为正方形要求这四条边都不能断。任何一边不够长整块就撑不起来。3. 边界怎么处理第一行和第一列的格子没有左边或上边。它们只能单独成块所以只要值是 ‘1’边长就是 1。代码里用 i 或 j 等于 0 来判断边界。三、代码实现classSolution:defmaximalSquare(self,matrix:List[List[str]])-int:# 动态规划dp[i][j] 代表以 i,j 为右下角的最大正方形边长rows,columnslen(matrix),len(matrix[0])# 创建一个 dp 数组用来存放 dp 矩阵dp[[0]*columnsfor_inrange(rows)]# 获取最大正方形的边长maxSide0foriinrange(rows):forjinrange(columns):ifmatrix[i][j]1:# 若在边上则 dp 1ifi0orj0:dp[i][j]1# 否则就是 左边、上边 和 左上角的 dp 1else:dp[i][j]min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])1# 别忘了动态更新maxSidemax(maxSide,dp[i][j])else:passreturnmaxSide*maxSidedp 用二维列表初始化先全部填 0。外层遍历行内层遍历列逐个格子判断。遇到 ‘1’ 才处理遇到 ‘0’ 保持 0 就行。每算出一个边长顺手更新一下 maxSide。总结最大正方形的核心是把右下角当成切入点。状态转移取左边、上边、左上角三者的最小值再加一。最后别忘了返回边长的平方也就是面积。二叉树的最近公共祖先二叉树的最近公共祖先是 LeetCode 第 236 题。题目给你一棵二叉树和两个节点要你找出它们最深的共同祖先。一、题目描述所谓公共祖先就是一个同时是 p 和 q 祖先的节点。最近的意思是在这所有公共祖先里深度最大的那个。这里的深度指的是从根出发到该节点经过的节点数。注意一个节点也可以是自己的祖先。二、思路与代码1. 思路两个节点往上走一定会交汇交汇点就是答案。可二叉树只有向下的指针没有指向父节点的指针。所以第一步要先补出「父节点表」。用一次 DFS 把所有节点和它的父节点记进字典。第二步从 p 出发一路往根走把路过的节点标记下来。再从 q 出发往上走遇到的第一个标记过的节点就是答案。2. 代码实现# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val x# self.left None# self.right NoneclassSolution:deflowestCommonAncestor(self,root:TreeNode,p:TreeNode,q:TreeNode)-TreeNode:# 先得到所有节点的父节点fa{}defdfs(node):ifnode.left:fa[node.left.val]node dfs(node.left)ifnode.right:fa[node.right.val]node dfs(node.right)fa[root.val]Nonedfs(root)vis{}# 将 p 往回溯找到其所有祖先whilep:vis[p.val]Truepfa[p.val]# 将 q 往上走看是否被标记过whileq:ifvis.get(q.val):returnq qfa[q.val]returnNone总结这题的思路就一句话补出父指针再向上找交汇点。先用 DFS 建好父节点字典再让 p 和 q 各自往上走。时间复杂度 O(n)空间 O(n)代码短也好记。