max-black-square-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

Imagine you have a square matrix, where each cell (pixel) is either black or white Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Return an array&nbsp;<code>[r, c, size]</code>, where&nbsp;<code>r</code>,&nbsp;<code>c</code>&nbsp;are the row number and the column number of the subsquare&#39;s upper left corner respectively, and <code>size</code>&nbsp;is the side length of the subsquare. If there are more than one answers, return the one that has smallest <code>r</code>. If there are more than one answers that have the same <code>r</code>, return the one that has smallest <code>c</code>. If there&#39;s no answer, return an empty array.

Example 1:

<pre>
Input:
[
&nbsp; [1,0,1],
&nbsp; [0,0,1],
&nbsp; [0,0,1]
]
Output: [1,0,2]
Explanation: 0 represents black, and 1 represents white, bold elements in the input is the answer.
</pre>

Example 2:

<pre>
Input:
[
&nbsp; [0,1,1],
&nbsp; [1,0,1],
&nbsp; [1,1,0]
]
Output: [0,0,1]
</pre>

Note: 

<ul>
	<li><code>matrix.length == matrix[0].length &lt;= 200</code></li>
</ul>

findSquare

Max Black Square LCCI

Array

Dynamic Programming

Matrix

给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 <code>[r, c, size]</code> ，其中&nbsp;<code>r</code>,&nbsp;<code>c</code>&nbsp;分别代表子方阵左上角的行号和列号，<code>size</code> 是子方阵的边长。若有多个满足条件的子方阵，返回 <code>r</code> 最小的，若 <code>r</code> 相同，返回 <code>c</code> 最小的子方阵。若无满足条件的子方阵，返回空数组。

示例 1：

<pre>
输入：
[
&nbsp; [1,0,1],
&nbsp; [0,0,1],
&nbsp; [0,0,1]
]
输出：[1,0,2]
解释：输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
</pre>

示例 2：

<pre>
输入：
[
&nbsp; [0,1,1],
&nbsp; [1,0,1],
&nbsp; [1,1,0]
]
输出：[0,0,1]
</pre>

提示：

<ul>
	<li><code>matrix.length == matrix[0].length &lt;= 200</code></li>
</ul>