分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.ArrayAndMatrix; /** * 边界都是1的最大正方形大小 * * 【题目】 * 给定一个NxN的短阵matrix在这个矩阵中只有0和1两种值返回边框全是1的最大正方形的边长长度。 * 例如 * 0 1 1 1 1 * 0 1 0 0 1 * 0 1 0 0 1 * 0 1 1 1 1 * 0 1 0 1 1 * 其中边框全是1的最大正方形的大小为4x4所以返回4。 * * 【难度】 * 中等 * * 【解答】 * 先介绍一个比较容易理解的解法 * 1.矩阵中一共有NxN个位置。O(N^2) * 2.对每一个位置都看是否可以成为边长为N-1的正方形左上角。比如对于(0,0)位置依次检查是否是边长为5的正方形左上角然 * 后检查边长为4、3等。O(N) * 3.如何检查一个位置是否可以成为边长为N的正方形的左上角呢?遍历这个边长为N的正方形边界看是否只由1构成也就是走过4个边的 * 长度(4N)。O(N) * 所以普通方法总的时间复杂度为O(N^2)xO(N)xO(N)O(N^4)。 * * 本文提供的方法的时间复杂度为O(N^3)基本过程也是如上三个步骤。但是对于步骤3可以把时间复杂度由O(N)降为O(1)。具体地 * 说就是能够在O(1)的时间内检查一个位置假设为(i,j)是否可以作为边长为a(1aN)的边界全是1的正方形左上角。关键是使 * 用预处理技巧这也是面试经常使用的技巧之一下面介绍得到预处理矩阵的过程。 * * 1.预处理过程是根据矩阵matrix得到两个矩阵right和down。right[i][j]的值表示从位置(i,j)出发向右有多少个连续的1。 * down[i][j]的值表示从位置(i,j)出发向下有多少个连续的1。 * * 2.right和down矩阵如何计算 * 1)从矩阵的右下角(n-l,n-1)位置开始计算如果matrix[n-1][n-1]1那么right[n-1][n-1]1且down[n-1][n-1]1 * 否则都等于0。 * 2)从右下角开始往上计算即在matrix最后一列上计算位置就表示为(i,n-1)。对right矩阵来说最后一列的右边没有内容所 * 以如果matrix[i][n-1]1则令right[i][n-1]1否则为0。对down矩阵来说如果matrix[i][n-1]1因为 * down[i1][n-1]表示包括位置(i1,n-1)在内并往下有多少个连续的1所以如果位置(i,n-1)是1那么令down[i][n-1] * down[i1][n-1]1如果matrix[i][n-1]0则令down[i][n-1]0。 * 3)从右下角开始往左计算即在matrix最后一行上计算位置可以表示为(n-1,j)。对right矩阵来说如果matrix[n-1][j]1 * 因为right[n-1][j1]表示包括位置(n-1,j1)在内右边有多少个连续的1。所以如果位置(n-1,j)是1则令right[n-1][j] * right[n-1][j1]1如果matrix[n-1][j]0则令right[n-1][j]0。对down矩阵来说最后一列的下边没有内容 * 所以如果matrix[n-1][j]1令down[n-1][j]1否则为0。 * 4)计算完步骤1)~步骤3)之后剩下的位置都是既有右也有下假设位置表示为(i,j) * 如果matrix[i][j]1则令right[i][j]right[i][j1]1down[i][j]down[i1][j]1。 * 如果matrix[i][j]0则令right[i][j]0down[i][j]0。 * * 预处理的具体过程请参看如下代码中的setBorderMap方法。 * * 得到right和down矩阵后如何加速检查过程呢比如现在想检查一个位置假设为(i,j)。是否可以作为边长为a(1aN)的边 * 界全为1的正方形左上角。 * 1)位置(i,j)的右边和下边连续为1的数量必须都大于或等于a(right[i][j]adown[i][j]a)否则说明上边界和左边界的 * 1不够。 * 2)位置(i,j)向右跳到位置(i,ja-1)这个位置是正方形的右上角那么这个位置的下边连续为1的数量也必须大于或等于 * a(down[i][ja-1]a)否则说明右边界的1不够。 * 3)位置(i,j)向下跳到位置(ia-l,j)这个位置是正方形的左下角那么这个位置的右边连续为1的数量也必须大于或等于 * a(right[ia-1][j]a)否则说明下边界的1不够。 * 以上三个条件都满足时就说明位置(i,j)符合要求利用right和down矩阵之后加速的过程很明显不需要遍历边长上的所有值 * 了只看4个点即可。 * * 全部过程请参看如下代码中的getMaxSize方法。 * * author Created by LiveEveryDay */ public class Border1MaxSquareSize { public static void setBorderMap(int[][] m, int[][] right, int[][] down) { int r m.length; int c m[0].length; if (m[r - 1][c - 1] 1) { right[r - 1][c - 1] 1; down[r - 1][c - 1] 1; } for (int i r - 2; i ! -1; i--) { if (m[i][c - 1] 1) { right[i][c - 1] 1; down[i][c - 1] down[i 1][c - 1] 1; } } for (int i c - 2; i ! -1; i--) { if (m[r - 1][i] 1) { right[r - 1][i] right[r - 1][i 1] 1; down[r - 1][i] 1; } } for (int i r - 2; i ! -1; i--) { for (int j c - 2; j ! -1; j--) { if (m[i][j] 1) { right[i][j] right[i][j 1] 1; down[i][j] down[i 1][j] 1; } } } } public static int getMaxSize(int[][] m) { int[][] right new int[m.length][m[0].length]; int[][] down new int[m.length][m[0].length]; setBorderMap(m, right, down); for (int size Math.min(m.length, m[0].length); size ! 0; size--) { if (hasSizeOfBorder(size, right, down)) { return size; } } return 0; } public static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) { for (int i 0; i ! right.length - size 1; i) { for (int j 0; j ! right[0].length - size 1; j) { if (right[i][j] size down[i][j] size right[i size - 1][j] size down[i][j size - 1] size) { return true; } } } return false; } public static void main(String[] args) { int[][] matrix new int[][]{ {0, 1, 1, 1, 1}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 1}, {0, 1, 1, 1, 1}, {0, 1, 0, 1, 1,}}; System.out.printf(The max size is: %d, getMaxSize(matrix)); } } // ------ Output ------ /* The max size is: 4 */