活跃农民
- 积分
- 437
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-10-27
- 最后登录
- 1970-1-1
|
最近比较有印象的是一道union find的实现,不算鬼斧神工但是基本功很扎实,面试官肯定会喜欢。他实现了princeton算法第一课讲的path compression和rank weighting来优化表现,多数人不会在意这种细节。
class UF {
private:
vector<int> fathers;
vector<int> ranks;
public:
UF(int m, int n): fathers(vector<int>(m*n, -1)), ranks(vector<int>(m*n, 0)){}
// init a new union
void Init(int i){
fathers[i] = i;
ranks[i] = 1;
}
// find with path compression
int Find(int i){
while(i!=fathers[i]){
i = fathers[fathers[i]];
}
return i;
}
// union with rank weighting
void Union(int i, int j){
int root_i = Find(i);
int root_j = Find(j);
if (root_i==root_j) return;
if (ranks[root_i]>ranks[root_j]){
fathers[root_j] = root_i;
ranks[root_i] += ranks[root_j];
} else {
fathers[root_i] = root_j;
ranks[root_j] += ranks[root_i];
}
}
// size of the union
int Size(int i){
return ranks[Find(i)];
}
};
class Solution {
public:
int largestIsland(vector<vector<int>> &grid) {
int m = grid.size(), n = grid[0].size();
UF uf(m,n);
// preprocess to build uf and record zeros
vector<int> zeros;
for (int i = 0; i<m; i++){
for (int j = 0; j<n; j++){
int index = i*n+j;
if (grid[i][j]==0) {
zeros.push_back(index);
} else {
uf.Init(index);
// only union with previous, later not init yet
if (i>0 && grid[i-1][j]) uf.Union((i-1)*n+j, index);
if (j>0 && grid[i][j-1]) uf.Union(i*n+(j-1), index);
}
}
}
// solve
if (zeros.empty()) return m*n;
int ans = 0;
for (auto &zero:zeros){
int i = zero/n, j = zero%n;
unordered_set<int> roots; // neighbors' root, use set to remove duplicate
if (i>0 && grid[i-1][j]) roots.insert(uf.Find((i-1)*n+j));
if (i<m-1 && grid[i+1][j]) roots.insert(uf.Find((i+1)*n+j));
if (j>0 && grid[i][j-1]) roots.insert(uf.Find(i*n+j-1));
if (j<n-1 && grid[i][j+1]) roots.insert(uf.Find(i*n+j+1));
int area = 1;
for (auto &root:roots){
area += uf.Size(root);
}
ans = max(ans, area);
}
return ans;
}
};
|
|