葫芦岛网站公司,seo网站建设是什么意思,公司电子商务网站建设规划方案,广西学校论坛网站建设废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【动态规划】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【动态规划】使用【数组】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。
明确目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
最大正方形【MID】
来解决一道最大正方形的题目
题干 解题思路
原题解出处按照动态规划的标准解题讨论来进行解题理解 min(上, 左, 左上) 1如题在其他动态规划方法的题解中大都会涉及到下列形式的代码
// 伪代码
if (matrix(i , j ) 1) {dp(i, j) min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) 1;
}其中dp(i, j) 是以 matrix(i , j ) 为 右下角 的正方形的最大边长 若某格子值为 1则以此为右下角的正方形的、最大边长为上面的正方形、左面的正方形或左上的正方形中最小的那个再加上此格 先来阐述简单共识
若形成正方形非单 1以当前为右下角的视角看则需要当前格、上、左、左上都是 1可以换个角度当前格、上、左、左上都不能受 0 的限制才能成为正方形 上面详解了 三者取最小 的含义
图 1受限于左上的 0图 2受限于上边的 0图 3受限于左边的 0
数字表示以此为正方形右下角的最大边长黄色表示格子 ? 作为右下角的正方形区域。就像 木桶的短板理论 那样——附近的最小边长才与 ? 的最长边长有关。 此时已可得到递推公式
// 伪代码
if (grid[i][j] 1) {dp[i][j] min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) 1;
}1 定义状态定义子问题
dp 具体定义dp[i ][j ] 表示 「以第 i 行、第 j 列为右下角的正方形的最大边长」
为何不是 dp[i][j]回到图解中任何一个正方形我们都「依赖」当前格 左、上、左上三个方格的情况但第一行的上层已经没有格子第一列左边已经没有格子需要做特殊 if 判断来处理为了代码简洁我们 假设补充 了多一行全 ‘0’、多一列全 ‘0’
2 状态转移方程描述子问题之间的联系
取自己左上、上方、左边最小值再加上自身
// 伪代码
if (grid[i][j] 1) {dp[i][j] min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) 1;
}3 初始化状态
初始值就是将第一列 dp[row][0] 、第一行 dp[0][col] 都赋为 0相当于已经计算了所有的第一行、第一列的 dp 值
4 求解方向
这里采用自底向上从最小的状态开始求解
5 找到最终解
题目要求面积。根据 「面积 边长 x 边长」可知我们只需求出 最大边长 即可,定义 maxSide 表示最长边长每次得出一个 dp就 maxSide max(maxSide, dp); 最终返回 return maxSide * maxSide;
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法动态规划 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param nums int整型一维数组* return int整型一维数组*/public int maximalSquare(char[][] matrix) {// 1 入参校验if (matrix null || matrix.length 0 || matrix[0].length 0) {return 0;}// 2 定义最长边以及获取边长int maxSide 0;int row matrix.length;int col matrix[0].length;// 3 定义dp数组,dp[i][j]表示以i、j为坐标的元素作为右下角的最大正方形边长默认初始化了两列0int[][] dp new int[row 1][col 1];// 4 编写状态转移方程for (int i 1; i row; i) {for (int j 1; j col; j) {if (matrix[i - 1][j - 1] 1) {dp[i][j] Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) 1;maxSide Math.max(maxSide, dp[i][j]);}}}return maxSide * maxSide;}
}考虑到每个方格都需要参与计算双重循环要从索引1开始否则dp[0][0]无法进行状态转移会数组越界这样为了第0行第0列可以参与计算就给dp数组补了0也就是base case补0后dp的第1行和第1列对应的判断元素其实是matrix的第0行和第0列所以这里的if条件是matrix[i - 1][j - 1] 1
复杂度分析
时间复杂度O(N^2)这里 N 是数组的长度我们写了两个 for 循环每个 for 循环的时间复杂度都是线性的 空间复杂度O(N)要使用和输入数组长度相等的状态数组因此空间复杂度是 O(N)。
