Java 题解 | #奶牛的活动面积#
奶牛的活动面积
https://www.nowcoder.com/practice/666cb0dd46a2439fb7c44d24a9918bf7
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param land char字符型二维数组 * @return int整型 */ public int maximalSquare (char[][] land) { // write code here int m = land.length; // 获取地块的行数 int n = land[0].length; // 获取地块的列数 int[][] dp = new int[m][n]; // 创建动态规划数组dp,初始化为0 int maxSide = 0; // 记录最大边长 // 初始化dp数组的第一行和第一列 for (int i = 0; i < m; i++) { dp[i][0] = land[i][0] == 'C' ? 1 : 0; maxSide = Math.max(maxSide, dp[i][0]); } for (int j = 0; j < n; j++) { dp[0][j] = land[0][j] == 'C' ? 1 : 0; maxSide = Math.max(maxSide, dp[0][j]); } // 填充dp数组,使用状态转移方程 // dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (land[i][j] == 'C') { 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; // 返回最大面积,即最大边长的平方 } }
编程语言是Java。
该题考察的知识点是动态规划
代码的文字解释如下:初始化dp数组的第一行和第一列。遍历第一行和第一列,如果land[i][j]等于字符'C',则dp[i][j]赋值为1,表示以当前位置为右下角的正方形的最大边长为1;否则,赋值为0。同时,更新maxSide的值。
利用状态转移方程填充dp数组。对于其他位置(i, j),如果land[i][j]等于字符'C',则dp[i][j]的值由其上方、左方和左上方的dp值决定,取其中最小的dp值加1。同时,更新maxSide的值。