Commitab123e9

committed

add a solution for 841

1 parenta464cde commitab123e9Copy full SHA for ab123e9

File tree

+41

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _841.java
- test/java/com/fishercoder
  - _841Test.java

+41

-0

lines changed

Lines changed: 37 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -58,4 +58,41 @@ public boolean canVisitAllRooms(List<List<Integer>> rooms) {`
`58`	`58`	`returnfalse;`
`59`	`59`	`}`
`60`	`60`	`}`
	`61`	`+`
	`62`	`+publicstaticclassSolution3 {`
	`63`	`+/**`
	`64`	`+ * My completely original recursive solution.`
	`65`	`+ */`
	`66`	`+publicbooleancanVisitAllRooms(List<List<Integer>>rooms) {`
	`67`	`+Set<Integer>visited =newHashSet<>();`
	`68`	`+visited.add(0);`
	`69`	`+Set<Integer>keys =newHashSet<>();`
	`70`	`+keys.addAll(rooms.get(0));`
	`71`	`+returndfs(rooms,visited,keys);`
	`72`	`+ }`
	`73`	`+`
	`74`	`+privatebooleandfs(List<List<Integer>>rooms,Set<Integer>visited,Set<Integer>keys) {`
	`75`	`+if (visited.size() ==rooms.size()) {`
	`76`	`+returntrue;`
	`77`	`+ }`
	`78`	`+Set<Integer>newKeys =newHashSet<>();`
	`79`	`+for (intkey :keys) {`
	`80`	`+if (!visited.contains(key)) {`
	`81`	`+visited.add(key);`
	`82`	`+if (!rooms.get(key).isEmpty()) {`
	`83`	`+newKeys.addAll(rooms.get(key));`
	`84`	`+ }`
	`85`	`+ }`
	`86`	`+ }`
	`87`	`+if (visited.size() ==rooms.size()) {`
	`88`	`+returntrue;`
	`89`	`+ }`
	`90`	`+if (newKeys.size() ==0) {`
	`91`	`+returnfalse;`
	`92`	`+ }`
	`93`	`+keys.addAll(newKeys);`
	`94`	`+dfs(rooms,visited,keys);`
	`95`	`+returnvisited.size() ==rooms.size();`
	`96`	`+ }`
	`97`	`+ }`
`61`	`98`	`}`

Lines changed: 4 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -13,12 +13,14 @@`
`13`	`13`	`publicclass_841Test {`
`14`	`14`	`privatestatic_841.Solution1solution1;`
`15`	`15`	`privatestatic_841.Solution2solution2;`
	`16`	`+privatestatic_841.Solution3solution3;`
`16`	`17`	`privatestaticList<List<Integer>>rooms;`
`17`	`18`
`18`	`19`	`@BeforeClass`
`19`	`20`	`publicstaticvoidsetup() {`
`20`	`21`	`solution1 =new_841.Solution1();`
`21`	`22`	`solution2 =new_841.Solution2();`
	`23`	`+solution3 =new_841.Solution3();`
`22`	`24`	`}`
`23`	`25`
`24`	`26`	`@Test`
`@@ -30,6 +32,7 @@ public void test1() {`
`30`	`32`	`rooms.add(Arrays.asList());`
`31`	`33`	`assertEquals(true,solution1.canVisitAllRooms(rooms));`
`32`	`34`	`assertEquals(true,solution2.canVisitAllRooms(rooms));`
	`35`	`+assertEquals(true,solution3.canVisitAllRooms(rooms));`
`33`	`36`	`}`
`34`	`37`
`35`	`38`	`@Test`
`@@ -41,5 +44,6 @@ public void test2() {`
`41`	`44`	`rooms.add(Arrays.asList(0));`
`42`	`45`	`assertEquals(false,solution1.canVisitAllRooms(rooms));`
`43`	`46`	`assertEquals(false,solution2.canVisitAllRooms(rooms));`
	`47`	`+assertEquals(false,solution3.canVisitAllRooms(rooms));`
`44`	`48`	`}`
`45`	`49`	`}`

Comments

(0)