Leetcode 198/213/337 House Robber
2022/7/16 6:20:10
本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升