LeetCode:221. Maximal Square(数组中最大的正方形) 分手后的思念是犯贱 2022-04-03 09:10 138阅读 0赞 > **文章最前**: 我是Octopus,这个名字来源于我的中文名--章鱼;我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ;这博客是记录我学习的点点滴滴,如果您对 Python、Java、AI、算法有兴趣,可以关注我的动态,一起学习,共同进步。 **相关文章:** 1. **[LeetCode:55. Jump Game(跳远比赛)][LeetCode_55. Jump Game]** 2. **[Leetcode:300. Longest Increasing Subsequence(最大增长序列)][Leetcode_300. Longest Increasing Subsequence]** 3. **[LeetCode:560. Subarray Sum Equals K(找出数组中连续子串和等于k)][LeetCode_560. Subarray Sum Equals K_k]** -------------------- **文章目录:** 题目描述: java实现方法1:暴力算法(brute force) python实现方式1: Java实现方式2: Python实现方式2: 源码github地址: -------------------- ### 题目描述: ### 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4 来源:力扣(LeetCode) -------------------- ### java实现方法1:暴力算法(brute force) ### /** * 获取最大正方形 * * @param matrix 二维数组 * @return 正方形边个数 */ public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } int row = matrix.length; int col = matrix[0].length; int maxSquare = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int temp = getMaxSquare(matrix, i, j); maxSquare = Math.max(maxSquare, temp); } } return maxSquare; } /** * 获取最大正方形 * * @param matrix 二维数组 * @param rowIndex 行号 * @param colIndex 列号 * @return 最大正方形 */ int getMaxSquare(char[][] matrix, int rowIndex, int colIndex) { int row = matrix.length; int col = matrix[0].length; if (matrix[rowIndex][colIndex] == '0') { return 0; } int length = 1; int maxSize = Math.min(row - rowIndex, col - colIndex); for (int size = 1; size < maxSize; size++) { int newCol = colIndex + size; int newRow = rowIndex + size; for (int i = rowIndex; i <= rowIndex + size; i++) { if (matrix[i][newCol] == '0') { return length * length; } } for (int j = colIndex; j <= colIndex + size; j++) { if (matrix[newRow][j] == '0') { return length * length; } } length++; } return length * length; } 时间复杂度:O(n^4) 空间复杂度:O(n) -------------------- ### python实现方式1: ### def get_max(self, matrix: List[List[int]], row_index: int, col_index: int) -> int: ''' 获取最大值 Args: matrix: 二维数组 row_index: 行下标 col_index: 列下标 Returns: 最大长度数量 ''' row, col = len(matrix), len(matrix[0]) if matrix[row_index][col_index] == '0': return 0 length = 1 max_size = min(row - row_index, col - col_index) for size in range(1, max_size): for i in range(row_index, row_index + size + 1): new_col = col_index + size if matrix[i][new_col] == '0': return length * length for j in range(col_index, col_index + size + 1): new_row = row_index + size if matrix[new_row][j] == '0': return length * length length += 1 return length * length def maximal_square(self, matrix: List[List[chr]]) -> int: ''' 获取最大正方形 Args: matrix: 输入二维数组 Returns: 最大正方形数量 ''' if matrix == None or len(matrix) < 1: return 0 row = len(matrix) col = len(matrix[0]) max_square = 0 for i in range(row): for j in range(col): temp = self.get_max(matrix, i, j) max_square = max(max_square, temp) return max_square 时间复杂度:O(n^4) 空间复杂度:O(n) -------------------- ### Java实现方式2: ### /** * 动态规划获取最大正方形 * * @param matrix 二维数组 * @return 最大正方形 */ public int maximalSquare2(char[][] matrix) { int maxSide = 0; if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return maxSide * maxSide; } int rows = matrix.length, cols = matrix[0].length; int[][] dp = new int[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (matrix[i][j] == '1') { if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } maxSide = Math.max(maxSide, dp[i][j]); } } } return maxSide * maxSide; } 时间复杂度:O(n\*m) 空间复杂度:O(n\*m) -------------------- ### Python实现方式2: ### def maximal_square2(self, matrix: List[List[chr]]) -> int: ''' 获取最大正方形 Args: matrix: 输入二维数组 Returns: 最大正方形数量 ''' if matrix == None or len(matrix) < 1: return 0 row = len(matrix) col = len(matrix[0]) dp = [[0 for x in range(col)] for y in range(row)] max_length = 0 for i in range(row): for j in range(col): if matrix[i][j] == '1': if i == 0 or j == 0: dp[i][j] = 1 else: dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1 max_length = max(max_length, dp[i][j]) return max_length * max_length 时间复杂度:O(n\*m) 空间复杂度:O(n\*m) -------------------- ### 源码github地址: ### [https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode] [github]: https://github.com/zhangyu345293721 [LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870 [Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249 [LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201 [https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode
还没有评论,来说两句吧...