Eran Medan
BAN USERConnected Components algorithm in a graph
public class Solution {
public static class Point {
int row;
int col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}
public boolean isValid(char[][] grid) {
int rows = grid.length;
int columns = grid[0].length;
return row >= 0 && row < rows && col >= 0 && col < columns && grid[row][col] == '1';
}
}
public static Point[] directions = {new Point(1,0),new Point(-1,0),new Point(0,1),new Point(0,-1)};
public int numIslands(char[][] grid) {
int rows = grid.length;
if(rows == 0){
return 0;
}
int columns = grid[0].length;
int component = 0;
boolean[][] visited = new boolean[rows][columns];
for (int i = 0; i< rows; i++) {
for (int j = 0; j< columns; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
visited[i][j] = true;
dfs(new Point(i,j), grid, visited);
component ++;
}
}
}
return component;
}
void dfs(Point start, char[][] grid, boolean[][] visited){
int rows = grid.length;
int columns = grid[0].length;
for(Point dir : directions) {
Point newPoint = new Point(start.row + dir.row, start.col + dir.col);
if(newPoint.isValid(grid) && !visited[newPoint.row][newPoint.col]) {
visited[newPoint.row][newPoint.col] = true;
dfs(newPoint, grid, visited);
}
}
}
}
Love your solution! small and elegant (and works)
- Eran Medan October 11, 2013Apparently all I had to do is change the priorities / precedence (left before down, up before right) to solve the last row edge case
import scala.annotation.tailrec
object Tests2 {
def main(args: Array[String]) {
solution("up")
println()
solution("yzy")
}
def solution(word: String) = {
word.foldLeft('a')((current, target) => {
pathToChar(current, target)
target
})
}
@tailrec
def pathToChar(start: Char, target: Char): Unit = {
val move = nextMove(start, target)
val dir = move._1
print(dir)
val nextChar = move._2
if (dir != '!') pathToChar(nextChar, target)
}
private def nextMove(current: Char, target: Char): (Char, Char) = {
def row(c: Char) = (c - 'a') / 5
def col(c: Char) = (c - 'a') % 5
val cr: Int = row(current)
val cc: Int = col(current)
val tr: Int = row(target)
val tc: Int = col(target)
val rowDist: Int = tr - cr
val colDist: Int = tc - cc
if (colDist < 0) {
('l', (current - 1).toChar)
} else if (rowDist < 0) {
('u', (current - 5).toChar)
} else if (colDist > 0) {
('r', (current + 1).toChar)
} else if (rowDist > 0) {
('d', (current + 5).toChar)
} else {
('!', current)
}
}
}
Yep, those edge cases :)
ddddrrrr!dllll!urrrr!
gotta handle the last row...
a bit verbose but simple to follow (I hope)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TreePrinter {
public static void main(String[] args) {
List<Relation> input = new ArrayList<>();
input.add(new Relation("animal", "mammal"));
input.add(new Relation("animal", "bird"));
input.add(new Relation("lifeform", "animal"));
input.add(new Relation("cat", "lion"));
input.add(new Relation("mammal", "cat"));
input.add(new Relation("animal", "fish"));
TreePrinter.printTree(input);
}
public static void printTree(Iterable<Relation> rs) {
Map<String, Node<String>> nodesByName = new HashMap<>();
for (Relation r : rs) {
String parent = r.parent;
String child = r.child;
Node<String> parentNode;
Node<String> childNode;
if (nodesByName.containsKey(parent)) {
parentNode = nodesByName.get(parent);
} else {
parentNode = new Node<String>(parent);
nodesByName.put(parent, parentNode);
}
if (nodesByName.containsKey(child)) {
childNode = nodesByName.get(child);
} else {
childNode = new Node<String>(child);
nodesByName.put(child, childNode);
}
if (parentNode != null && !parentNode.children.contains(childNode)) {
parentNode.addChild(childNode);
}
}
nodesByName.values().iterator().next().getRoot().dfsPrint();
}
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) {
this.parent = parent;
this.child = child;
}
}
public static class Node<T> {
private Node<T> parent;
private List<Node<T>> children = new ArrayList<>();
private T data;
public Node(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> addChild(T data) {
Node<T> node = new Node<>(data);
node.parent = this;
children.add(node);
return node;
}
public Node<T> addChild(Node<T> node) {
node.parent = this;
children.add(node);
return node;
}
public Node<T> getRoot() {
if (parent == null) {
return this;
} else {
return parent.getRoot();
}
}
public void dfsPrint() {
if (data != null) {
System.out.println(data.toString());
}
for (Node<T> child : children) {
child.dfsPrint();
}
}
}
}
O(1) memory, O(n) time, no sorting needed
- Eran Medan March 05, 2016