My Java O(n) solution without Math library and coping arrays


  • 0
    S

    To explain my algorithm, if thief decides to rob house n, the accumulated amount will depends on whether he previously robbed house n - 2 or n - 3, since he cannot rob house n - 1. And it doesn't make sense if he doesn't rob either n - 2 or n - 3, for example, he rob n - 4 instead.

    n-2 --->
                   ---> n
    n-3 --->
    
    public class Solution {
        public int rob(int[] num) {
            if(num != null) {
                if(num.length == 0)
                    return 0;
                if(num.length == 1)
                    return num[0];
                if(num.length == 2)
                    return (num[0] > num[1]) ? num[0] : num[1];
                
                if(num.length > 2){
                    //now the num array denotes the max amount the thief could rob so far if this house is chosen to be robbed
                    num[2] += num[0];
                    for(int i = 3; i< num.length; i++) {
                        num[i] += (num[i-2] > num[i-3]) ? num[i-2] : num[i-3];
                    }
                    return (num[num.length - 1] > num[num.length - 2]) ? num[num.length - 1] : num[num.length - 2];
                }
            }
            return 0;
        }
    }

  • 0
    Q

    Nice solution. I made this into much harder graph generation/traversal problem.

    public class Solution{
          private class Node{
    		Node left;
    		Node right;
    		int value;
    		boolean visited = false;
    		int accumVal;
    	}
    	
    
    	public int rob(int[] num) {
    		if (num == null) {
    			return 0;
    		}
    		if (num.length == 1) {
    			return num[0];
    		}
    		if (num.length == 2) {
    			return Math.max(num[0], num[1]);
    		}
    
    		Node n = new Node();
    		Map<Integer,Node> nodesUsed = new HashMap<Integer,Node>();
    		
    		buildTree(n, num, 0, nodesUsed);
    		calculateMax(n,  0);
    		
    		return n.accumVal;
    	}
    
    	private int calculateMax(Node n, int val){
    		Node left = n.left;
    		Node right = n.right;
    		if (left == null && right == null){
    			n.accumVal = n.value;
    			return n.value;
    		}
    		int val1 = 0;
    		int val2 = 0;
    		if (left!=null){
    			if (left.visited == false){
    				val1 = calculateMax(left,  val+n.value);
    				left.visited = true;
    			}
    			else{
    				val1 = left.accumVal;
    			}
    		}
    		if (right!=null){
    			if (right.visited == false){
    				val2 = calculateMax(right, val+n.value);
    				right.visited = true;
    			}
    			else{
    				val2 = right.accumVal;
    			}
    		}
    		n.accumVal = n.value+Math.max(val1,val2);
    		return n.accumVal;
    	}
    	
    	private void buildTree(Node parent, int[]num, int index, Map<Integer,Node> nodesUsed){
    		if (num.length-index>1){
    			int val1 = num[index];
    			int val2 = num[index+1];
    			
    			Node node1 = nodesUsed.get(index);
    			Node node2 = nodesUsed.get(index+1);
    			
    			boolean justBuilt1 = false;
    			boolean justBuilt2 = false;
    			if (node1 == null){
    				node1 = new Node();
    				node1.value = val1;
    				nodesUsed.put(index, node1);
    				justBuilt1 = true;
    			}
    			if (node2 == null){
    				node2 = new Node();
    				node2.value = val2;
    				nodesUsed.put(index+1, node2);
    				justBuilt2 = true;
    			} 
    
    			parent.left=node1;
    			parent.right=node2;
    			
    			
    			if (justBuilt1){
    				buildTree(node1,num, index+2, nodesUsed);
    			}
    			if (justBuilt2){
    				buildTree(node2, num, index+3, nodesUsed);
    			}
    			
    		}
    		else if (num.length-index == 1){
    			Node n = nodesUsed.get(index);
    			if (n == null){
    				int val = num[index];
    				n = new Node();
    				n.value = val;
    			}
    			parent.left = n;
    		}
    	}
    }

  • 0
    F

    brilliant solution


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.