Leetcode 198/213/337 House Robber

本文主要是介绍Leetcode 198/213/337 House Robber，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

198.

已知是非负数组，小偷去抢，偷完一家后，不能再偷邻居，即不能拿隔壁的。 

没有排序，没有连续

s0=H0=1;

S1=max(S0,H1)=2

S2=max(S1,S0+H2)=4;

S3=max(s2,S1+H3)=4;

Sn= max(Sn-1,Sn-2+Hn);

=============solution. (因为只有遍历）

public solution{

　　public int rob(int[] nums){

　　　　int n=nums.length;

　　　　if(n==0) return 0;

　　　　if(n==1) return nums[0];

　　　　int second= Math.max(nums[0],nums[1]);

　　　　for(int i=2;i<n;i++)[

　　　　　　int tmp=second;

　　　　　　second=Math.max(second,first+nums[i]);

　　　　　　first=tmp

　　　　}

　　　　return second;

}

}

Time O(n), Space O(1)

==============

213。House Robber 2

题目中变成了环  circle;

class Solution{

　　public int rob(int[] nums){

　　　　if(nums==null||nums.length==0) return 0;

　　　　if(nums.length==1) return nums[0];

　　　　int res1=helper(nums,0,nums.length-2);

　　　　int res2= helper(nums,1,nums.length-1);

　　　　return Math.max(res1,res2);

}

　　　private int helper(int[] nums,int start, int end){

　　　　　　if(start==end) return nums[start];

　　　　　　if(end-start==1) return math.max(nums[start],nums[end]);

　　　　　　int[] dp= new int[end-start+1];

　　　　　　dp[0]=nums[start];

　　　　　　dp[1]= Math.max(nums[start],nums[start+1]);

　　　　　　for (int i=2;i<dp.length;i++){

　　　　　　　　　dp[i]=Math.max(dp[i-2]+nums[start+i],dp[i-2]);

}

return. dp[dp.length-1];

}
}

==================================================

337. House Robber 3. 

基于树结构的房间分布，然后偷钱；

思路一：直接从头部取，分别识别左节点的value, 有节点的value; 但这一方法是超时的。

于是有了从postorder的方法。

public int rob(TreeNode root){

　　int[] res=robSob(root);

　　return Math.max(res[0],res[1]);

}

private int[] robSob(TreeNode root){

　　　if(root==null) return new int[2];

　　　int[] left= rubSob(root.left);

　　　int[] right=rubSob(root.right);

　　　　int[] res= new int[2];

　　　　res[0]=Math.max(left[0],left[1])+ Math.max(right[0],right[1]);

　　　　res[1]=root.val+left[0]+right[0];

　　　　return res;

}

}

这篇关于Leetcode 198/213/337 House Robber的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！