- 好习惯,务必数组要初始化,因为中途不是按照顺序走的,他是跳着走的,这样的话,int数组又是随机初始化(也可能随机初始化一个很小的值,所以,务必使用vector且全部初始化0. 后续在做自己的开始初始化,以及计算值)
class Solution { public: /** * 最大正方形 * @param matrix char字符型vector<vector<>> * @return int整型 */ int solve(vector<vector<char> >& matrix) { // write code here vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),0)); // 初始化 dp 矩阵的第一列 for(int i = 0; i< matrix.size();i++){ // 如果当前点为 1 ,那么最大正方形就是他本身,最大边长也就是 1 dp[i][0] = matrix[i][0] - '0'; } // 初始化 dp 矩阵的第一行 for(int i = 0; i< matrix[0].size();i++){ // 如果当前点为 1 ,那么最大正方形就是他本身,最大边长也就是 1 dp[0][i] = matrix[0][i] - '0'; } int max_ =0; // 遍历所有点,填充 dp 矩阵的所有位置。 for(int i = 1; i< matrix.size(); i++){ for(int j = 1; j< matrix[0].size();j++){ if(matrix[i][j] == '1'){//剪枝操作了。就导致部分dp没有初始化好,有垃圾数据。 dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]); dp[i][j]=min(dp[i][j],dp[i][j-1])+1; max_=max(max_,dp[i][j]); } } } return max_*max_; } };