LeetCode 959. Regions Cut By Slashes
原题链接在这里：https://leetcode.com/problems/regions-cut-by-slashes/
题目：
In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space. These characters divide the square into contiguous regions.
(Note that backslash characters are escaped, so a \ is represented as "\\".)
Return the number of regions.
Example 1:
Input:
[
" /",
"/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:
Example 2:
Input:
[
" /",
" "
]
Output: 1
Explanation: The 2x2 grid is as follows:
Example 3:
Input:
[
"\\/",
"/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:
Example 4:
Input:
[
"/\\",
"\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:
Example 5:
Input:
[
"//",
"/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:
Note:
1 <= grid.length == grid[0].length <= 30grid[i][j]is either'/','\', or' '.
题解：
If one grid is divided by both '/' and '\\', then it could be 4 regions.
Mark them as 0,1,2,3 for top, right, bottom and left part.
If there is no '/', then 0 and 1 are unioned, 2 and 3 are unioned.
If there is no '\\', then 0 and 3 are unioned, 1 and2 are unioned.
For two adjacent grids, left grid part 1 and right grid part 3 are unioned. top grid part 2 and bottom grid part 0 are unioned.
Finally return unions count.
Time Complexity: O(n^2logn). n = grid.length. find takes O(log(n^2)) = O(logn). With path compression and union by weight, amatorize O(1).
Space: O(n^2).
AC Java:
class Solution {
int [] parent;
int [] size;
int count;
int n;
public int regionsBySlashes(String[] grid) {
if(grid == null || grid.length == 0){
return 0;
}
n = grid.length;
parent = new int[n*n*4];
size = new int[n*n*4];
count = n*n*4;
for(int i = 0; i<n*n*4; i++){
parent[i] = i;
size[i] = 1;
}
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
if(i > 0){
union(getIndex(i-1, j, 2), getIndex(i, j, 0));
}
if(j > 0){
union(getIndex(i, j-1, 1), getIndex(i, j, 3));
}
if(grid[i].charAt(j) != '/'){
union(getIndex(i, j, 0), getIndex(i, j, 1));
union(getIndex(i, j, 2), getIndex(i, j, 3));
}
if(grid[i].charAt(j) != '\\'){
union(getIndex(i, j, 0), getIndex(i, j, 3));
union(getIndex(i, j, 1), getIndex(i, j, 2));
}
}
}
return count;
}
private void union(int i, int j){
int p = find(i);
int q = find(j);
if(p != q){
if(size[p] > size[q]){
parent[q] = p;
size[p] += size[q];
}else{
parent[p] = q;
size[q] += size[p];
}
count--;
}
}
private int find(int i){
while(i != parent[i]){
parent[i] = parent[parent[i]];
i = parent[i];
}
return parent[i];
}
private int getIndex(int i, int j, int k){
return (i*n+j)*4+k;
}
}
最新文章
- iOS 地图定位及大头针的基本使用
- Moon.Orm 5.0其他额外配置的讲解
- BizTalk动手实验（三）BizTalk开发综合实验
- maven 编译插件
- hrbustoj 1179:下山（DFS+剪枝）
- 【液晶模块系列基础视频】5.3.X-GUI字体驱动3
- asp.net获取select值的方法
- 异常练习一 throw
- JavaScript的实现
- 《Lua游戏开发实践指南》读后感
- Spring Boot启动过程（一）
- css弹性盒子新旧兼容
- NoClassDefFoundError: org/apache/commons/lang3/StringUtils
- [server]利用python构建的服务器地址问题
- 【aardio】]SQL创建、读写 excel
- WCF开发实战系列五：创建WCF客户端程序
- tensorflow之数据读取探究(1)
- Linux系统下我的/etc/sysconfig/路径下无iptables文件
- openssl安装/更新教程（CentOS）
- javascript 模块化编程