精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
一非C9的硕士毕业生收到比亚迪的offer，薪资待遇：13k*1.36*12，感觉有点低。我查了下比亚迪历年的校招薪资，这个待遇在比亚迪其实不算低，如果是和互联网大厂比确实有点少，但比亚迪毕竟不是互联网行业，核心技术还是以机械和电气为主。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第221题：最大正方形。
问题描述
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
输入：matrix = [["0","1"],["1","0"]]
输出：1
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'
问题分析
所以我们可以得出结论，如果matrix[i,j]是1，那么以它为右下角的最大正方形边长是min(dp[i-1][j-1]，dp[i-1][j]，dp[i][j-1])+1；
所以我们可以找出递推公式
如果matrix[i,j]为0，则dp[i][j]=0;
如果matrix[i,j]为1，则dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
public int maximalSquare(char[][] matrix) {
// 二维矩阵的宽和高
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
int maxSide = 0;// 最大正方形的宽
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
// 递推公式
dp[i][j] = Math.min(dp[i - 1][j],
Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
// 记录最大的边长
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide; // 返回正方形的面积
}
public:
int maximalSquare(vector<vector<char>> &matrix) {
// 二维矩阵的宽和高
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m + 1, vector(n + 1, 0));
int maxSide = 0;// 最大正方形的宽
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
// 递推公式
dp[i][j] = min(dp[i - 1][j],
min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
// 记录最大的边长
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide; // 返回正方形的面积
}
def maximalSquare(self, matrix: List[List[str]]) -> int:
# 二维矩阵的宽和高
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
maxSide = 0 # 最大正方形的宽
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i - 1][j - 1] == '1':
# 递推公式
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
# 记录最大的边长
maxSide = max(maxSide, dp[i][j])
return maxSide * maxSide # 返回正方形的面积
数组，稀疏表(Sparse Table)，单向链表，双向链表，块状链表，跳表，队列和循环队列，双端队列，单调队列，栈，单调栈，双端栈，散列表，堆，字典树(Trie树)，ArrayMap，SparseArray，二叉树，二叉搜索树(BST)，笛卡尔树，AVL树，树堆(Treap)，FHQ-Treap，哈夫曼树，滚动数组，差分数组，LRU缓存，LFU缓存
……
图的介绍，图的表示方式，邻接矩阵转换，广度优先搜索(BFS)，深度优先搜索(DFS)，A*搜索算法，迭代深化深度优先搜索(IDDFS)，IDA*算法，双向广度优先搜索，迪杰斯特拉算法(Dijkstra)，贝尔曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓扑排序，约翰逊算法(Johnson)
……
