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的值。

全部评论

相关推荐

我是没经验的毕业生,这啥情况啊会不会是hr在刷kpi
JamesGosli...:字节boss属于是群发了,我都快入职字节了,其他部门还在和我boss打招呼
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务