当前位置: 首页 > news >正文

网站推广的方法?seo零基础入门教程

网站推广的方法?,seo零基础入门教程,sm做任务的网站,建好网站后最怎么维护优质博文:IT-BLOG-CN 一、题目 在一个由0和1组成的二维矩阵内,找到只包含1的最大正方形,并返回其面积。 示例 1: 输入:matrix [["1","0","1","0","0"],[&quo…

优质博文:IT-BLOG-CN

一、题目

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

示例 1:
在这里插入图片描述

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

示例 2:
在这里插入图片描述

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

示例 3:

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

提示:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j]'0''1'

二、代码

方法一:暴力法

由于正方形的面积等于边长的平方,因此要找到最大正方形的面积,首先需要找到最大正方形的边长,然后计算最大边长的平方即可。

暴力法是最简单直观的做法,具体做法如下:

遍历矩阵中的每个元素,每次遇到1,则将该元素作为正方形的左上角;

确定正方形的左上角后,根据左上角所在的行和列计算可能的最大正方形的边长(正方形的范围不能超出矩阵的行数和列数),在该边长范围内寻找只包含1的最大正方形;

每次在下方新增一行以及在右方新增一列,判断新增的行和列是否满足所有元素都是1

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++) {// 判断新增的一行一列是否均为 1boolean 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;}
}

时间复杂度: O(mnmin(m,n) ^2),其中mn是矩阵的行数和列数。
 ☑️ 需要遍历整个矩阵寻找每个1,遍历矩阵的时间复杂度是O(mn)
 ☑️ 对于每个可能的正方形,其边长不超过mn中的最小值,需要遍历该正方形中的每个元素判断是不是只包含1,遍历正方形时间复杂度是O(min(m,n)^2)
 ☑️ 总时间复杂度是O(mnmin(m,n) ^2)

空间复杂度: O(1)。额外使用的空间复杂度为常数。

方法二:动态规划

方法一虽然直观,但是时间复杂度太高,有没有办法降低时间复杂度呢?

可以使用动态规划降低时间复杂度。我们用dp(i,j)表示以(i,j)为右下角,且只包含1的正方形的边长最大值。如果我们能计算出所有dp(i,j)的值,那么其中的最大值即为矩阵中只包含1的正方形的边长最大值,其平方即为最大正方形的面积。

那么如何计算dp中的每个元素值呢?对于每个位置(i,j),检查在矩阵中该位置的值:

如果该位置的值是0,则dp(i,j)=0,因为当前位置不可能在由1组成的正方形中;

如果该位置的值是1,则dp(i,j)的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言,当前位置的元素值等于三个相邻位置的元素中的最小值加1,状态转移方程如下:
dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1

此外,还需要考虑边界条件。如果ij中至少有一个为0,则以位置(i,j)为右下角的最大正方形的边长只能是1,因此dp(i,j)=1

以下用一个例子具体说明。原始矩阵如下。

0 1 1 1 0
1 1 1 1 0
0 1 1 1 1
0 1 1 1 1
0 0 1 1 1

对应的dp值如下。

0 1 1 1 0
1 1 2 2 0
0 1 2 3 1
0 1 2 3 2
0 0 1 2 3

下图也给出了计算dp值的过程。

在这里插入图片描述

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;int[][] dp = new int[rows][columns];for (int i = 0; i < rows; i++) {for (int j = 0; j < columns; j++) {if (matrix[i][j] == '1') {if (i == 0 || j == 0) {dp[i][j] = 1;} else {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]);}}}int maxSquare = maxSide * maxSide;return maxSquare;}
}

时间复杂度: O(mn),其中mn是矩阵的行数和列数。需要遍历原始矩阵中的每个元素计算dp的值。

空间复杂度: O(mn),其 mn是矩阵的行数和列数。创建了一个和原始矩阵大小相同的矩阵dp。由于状态转移方程中的dp(i,j)由其上方、左方和左上方的三个相邻位置的dp值决定,因此可以使用两个一维数组进行状态转移,空间复杂度优化至O(n)

http://www.tj-hxxt.cn/news/11117.html

相关文章:

  • 网络策划师是什么职业网络优化的内容包括哪些
  • 工程建设概念西安关键词排名优化
  • 网站开发税目编码一元手游平台app
  • 哪家做网站做的好官网优化包括什么内容
  • 弱电网站源码百度热搜关键词排名
  • 如何做同城信息网站百度风云排行榜
  • 宿州注册公司多少钱搜索引擎优化seo价位
  • 昆明营销型网站建设北京建站工作室
  • 内网网站建设工作会议品牌策划与推广方案
  • 南宁网站关键字优化微信公众平台开发
  • 网站工程师是做什么的怎么做私人网站
  • 企业网站做开放api网站排名软件有哪些
  • 浏览器网站在线进入常用的seo网站优化排名
  • 可以做没有水印的视频网站网页优化怎么做
  • wordpress 外贸企业模板seo排名软件怎么做
  • 阿里云 网站部署广告联盟哪个比较好
  • 无锡 网站建设公司营销软件商城
  • 如何制作网站后台郑州seo排名公司
  • 网站页面的大小写电商网站链接买卖
  • 自然景观网站模板国产免费crm系统有哪些在线
  • 做网站专题页需要注意什么淘宝关键词搜索量查询工具
  • 黄山地区建设行业网站广告投放平台公司
  • 遵义做网站 0852t银行营销技巧和营销方法
  • 今日油价最新价格查询搜索引擎优化的分类
  • sublime怎么做网站晋城今日头条新闻
  • 图文广告店最佳名字seo网站排名软件
  • 营销型网站的盈利模式sem 优化价格
  • 做庭院景观的那个网站推广好web网页
  • 单仁做的网站宁波网站关键词优化排名
  • 廊坊免费网站建设模板郑州seo招聘