diff options
| -rw-r--r-- | CourseSchedule.java | 46 | ||||
| -rw-r--r-- | NumberOfIslands.java | 38 |
2 files changed, 61 insertions, 23 deletions
diff --git a/CourseSchedule.java b/CourseSchedule.java index 5b5ed02..6f85f44 100644 --- a/CourseSchedule.java +++ b/CourseSchedule.java @@ -3,9 +3,26 @@ import java.util.*; import node.*; class CourseSchedule { - public static boolean canFinish(int[][] prerequisites) { - GraphNode node = createGraph(prerequisites); - return !detectCycle(node); + public static boolean detectCycle(GraphNode node) { + Stack<GraphNode> stack = new Stack<GraphNode>(); + ArrayList<GraphNode> visited = new ArrayList<GraphNode>(); + stack.push(node); + while (!stack.empty()) { + node = stack.pop(); + if (visited.contains(node)) { + System.out.println("Cycle " + node.val); + return true; + } + visited.add(node); + System.out.println("Node: " + node.val); + System.out.print("Neighbors: "); + for (GraphNode neighbor : node.neighbors) { + stack.push(neighbor); + System.out.print(neighbor.val + " "); + } + System.out.println(); + } + return false; } public static GraphNode createGraph(int[][] prerequisites) { @@ -31,26 +48,9 @@ class CourseSchedule { return map.get(1); } - public static boolean detectCycle(GraphNode node) { - Stack<GraphNode> stack = new Stack<GraphNode>(); - ArrayList<GraphNode> visited = new ArrayList<GraphNode>(); - stack.push(node); - while (!stack.empty()) { - node = stack.pop(); - if (visited.contains(node)) { - System.out.println("Cycle " + node.val); - return true; - } - visited.add(node); - System.out.println("Node: " + node.val); - System.out.print("Neighbors: "); - for (GraphNode neighbor : node.neighbors) { - stack.push(neighbor); - System.out.print(neighbor.val + " "); - } - System.out.println(); - } - return false; + public static boolean canFinish(int[][] prerequisites) { + GraphNode node = createGraph(prerequisites); + return !detectCycle(node); } public static void main(String[] args) { diff --git a/NumberOfIslands.java b/NumberOfIslands.java new file mode 100644 index 0000000..422b80e --- /dev/null +++ b/NumberOfIslands.java @@ -0,0 +1,38 @@ +import java.lang.*; +import java.util.*; + +class NumberOfIslands { + public static void setZero(int y, int x, int[][] grid) { + if (y < 0 || y > grid.length - 1 || x < 0 || x > grid[0].length - 1 || grid[y][x] == 0) + return; + grid[y][x] = 0; + System.out.println("y: " + y + " x: " + x); + setZero(y, x + 1, grid); + setZero(y + 1, x, grid); + setZero(y, x - 1, grid); + setZero(y - 1, x, grid); + } + + public static int numIslands(int[][] grid) { + int num = 0; + for (int y = 0; y < grid.length; y++) { + for (int x = 0; x < grid[y].length; x++) { + if (grid[y][x] == 1) { + num++; + setZero(y, x, grid); + } + } + } + return num; + } + + public static void main(String[] args) { + int[][] grid = { + {1,1,1,1,0}, + {1,1,0,1,0}, + {1,1,0,0,0}, + {0,0,0,1,1} + }; + System.out.println(numIslands(grid)); + } +} |