原题地址：被围绕的区域
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
并查集
根据题意，所有边界上的'O'及与其相连的'O'都不会被转换为'X'，所以我们可以先将这些'O'转换为'M'，再通过一次循环即可将其余的'O'转换为'X'的同时将这些'M'再转换为'O'。
具体的实现如下：
/**
* @param {string[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
const solve1 = function(board) {
// 空矩阵不需要处理
if (board.length === 0) {
return;
}
/**
* 将找到的边界上O及与其相连的O全部转换为M
* @param position 找到的边界O的位置
*/
const convertOToM = (position) => {
// 利用栈来存储需要转换的O
let stack = [position];
while (stack.length > 0) {
// 将栈顶元素弹出并转换为M
let item = stack.pop();
board[item[0]][item[1]] = 'M';
// 找到与栈顶元素相连的格子，如果其为O，则将其加入栈中
let linked = [
[item[0] - 1, item[1]],
[item[0] + 1, item[1]],
[item[0], item[1] - 1],
[item[0], item[1] + 1],
];
for (let j = 0; j < linked.length; j ++) {
if (linked[j][0] >= 0 && linked[j][0] < m && board[linked[j][0]][linked[j][1]] === 'O') {
stack.push(linked[j])
}
}
}
};
let [m, n] = [board.length, board[0].length];
// 将所有不会被转换为X的O临时转为M
for (let i = 0; i < n; i ++) {
if (board[0][i] === 'O') {
convertOToM([0, i]);
}
if (board[m - 1][i] === 'O') {
convertOToM([m - 1, i]);
}
}
for (let i = 1; i < m - 1; i ++) {
if (board[i][0] === 'O') {
convertOToM([i, 0])
}
if (board[i][n - 1] === 'O') {
convertOToM([i, n - 1])
}
}
// 将其余的O转换为X，同时将M转为O
for (let i = 0; i < m; i ++) {
for (let j = 0; j < n; j ++) {
if (board[i][j] === 'O') {
board[i][j] = 'X'
} else if (board[i][j] === 'M') {
board[i][j] = 'O'
}
}
}
};
测试：
let start = new Date();
const test = solve1;
let board = [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']];
test(board); // [['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]
console.log(board);
console.log(new Date().getTime() - start.getTime()); // 11
时间复杂度： 转换为
'M'时，所有元素最多会被处理一次，后续再次转换只需要一次循环即可完成，所以总的时间复杂度为$O(2MN)=O(MN)$
空间复杂度： 转换为'M'时需要一个栈辅助，空间不会超过矩阵的元素个数，所以空间复杂度为$O(MN)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Sep 27,2019