#43. Number of Islands
Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island (1's) is surrounded by water (0's) and is formed by connecting adjacent lands horizontally or vertically.
class Solution {
public int numIslands(char[][] grid) {
if (grid.length == 0) {
return 0;
}
int[][] markedGrid = new int[grid.length][grid[0].length];
for (int i=0; i<markedGrid.length; i++) {
for (int j=0; j<markedGrid[i].length; j++) {
markedGrid[i][j] = 0;
}
}
int tag = 1;
for (int i=0; i<grid.length; i++) {
for (int j=0; j<grid[i].length; j++) {
if (markedGrid[i][j] == 0) {
AtomicBoolean modified = new AtomicBoolean(false);
markedGrid = markGrid(i, j, grid, markedGrid, tag, modified);
if (modified.get()) {
tag++;
}
}
}
}
return tag - 1;
}
private int[][] markGrid(int i, int j, char[][] grid, int[][] markedGrid, int tag, AtomicBoolean modified) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0' || markedGrid[i][j] > 0) {
return markedGrid;
}
markedGrid[i][j] = tag;
markedGrid = markGrid(i-1, j, grid, markedGrid, tag, modified);
markedGrid = markGrid(i+1, j, grid, markedGrid, tag, modified);
markedGrid = markGrid(i, j-1, grid, markedGrid, tag, modified);
markedGrid = markGrid(i, j+1, grid, markedGrid, tag, modified);
modified.set(true);
return markedGrid;
}
}
#44. Pacific Atlantic Water Flow
There is an m x n rectangular island that borders both the Pacific Ocean and the Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix height where heights[r][c] represent the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rainwater can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates results where result[i] = [ri, ci] denotes that rainwater can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
// solutie cu timp ridicat de executie
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
Map<Integer,Set<Integer>> edges = new HashMap<>();
for (int i=0; i<heights.length; i++) {
for (int j=0; j<heights[0].length; j++) {
int label = getNodeLabel(i, j, heights[0].length);
edges.put(label, getNeighbors(i,j,heights)); // edge from label to its neighbors (water flows to)
}
}
findAllEdges(edges, heights[0].length, heights.length);
List<List<Integer>> results = new ArrayList<>();
for (int node : edges.keySet()) {
boolean pacific = nearPacific(node, heights[0].length);
boolean atlantic = nearAtlantic(node, heights[0].length, heights.length);
if (!pacific || !atlantic) {
for (int conn : edges.get(node)) {
pacific = pacific || nearPacific(conn, heights[0].length);
atlantic = atlantic || nearAtlantic(conn, heights[0].length, heights.length);
if (pacific && atlantic) {
break;
}
}
}
if (pacific && atlantic) {
addResult(node, heights[0].length, results);
}
}
return results;
}
private void addResult(int node, int M, List<List<Integer>> results) {
int i = getI(node, M), j = getJ(node, M);
List<Integer> res = new ArrayList<>();
res.add(i);
res.add(j);
results.add(res);
}
private void findAllEdges(Map<Integer, Set<Integer>> edges, int M, int N) {
Map<Integer, Set<Integer>> allEdges = new HashMap(edges);
boolean doContinue = true;
while (doContinue) {
doContinue = false;
Set<Integer> toRemove = new HashSet<>();
for (int a : edges.keySet()) {
Set<Integer> toAdd = new HashSet<>();
for (int b : edges.get(a)) {
if (edges.get(b) != null) {
toAdd.addAll(edges.get(b));
toAdd.remove(a);
}
}
int size = edges.get(a).size();
edges.get(a).addAll(toAdd);
boolean modified = size < edges.get(a).size();
if (!modified) {
toRemove.add(a); // if no new connections added to a, it will never add more
}
allEdges.get(a).addAll(toAdd);
doContinue = doContinue || modified;
}
for (int a : toRemove) {
edges.remove(a);
}
}
edges = allEdges;
}
private boolean nearPacific(int nodeLabel, int M) {
int i = getI(nodeLabel, M), j = getJ(nodeLabel, M);
return i == 0 || j == 0;
}
private boolean nearAtlantic(int nodeLabel, int M, int N) {
int i = getI(nodeLabel, M), j = getJ(nodeLabel, M);
return i == N - 1 || j == M - 1;
}
private Set<Integer> getNeighbors(int i, int j, int[][] heights) {
Set<Integer> neighbors = new HashSet<>(); // to whom water flows from (i,j)
if (i>0 && heights[i][j] >= heights[i-1][j]) {
neighbors.add(getNodeLabel(i-1, j, heights[0].length));
}
if (j>0 && heights[i][j] >= heights[i][j-1]) {
neighbors.add(getNodeLabel(i, j-1, heights[0].length));
}
if (i<heights.length-1 && heights[i][j] >= heights[i+1][j]) {
neighbors.add(getNodeLabel(i+1, j, heights[0].length));
}
if (j<heights[0].length-1 && heights[i][j] >= heights[i][j+1]) {
neighbors.add(getNodeLabel(i, j+1, heights[0].length));
}
return neighbors;
}
private int getNodeLabel(int i, int j, int M) {
return i * M + j;
}
private int getI(int nodeLabel, int M) {
return nodeLabel / M;
}
private int getJ(int nodeLabel, int M) {
return nodeLabel % M;
}
}
// solutie acceptabila ca timp
class Solution {
private enum Tag {UNK, PAC, ATL, BOTH};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
// init tags
Tag[][] tags = new Tag[heights.length][heights[0].length];
for (int i=0; i<heights.length; i++) {
for (int j=0; j<heights[0].length; j++) {
tags[i][j] = Tag.UNK;
}
}
for (int j=0; j<heights[0].length; j++) {
tags[0][j] = Tag.PAC;
tags[heights.length-1][j] = updateTag(tags[heights.length-1][j], Tag.ATL);
}
for (int i=0; i<heights.length; i++) {
tags[i][0] = updateTag(tags[i][0], Tag.PAC);
tags[i][heights[0].length-1] = updateTag(tags[i][heights[0].length-1], Tag.ATL);
}
// tag all
for (int i=0; i<heights.length; i++) {
for (int j=heights[0].length-1; j>=0; j--) {
tags = tagNode(i, j, heights, tags, new ArrayList<>()); // top-right to bottom-left
}
}
for (int i=heights.length-1; i>=0; i--) {
for (int j=0; j<heights[0].length; j++) {
tags = tagNode(i, j, heights, tags, new ArrayList<>()); // bottom-left to top-right
}
}
for (int i=0; i<heights.length; i++) {
for (int j=0; j<heights[0].length; j++) {
tags = tagNode(i, j, heights, tags, new ArrayList<>()); // top-left to bottom-right
}
}
for (int i=heights.length-1; i>=0; i--) {
for (int j=heights[0].length-1; j>=0; j--) {
tags = tagNode(i, j, heights, tags, new ArrayList<>()); // bottom-right to top-left
}
}
List<List<Integer>> results = new ArrayList<>();
for (int i=0; i<heights.length; i++) {
for (int j=0; j<heights[0].length; j++) {
if (tags[i][j] == Tag.BOTH) {
List<Integer> res = new ArrayList<>();
res.add(i);
res.add(j);
results.add(res);
}
}
}
return results;
}
private Tag[][] tagNode(int i, int j, int[][] heights, Tag[][] tags, List<Integer> trace) {
int currentNode = getNodeLabel(i, j, heights[0].length);
trace.add(currentNode);
if (i>0 && heights[i][j] >= heights[i-1][j]) {
int next = getNodeLabel(i-1, j, heights[0].length);
if (tags[i-1][j] == Tag.UNK && !trace.contains(next)) {
tagNode(i-1, j, heights, tags, trace);
}
tags[i][j] = updateTag(tags[i][j], tags[i-1][j]);
}
if (j>0 && heights[i][j] >= heights[i][j-1]) {
int next = getNodeLabel(i, j-1, heights[0].length);
if (tags[i][j-1] == Tag.UNK && !trace.contains(next)) {
tagNode(i, j-1, heights, tags, trace);
}
tags[i][j] = updateTag(tags[i][j], tags[i][j-1]);
}
if (i<heights.length-1 && heights[i][j] >= heights[i+1][j]) {
int next = getNodeLabel(i+1, j, heights[0].length);
if (tags[i+1][j] == Tag.UNK && !trace.contains(next)) {
tagNode(i+1, j, heights, tags, trace);
}
tags[i][j] = updateTag(tags[i][j], tags[i+1][j]);
}
if (j<heights[0].length-1 && heights[i][j] >= heights[i][j+1]) {
int next = getNodeLabel(i, j+1, heights[0].length);
if (tags[i][j+1] == Tag.UNK && !trace.contains(next)) {
tagNode(i, j+1, heights, tags, trace);
}
tags[i][j] = updateTag(tags[i][j], tags[i][j+1]);
}
return tags;
}
private Tag updateTag(Tag initialTag, Tag newTag) {
if (initialTag == Tag.UNK || initialTag == null) {
return newTag;
}
if (newTag == Tag.UNK) {
return initialTag;
}
if (initialTag != newTag) {
return Tag.BOTH;
}
return initialTag; // PAC sau ATL sau BOTH
}
private int getNodeLabel(int i, int j, int M) {
return i * M + j;
}
}
Niciun comentariu:
Trimiteți un comentariu