python面试大全(3)
python前言(0)
发布于2019-08-07 12:33 阅读(705) 评论(0) 点赞(0) 收藏(5)
在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
示例:
- Input:
-
- 1 0 1 0 0
- 1 0 1 1 1
- 1 1 1 1 1
- 1 0 0 1 0
-
- Output: 4
输出4的原因是第2行和第3行中组成了2x2的正方形。
1、简单法
正方形的左上角也是正方形,正方形的最小边长为1。所以只要碰到'1',按照正方行对角线扩展,边长每增加1,对应轮廓增加1。从左上到右下,只要保证每次扩展的边界没有'0',便可以增加轮廓。
C++:
- class Solution {
- public:
- int maximalSquare(vector<vector<char>>& matrix) {
- if (matrix.empty() || matrix[0].empty())
- return 0;
- int ans = 0, row = matrix.size(), col = matrix[0].size();
- for (int i = 0; i < row;i++)
- for (int j = 0; j < col; j++)
- if (matrix[i][j] == '1')
- ans = max(ans, helper(i, j, matrix));
- return ans;
- }
- int helper(int x, int y, vector<vector<char>>& matrix){
- int circle = 1;
- bool flag = true;
- int row = matrix.size(), col = matrix[0].size();
- while(flag)
- {
- circle++;
- if (x + circle <= row && y + circle <= col)
- {
- for (int i = x; i < x + circle;i++)
- {
- if(matrix[i][y + circle - 1] == '0')
- {
- flag = false;
- circle--;
- return pow(circle, 2);
- }
- }
- for (int j = y; j < y + circle;j++)
- {
- if(matrix[x + circle - 1][j] == '0')
- {
- flag = false;
- circle--;
- return pow(circle, 2);
- }
- }
- }
- else
- {
- flag = false;
- circle--;
- }
- }
- return pow(circle, 2);
- }
- };
Python:
- class Solution:
- def maximalSquare(self, matrix: List[List[str]]) -> int:
- if len(matrix) == 0 or len(matrix[0]) == 0:
- return 0
- ans = 0
- row = len(matrix)
- col = len(matrix[0])
- def helper(x, y):
- circle = 1
- # flag = True
- while True:
- circle += 1
- if x + circle <= row and y + circle <= col:
- for i in range(x , x + circle):
- if matrix[i][y + circle - 1] == '0':
- # flag = False
- circle -= 1
- return pow(circle, 2)
- for j in range(y, y + circle):
- if matrix[x + circle - 1][j] == '0':
- # flag = False
- circle -= 1
- return pow(circle, 2)
- else:
- # flag = False
- circle -= 1
- return pow(circle, 2)
-
- for i in range(row):
- for j in range(col):
- if matrix[i][j] == '1':
- ans = max(ans, helper(i, j))
- return ans
2、递归
考虑这样一个例子:
- 1 1 1
- 1 1 1
- 1 1 1
这个例子中,假设已经知道除了不加右下角的1之外的所有最大面积。那么怎么得到包含右下角1的最大面积呢?首先,根据上面可知,右下角邻接的3个左、上、左上所能组成的均是一个2x2的正方形。那么,当左边的正方形被破坏呢?
- 1 1 1
- 1 1 1
- 0 1 1
其能组成的面积,要依赖左边点的面积。此时左边最大为1,组成结果为2x2。那么此时再将上面两个1破坏呢?
- 1 1 1
- 1 0 0
- 0 1 1
这个时候,左上和上的最大面积仅为0,所以,这时也组成不了2x2的面积,只能为1x1。总结一个规律就是:
C++:
- class Solution {
- public:
- int maximalSquare(vector<vector<char>>& matrix) {
- if (matrix.empty())
- return 0;
-
- int row = matrix.size(), col = matrix[0].size(), ans = 0;
- vector<vector<int>> dp(row, vector<int>(col, 0));
- for (int i = 0; i < row; i++)
- {
- for (int j = 0; j < col; j++)
- {
- if (!i || !j || matrix[i][j] == '0')
- {
- dp[i][j] = matrix[i][j] - '0';
- }
- else
- {
- dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
- }
- ans = max(dp[i][j], ans);
- }
- }
- return pow(ans, 2);
- }
- };
Python:
- class Solution:
- def maximalSquare(self, matrix: List[List[str]]) -> int:
- if len(matrix) == 0 or len(matrix[0]) == 0:
- return 0
- ans = 0
- row = len(matrix)
- col = len(matrix[0])
-
- dp = [[0 for j in range(col)] for i in range(row)]
- for i in range(row):
- for j in range(col):
- if (not i or not j or matrix[i][j] == '0'):
- dp[i][j] = ord(matrix[i][j]) - ord('0')
- else:
- dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
- ans = max(dp[i][j], ans)
- return pow(ans, 2)
作者:骷髅无悔
链接:https://www.pythonheidong.com/blog/article/10836/d6643fe60ad845a88b1b/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!