Commit50f293d

committed

house robber III

1 parent89a68de commit50f293dCopy full SHA for 50f293d

File tree

+52

-0

lines changed

+52

-0

lines changed

Lines changed: 8 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,8 @@`
	`1`	`+packageclasses;`
	`2`	`+`
	`3`	`+publicclassTreeNode {`
	`4`	`+publicintval;`
	`5`	`+publicTreeNodeleft;`
	`6`	`+publicTreeNoderight;`
	`7`	`+publicTreeNode(intx){this.val =x;}`
	`8`	`+}`

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,44 @@`
	`1`	`+packagemedium;`
	`2`	`+`
	`3`	`+importjava.util.HashMap;`
	`4`	`+importjava.util.Map;`
	`5`	`+`
	`6`	`+importclasses.TreeNode;`
	`7`	`+`
	`8`	`+publicclassHouseRobberIII {`
	`9`	`+`
	`10`	`+//simple recursion without cacheing: 1189 ms`
	`11`	`+publicintrob(TreeNoderoot) {`
	`12`	`+if(root ==null)return0;`
	`13`	`+`
	`14`	`+intval =0;`
	`15`	`+if(root.left !=null){`
	`16`	`+val +=rob(root.left.left) +rob(root.left.right);`
	`17`	`+ }`
	`18`	`+if(root.right !=null){`
	`19`	`+val +=rob(root.right.left) +rob(root.right.right);`
	`20`	`+ }`
	`21`	`+val =Math.max(val +root.val,rob(root.left) +rob(root.right));`
	`22`	`+returnval;`
	`23`	`+ }`
	`24`	`+`
	`25`	`+//same idea, but with cacheing via a hashmap: 8 ms`
	`26`	`+publicintrob_dp(TreeNoderoot) {`
	`27`	`+Map<TreeNode,Integer>map =newHashMap<TreeNode,Integer>();`
	`28`	`+returnget(root,map);`
	`29`	`+ }`
	`30`	`+`
	`31`	`+privateintget(TreeNoderoot,Map<TreeNode,Integer>map){`
	`32`	`+if(root ==null)return0;`
	`33`	`+if(map.containsKey(root))returnmap.get(root);`
	`34`	`+`
	`35`	`+intval =0;`
	`36`	`+if(root.left !=null)val +=get(root.left.left,map) +get(root.left.right,map);`
	`37`	`+if(root.right !=null)val +=get(root.right.left,map) +get(root.right.right,map);`
	`38`	`+intmax =Math.max(root.val +val,get(root.left,map) +get(root.right,map));`
	`39`	`+map.put(root,max);`
	`40`	`+returnmax;`
	`41`	`+ }`
	`42`	`+`
	`43`	`+`
	`44`	`+}`

Comments

(0)