@(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
}
以上代码可查看 动态规划解法。
网友评论