LeetCode 221. 最大正方形
LeetCode 最大 正方形
2023-09-11 14:19:00 时间
思路
方法:动态规划
思路来源:
1 class Solution { 2 public: 3 int maximalSquare(vector<vector<char>>& matrix) { 4 if (matrix.size() == 0 || matrix[0].size() == 0) { 5 return 0; 6 } 7 int maxSide = 0; 8 int rows = matrix.size(), columns = matrix[0].size(); 9 vector<vector<int>> dp(rows, vector<int>(columns)); 10 for (int i = 0; i < rows; i++) { 11 for (int j = 0; j < columns; j++) { 12 if (matrix[i][j] == '1') { 13 if (i == 0 || j == 0) { 14 dp[i][j] = 1; 15 } else { 16 dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; 17 } 18 maxSide = max(maxSide, dp[i][j]); 19 } 20 } 21 } 22 int maxSquare = maxSide * maxSide; 23 return maxSquare; 24 } 25 };
相关文章
- 通过 LeetCode 周赛学习二分查找算法
- LeetCode高频题56. 合并区间,将重叠的区间合并为一个区间,包含所有区间
- 【Leetcode】1299. 将每个元素替换为右侧最大元素(简单)
- JS leetcode 找到所有数组中消失的数字 题解分析
- [LeetCode] Longest Substring Without Repeating Characters
- [LeetCode]剑指 Offer 42. 连续子数组的最大和
- LeetCode 421. 数组中两个数的最大异或值
- LeetCode数据结构_C语言题解系列-树
- 200、【数组】leetcode ——6316. 重排数组以得到最大前缀分数(C++版本)
- [LeetCode] 1043. Partition Array for Maximum Sum 分隔数组以得到最大和
- [LeetCode] 1139. Largest 1-Bordered Square 最大的以1为边界的正方形
- [LeetCode] 1032. Stream of Characters 字符流
- [LeetCode] 892. Surface Area of 3D Shapes 三维物体的表面积
- [LeetCode] Max Chunks To Make Sorted 可排序的最大块数
- [LeetCode] 559. Maximum Depth of N-ary Tree N叉树的最大深度
- [LeetCode] Max Increase to Keep City Skyline 保持城市天际线的最大增高
- [LeetCode] Cut Off Trees for Golf Event 为高尔夫赛事砍树
- [LeetCode] Prefix and Suffix Search 前后缀搜索
- [LeetCode] Map Sum Pairs 映射配对之和
- [LeetCode] 654. Maximum Binary Tree 最大二叉树
- [LeetCode] Maximum Distance in Arrays 数组中的最大距离
- [LeetCode] 421. Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字
- [LeetCode] 221. Maximal Square 最大正方形
- [LeetCode] 53. Maximum Subarray 最大子数组
- [LeetCode] 79. Word Search 词语搜索
- [LeetCode] 85. Maximal Rectangle 最大矩形
- [LeetCode] 164. Maximum Gap 求最大间距
- leetcode 413. Arithmetic Slices 等差数列划分