【力扣】[力扣热题HOT100] 337.打家劫舍|||
2021/7/4 23:20:26
本文主要是介绍【力扣】[力扣热题HOT100] 337.打家劫舍|||,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、题目
在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
链接:https://leetcode-cn.com/problems/house-robber-iii/
2、思路解析
1)暴力求解法
首先考虑健壮性的问题,检测当前结点和左右子树是否为空。
其次考虑当前结点被偷,则它的结点的左右子树必定不会被偷,则其孙子子树一定会被偷。
如果当前结点不被偷,则其左右子树一定被偷。
最终返回算出来大的结果
class Solution { public: int rob(TreeNode* root) { // 时间复杂度过大 // 健壮性检测 if(root == nullptr) return 0; if(root->left == nullptr && root->right == nullptr) return root->val; // 偷当前的 int val1 = root->val; if(root->left) val1 += rob(root->left->left) + rob(root->left->right); if(root->right) val1 += rob(root->right->left) +rob(root->right->right); // 不偷当前的 int val2 = rob(root->left) +rob(root->right); // 返回较大的一个 return max(val1, val2); } };
2)哈希表提高时间复杂度
利用哈希以该节点被偷的金额数记录下来,下次遇到的情况,则直接返回哈希表中的金额数即可。
class Solution { public: unordered_map<TreeNode*, int> map; // 记录已经遍历过的 int rob(TreeNode* root) { if(root == nullptr) return 0; if(root->left == nullptr && root->right == nullptr) return root->val; // 偷当前的 int val1 = root->val; if(root->left) val1 += rob(root->left->left) + rob(root->left->right); if(root->right) val1 += rob(root->right->left) +rob(root->right->right); if(map[root]) return map[root]; // 不偷当前的 int val2 = rob(root->left) +rob(root->right); map[root] = max(val1, val2); // 记录的是当前结点算出来的是偷盗的最大金额数 // 返回较大的一个 return max(val1, val2); };
3)动态规划
用哈希表记录该节点 f 表示被偷,g记录该节点不会被偷
当前结点(o)被偷,则其子节点一定不会被偷,即:f(o) = g(o->left) + g(o->right);
当该节点不被偷,则其子节点一定被偷,即:g(o) = f(o->left) + f(o->right);
我们用哈希表存储f,g函数的值,然后深度优先搜索遍历二叉树,得到每一个结点的 f 和 g,因此根节点的 f 和 g 就是最大的值。
class Solution { public: unordered_map<TreeNode*, int> f, g; void dfs(TreeNode* root) { if(!root) return; dfs(root->left); dfs(root->right); f[root] = root->val + g[root->left] + g[root->right]; g[root] = max(f[root->left], g[root->left]) + max(g[root->right], f[root->right]); } int rob(TreeNode* root) { dfs(root); return max(f[root], g[root]); } };
这篇关于【力扣】[力扣热题HOT100] 337.打家劫舍|||的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)