LeetCode 764. Largest Plus Sign
@(LeetCode)
问题描述
在一个二维的表格中，从 (0, 0) 到 (N-1, N-1)，每个格子里都包含一个 1，除了在 mines 中的格子除外，它包含 0。那么，由 1 组成的最大的十字符号是多少？返回十字符的阶数。如果不存在，返回 0。
k 阶由 1 组成的十字符定义如下：存在某个中心点 grid[x][y] = 1，且它的上下左右都有 k-1 个连续的 1。看下面的图形描述应该就很清楚了。
1 阶:
000
010
000
2 阶:
00000
00100
01110
00100
00000
3 阶:
0000000
0001000
0001000
0111110
0001000
0001000
0000000
栗 1：
输入：N = 5, mines = [[4, 2]]
输出：2
其中的一个十字符如下，用粗体标出：
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
栗 2：
输入: N = 2, mines = []
输出: 1
栗 3：
输入: N = 1, mines = [[0, 0]]
输出: 0
解释：不存在十字符，返回 0
注意：
-
N是一个整数，且其范围在[1, 500]。 -
mine的长度至多5000。 -
mine[i]有 2 个元素，且为整数，其范围为[0, N-1]。
解题思路
暴力解法
这题最直观最容易想到的思路就是穷举遍历法。
如果为 k 阶，则中心点四周的 1 的长度为 k - 1。
- 当
k = 1，只要grid中存在1即满足。 - 当
k = 2，那么至少需要上下各留一行，左右各留一列才能满足。即x >= 1 && x <= N - 2，y >= 1 && y <= N - 2。 - 同理，当
k = 3，上下至少需要各留2行，左右各留2列才满足。即x >= 2 && x <= N - 3，y >= 2 && y <= N - 3。
因此 ，当为 k 阶时可以推导出如下限制条件：
x >= k && x <= N - k - 1 ，y >= k && y <= N - k - 1。逐个遍历 x, y 的取值，判断是否能满足条件。
判断是否能组成十字符也挺简单，分别从中心点往上下左右四个方向，找出是否存在 k - 1 个连续的 1 即可。
若矩阵为 N * N，那么其最大的阶数为：maxOrder = (N - 1) / 2 + 1。
那么我们可以从最大阶数往下遍历，只要满足条件，则直接返回当前阶数即可。
代码如下：
/**
* @param {number} N
* @param {number[][]} mines
* @return {number}
*/
// Time Limit Exceeded
var orderOfLargestPlusSign = function(N, mines) {
// 预处理 mines
let map = new Map()
mines.map((array) => {
if (array.length === 2) {
const key = `${array[0]}-${array[1]}`
map.set(key, true)
}
})
let maxOrder = Math.floor((N - 1) / 2) + 1
let k = maxOrder
let i, j
while (k >= 1) {
for (i = k - 1; i <= N - k; i++) {
for (j = k - 1; j <= N - k; j++) {
// 计算是否满足条件
if (hasPlusSign(i, j, k, map)) {
return k
}
}
}
k -= 1
}
return 0
};
var hasPlusSign = function(i, j, k, map) {
// 计算是否满足条件
const key = `${i}-${j}`
if (!map.has(key)) {
// 左
let m = j - 1
while (m >= j - (k - 1)) {
const key = `${i}-${m}`
// 为 0，不满足
if (map.has(key)) {
return false
}
m -= 1
}
// 右
m = j + 1
while (m <= j + (k - 1)) {
const key = `${i}-${m}`
// 为 0，不满足
if (map.has(key)) {
return false
}
m += 1
}
// 下
m = i - 1
while (m >= i - (k - 1)) {
const key = `${m}-${j}`
// 为 0，不满足
if (map.has(key)) {
return false
}
m -= 1
}
// 下
m = i + 1
while (m <= i + (k - 1)) {
const key = `${m}-${j}`
// 为 0，不满足
if (map.has(key)) {
return false
}
m += 1
}
return true
}
return false
}
但是很可惜，这种解法会出现 Time Limit Exceeded，因为时间复杂度太高了，为 O(n^3)。
以上代码可查看 暴力解法。
动态规划
换个思路，其实一个中心点的最大阶数是由其上下左右最短的 1 的长度决定的。所以我们只需要求出每个点的最大阶数，遍历即可。
而求每个点的最大阶数，需要算出其上下左右 1 的长度才能得到。如果对于每个点，分别去求四个方向的长度，计算量还是比较大。
其实对于 grid[i][j]，假设其左边的长度为 l。那么对于它右边的格子 grid[i][j+1] 来说，如果其值为 0，则长度为 0；如果其值为 1，则长度为 l+1。这就是使用动态规划的思想，根据前一个值来进行计算，减少重复工作，真是比较妙啊。
以计算左边长度为例，其状态转移方程为：
// left[i][j] 存储点 (i, j) 左边的长度
若 grid[i][j] == 0, 则 left[i][j] = 0
若 grid[i][j] == 1，则 left[i][j] = left[i][j-1] + 1
举个栗子：
假设矩阵某一行为 11101，那么每个数对应的左边长度为 12301。从最左开始遍历，根据前一个值累加。
同理，右边的长度则从最右开始遍历累加，为 32101。
对于某一列来说：
1
0
1
1
上边的长度从最上开始计算，结果为：
1
0
1
2
下边的长度从最下开始计算，结果为：
1
0
2
1
这样就可以分别出计算上下左右的长度，取最小的长度即为当前点的最大阶数。这样一看，可能需要四个数组来保存上下左右的长度值，但是优化后，只需要一个数组。
比如我们先计算出左边的长度 l 保存下来，当在计算右边长度 r 时，只需计算 min(l, r) ，这样始终只记录最小的长度。在计算上边/下边长度时也一样。
当计算第四个方向时，这时已经知道当前点的阶数，整体最大阶数与其进行比较即可。
因此，大致思路为：
- 对于一行，从左往右遍历，计算左边长度；从右往左遍历，计算右边长度
- 对于一列，从上往下遍历，计算上边长度；从下往上遍历，计算下边长度
- 始终记录最小长度
- 计算完成，得到当前点阶数。最大阶数与其进行比较，进行更新
代码如下：
/**
* @param {number} N
* @param {number[][]} mines
* @return {number}
*/
// Time Limit Exceeded
var orderOfLargestPlusSign = function(N, mines) {
// 预处理 mines
let map = new Map()
mines.map((array) => {
if (array.length === 2) {
const key = `${array[0]}-${array[1]}`
map.set(key, true)
}
})
// 初始化数组为 0
let dp = new Array()
for (let r = 0; r < N; r++) {
let array = new Array()
for (let c = 0; c < N; c++) {
array.push(0)
}
dp.push(array)
}
let maxOrder = 0
// 以行遍历
for (let r = 0; r < N; r++) {
let len = 0
// 计算左边
for (let c = 0; c < N; c++) {
const key = `${r}-${c}`
if (map.has(key)) {
len = 0
} else {
len += 1
}
dp[r][c] = len
}
// 计算右边
len = 0
for (c = N - 1; c >= 0; c--) {
const key = `${r}-${c}`
if (map.has(key)) {
len = 0
} else {
len += 1
}
// 这里记录最小长度
dp[r][c] = Math.min(len, dp[r][c])
}
}
// 以列遍历
for (let c = 0; c < N; c++) {
let len = 0
// 计算上边
for (let r = 0; r < N; r++) {
const key = `${r}-${c}`
if (map.has(key)) {
len = 0
} else {
len += 1
}
// 这里记录最小长度
dp[r][c] = Math.min(len, dp[r][c])
}
// 计算下边
len = 0
for (r = N - 1; r >= 0; r--) {
const key = `${r}-${c}`
if (map.has(key)) {
len = 0
} else {
len += 1
}
// 这里记录最小长度
dp[r][c] = Math.min(len, dp[r][c])
// 最后一个方位计算完毕，则可确定该点的 order
maxOrder = Math.max(maxOrder, dp[r][c])
}
}
return maxOrder
}
以上代码可查看 动态规划解法。
