首页 > 编程语言 >#yyds干货盘点# LeetCode程序员面试金典:最大正方形

#yyds干货盘点# LeetCode程序员面试金典:最大正方形

时间:2023-08-19 22:00:46浏览次数:61  
标签:yyds matrix 正方形 int 金典 ++ maxSide length LeetCode

题目:

在一个由 '0' 和 '1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。

 

示例 1:

#yyds干货盘点# LeetCode程序员面试金典:最大正方形_Math

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4

示例 2:

#yyds干货盘点# LeetCode程序员面试金典:最大正方形_Math_02

输入:matrix = [["0","1"],["1","0"]]
输出:1

示例 3:

输入:matrix = [["0"]]
输出:0

代码实现:

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    // 遇到一个 1 作为正方形的左上角
                    maxSide = Math.max(maxSide, 1);
                    // 计算可能的最大正方形边长
                    int currentMaxSide = Math.min(rows - i, columns - j);
                    for (int k = 1; k < currentMaxSide; k++) {
                        // 判断新增的一行一列是否均为 1
                        boolean flag = true;
                        if (matrix[i + k][j + k] == '0') {
                            break;
                        }
                        for (int m = 0; m < k; m++) {
                            if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            maxSide = Math.max(maxSide, k + 1);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}

标签:yyds,matrix,正方形,int,金典,++,maxSide,length,LeetCode
From: https://blog.51cto.com/u_13321676/7152656

相关文章

  • #yyds干货盘点#electron-egg: 当代桌面开发框架
    当前技术社区中出现了各种下一代技术或框架,却很少有当代可以用的,于是electron-egg就出现了。当前桌面软件技术有哪些?语言技术优点缺点C#wpf专业的桌面软件技术,功能强大学习成本高Javaswing/javaFx跨平台和语言流行GUI库少,界面不美观C++Qt跨平台,功能和类库丰富学习成本高Swift无非跨......
  • leetcode2235 两整数相加
    题目描述:(这第一种方法我就不多说了,肯定是有手就行)给你两个整数num1和num2,返回这两个整数的和。示例1:输入:num1=12,num2=5输出:17解释:num1是12,num2是5,它们的和是12+5=17,因此返回17。示例2:输入:num1=-10,num2=4输出:-6解释:num1+num2=-6,因此返......
  • Leetcode 146 LRUCache
    /***Copyright(C)2023-08-1813:51zxinlog<[email protected]>**/#include<func.h>#defineN1000//普通NodetypedefstructNode{intkey;intvalue;structNode*prev;structNode*next;}Node;//定义HashNodetyped......
  • LeetCode 1020.飞地的数量
    1.题目:给你一个大小为 mxn 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数......
  • 【LeetCode1384. 按年度列出销售总额】MySQL使用with recursive根据开始日期和结束日
    题目地址https://leetcode.cn/problems/total-sales-amount-by-year/description/代码WITHRECURSIVEDateSeriesAS(SELECTproduct_id,period_startASsale_date,period_end,average_daily_salesFROMSales--Assumingyourtablenameissales_dataUN......
  • 【LeetCode2199. 找到每篇文章的主题】字符串处理题,使用MySQL里的group_concat和LOCAT
    题目地址https://leetcode.cn/problems/finding-the-topic-of-each-post/description/代码witht1as(selectp.*,k.*fromPostspleftjoinKeywordskonLOCATE(LOWER(CONCAT('',word,'')),LOWER(CONCAT('',conte......
  • Leetcode 142. 环形链表II(Linked list cycle ii)
    题目链接给定一个链表的头节点head,返回链表开始入环的第一个节点。.如果链表无环,则返回null.如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环.为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始).......
  • 【LeetCode2118. 建立方程】 group_concat指定分隔符,指定排序顺序
    目录题目地址题目描述代码题目地址https://leetcode.cn/problems/build-the-equation/description/题目描述Example2:输入:Terms表:+-------+--------+|power|factor|+-------+--------+|4|-4||2|1||1|-1|+-------+---......
  • 【LeetCode1225. 报告系统状态的连续日期】MySQL使用lag,lead得到连续段的:开始标志,结束
    目录题目地址题目描述代码题目地址https://leetcode.cn/problems/report-contiguous-dates/description/题目描述Asystemisrunningonetaskeveryday.Everytaskisindependentoftheprevioustasks.Thetaskscanfailorsucceed.Writeasolution toreportth......
  • 【LeetCode173. 最多连胜的次数】MySQL用户变量编程解法
    目录题目地址题目描述代码题目地址https://leetcode.cn/problems/longest-winning-streak/description/题目描述选手的 连胜数是指连续获胜的次数,且没有被平局或输球中断。编写解决方案来计算每个参赛选手最多的连胜数。结果可以以任何顺序返回。代码WITHt1AS(......