Smallest Rectangle Enclosing Black Pixels
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
For example, given the following image:
[
"0010",
"0110",
"0100"
]
and x = 0, y = 2,
Return 6.
----------------------------------------------------------------------
COME_BACK, mid的取值问题
binary search
getTop()和getLeft() 返回的都是包含black，其他2个返回的是不包含black。
稍微简单一点写法：
https://leetcode.com/discuss/68246/c-java-python-binary-search-solution-with-explanation
class Solution {
public:
int getTop(vector<vector<char>>& image, int x) {
int top = 0, bottom = x, n = image[0].size();
while (top < bottom) {
int mid = (top + bottom) / 2;
int k = 0;
while (k < n && image[mid][k] == '0') {
k++;
}
if (k < n) {
bottom = mid;
}else {
top = mid + 1;
}
}
return bottom;
}
int getBottom(vector<vector<char>>& image, int x) {
int top = x, bottom = image.size(), n = image[0].size();
while (top < bottom) {
int mid = (top + bottom) / 2;
int k = 0;
while (k < n && image[mid][k] == '0') {
k++;
}
if (k < n) {
top = mid + 1;
}else {
bottom = mid;
}
}
return bottom;
}
int getLeft(vector<vector<char>>& image, int y) {
int left = 0, right = y, m = image.size();
while (left < right) {
int mid = (left + right) / 2;
int k = 0;
while (k < m && image[k][mid] == '0') {
k++;
}
if (k < m) {
right = mid;
}else {
left = mid + 1;
}
}
return left;
}
int getRight(vector<vector<char>>& image, int y) {
int right = image[0].size(), left = y, m = image.size();
while (left < right) {
int mid = (left + right) / 2;
int k = 0;
while (k < m && image[k][mid] == '0') {
k++;
}
if (k < m) {
left = mid + 1;
}else {
right = mid;
}
}
return left;
}
int minArea(vector<vector<char>>& image, int x, int y) {
int top = getTop(image,x);
int bottom = getBottom(image,x + 1);
int left = getLeft(image,y);
int right = getRight(image,y + 1);
return (bottom - top) * (right - left);
}
};
Number of Islands II
A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.
1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.
1 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.
1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.
1 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]
Challenge:
Can you do it in time complexity O(k log mn), where k is the length of the positions?
-------------------------------------------------------
COME_BACK
标准union find, O(k * lg k), k 为 0 - m * n
注意：
#1 2维坐标和1维的来回转换
#2 看清题意，对count的计算
class UnionFind {
public:
UnionFind(vector<pair<int, int>>& positions, int col) {
this->col = col;
count = 0;
}
void addPoint(pair<int,int> &p) {
int index = encode(p);
root[index] = index;
size[index] = 1;
count++;
}
int findRoot(pair<int,int> &p) {
int index = encode(p);
if (root.find(index) == root.end()) return -1;
while (root[index] != index) {
index = root[index];
}
return index;
}
void unionF(pair<int,int> &p1, pair<int,int> &p2) {
int root1 = findRoot(p1), root2 = findRoot(p2);
if (root1 == root2) return;
if (size[root1] > size[root2]) {
size[root1] += size[root2];
root[root2] = root1;
}else {
root[root1] = root2;
}
count--;
}
int getCount() {
return count;
}
private:
unordered_map<int,int> root;
unordered_map<int,int> size;
int count;
int col;
int encode(pair<int, int> &position) {
return position.first * col + position.second;
}
pair<int,int> decode(int index) {
return make_pair<int,int>(index / col, index % col);
}
};
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> rt;
UnionFind uf(positions, n);
for (int i = 0; i < positions.size(); i++) {
uf.addPoint(positions[i]);
int x = positions[i].first, y = positions[i].second;
pair<int,int> p = make_pair(x + 1, y);
if (x + 1 < m && uf.findRoot(p) != - 1) {
uf.unionF(positions[i], p);
}
p = make_pair(x - 1,y);
if (x - 1 >= 0 && uf.findRoot(p) != - 1) {
uf.unionF(positions[i], p);
}
p = make_pair(x, y + 1);
if (y + 1 < n && uf.findRoot(p) != - 1) {
uf.unionF(positions[i],p);
}
p = make_pair(x, y - 1);
if (y - 1 >= 0 && uf.findRoot(p) != - 1) {
uf.unionF(positions[i], p);
}
rt.push_back(uf.getCount());
}
return rt;
}
};
Java, ids类似于一个树。注意2处可以优化的地方。 O(k * log m * n), k为插入的次数，log(m*n)为树的深度(find()方法)，完全优化后深度为1
https://blog.csdn.net/dm_vincent/article/details/7655764
https://blog.csdn.net/dm_vincent/article/details/7769159 UnionFind更多应用
class Solution {
private int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
public List numIslands2(int m, int n, int[][] positions) {
List rt = new ArrayList<>();
UnionFind uf = new UnionFind(m,n);
for (int[] pos : positions) {
uf.add(pos);
int p = uf.getRootId(pos[0], pos[1]);
for (int[] dir : dirs) {
int i = pos[0] + dir[0];
int j = pos[1] + dir[1];
int q = uf.getRootId(i, j);
if (q > 0 && q != p) {
uf.union(pos[0], pos[1], i, j);
}
}
rt.add(uf.getCount());
}
return rt;
}
}
class UnionFind {
private int count;
private int[] ids;
private int[] sizes;
private int m;
private int n;
public UnionFind(int m, int n) {
count = 0;
ids = new int[m * n + 1];
sizes = new int[m * n + 1];
this.m = m;
this.n = n;
}
public int getRootId(int i, int j) {
if (i >= 0 && i < m && j >= 0 && j < n) {
int index = getIndex(i,j);
if ((ids[index]) == 0) return 0;
return find(i, j);
}
return 0;
}
public void add(int[] pos) {
int id = getIndex(pos[0], pos[1]);
ids[id] = id;
sizes[id] = 1;
count++;
}
public int find(int i, int j) {
int id = getIndex(i,j);
while (ids[id] != id) {
ids[id] = ids[ids[id]]; // Optimization
id = ids[id];
}
return id;
}
public void union(int pI, int pJ, int qI, int qJ) {
int rootP = find(pI, pJ);
int rootQ = find(qI, qJ);
if (rootP == rootQ) return;
if (sizes[rootP] >= sizes[rootQ]) { // Optimization
sizes[rootP] += sizes[rootQ];
ids[rootQ] = rootP;
}else {
sizes[rootQ] += sizes[rootP];
ids[rootP] = rootQ;
}
count--;
}
public int getCount() {
return count;
}
private int getIndex(int i, int j) {
return i * n + j + 1;
}
}
