免费信息推广网站,宿迁seo,推广普通话的意义30字,网页设计与制作思政教学设计文章目录 一、198、打家劫舍二、213、打家劫舍 II三、337、打家劫舍III三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、198、打家劫舍 思路分析#xff1a;打家劫舍是动态规划的的经典题目。本题的难点在于递归公式… 文章目录 一、198、打家劫舍二、213、打家劫舍 II三、337、打家劫舍III三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、198、打家劫舍 思路分析打家劫舍是动态规划的的经典题目。本题的难点在于递归公式和初始化。
第一步 d p [ j ] dp[j] dp[j]的含义。 d p [ j ] dp[j] dp[j]代表到第 j j j家的时候偷窃到的最高金额。第二步递推公式。 d p [ j ] dp[j] dp[j]仅仅与 d p [ j − 1 ] dp[j-1] dp[j−1]和 d p [ j − 2 ] dp[j-2] dp[j−2]有关。如果不偷第 j j j家则偷窃金额不变 d p [ j ] d p [ j − 1 ] dp[j] dp[j-1] dp[j]dp[j−1]。如果偷第 j j j家那么偷窃金额在 d p [ j − 2 ] dp[j-2] dp[j−2]基础上加上 n u m s [ i ] nums[i] nums[i]即 d p [ j ] d p [ j − 2 ] n u m s [ i ] dp[j] dp[j-2] nums[i] dp[j]dp[j−2]nums[i]。综合二者 d p [ j ] m a x ( d p [ j − 1 ] , d p [ j − 2 ] n u m s [ i ] ) dp[j] max(dp[j-1], dp[j-2] nums[i]) dp[j]max(dp[j−1],dp[j−2]nums[i])。第三部元素初始化。 d p [ 0 ] dp[0] dp[0]初始化为0代表还没开始偷窃 d p [ 1 ] dp[1] dp[1]初始化为 n u m [ 0 ] num[0] num[0]。第四部递归顺序。循环从 j 2 j 2 j2开始。第五步打印结果。 程序如下
// 198、打家劫舍动态规划
class Solution {
public:int rob(vectorint nums) {vectorint dp(nums.size() 1, 0);dp[1] nums[0];for (int i 2; i nums.size(); i) {dp[i] max(dp[i - 1], dp[i - 2] nums[i-1]);}return dp[nums.size()];}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。 因为只用到了dp数组的最后一个元素实际上不需要保存所有的元素。因此对上述代码进行内存优化将空间复杂度降低到 O ( 1 ) O(1) O(1)但是递归的过程不明显找bug费劲。
// 198、打家劫舍动态规划-内存优化
class Solution2 {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];int first nums[0], second max(nums[0], nums[1]);for (int i 2; i nums.size(); i) {int temp second;second max(second, first nums[i]);first temp;}return second;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。
二、213、打家劫舍 II 思路分析本题是打家劫舍I的升级版要求第一家和最后一家是连着的不能同时偷。这是一个非此即彼的问题。要么偷第一家不偷最后一家这等于将最后一家排除在外。反之不偷第一家偷最后一家等价于将第一家排除在外。假设第一家的下标为 0 0 0最后一家的下标为 i − 1 i-1 i−1那么一共有两种情况偷窃范围 [ 0 , i − 2 ] [0, i - 2] [0,i−2]偷窃范围 [ 1 , i − 1 ] [1, i - 1] [1,i−1]。然后应用打家劫舍I的思路来做即可。以下是动态规划的代码内存优化版本就没给出了思路都是一样的。 程序如下
// 213、打家劫舍II动态规划
class Solution3 {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];int result1 robRange(nums, 0, nums.size() - 2);int result2 robRange(nums, 1, nums.size() - 1);return max(result1, result2);}int robRange(vectorint nums, int start, int end) {if (end start) return nums[start];vectorint dp(nums.size(), 0);dp[start] nums[start];dp[start 1] max(nums[start], nums[start 1]);for (int i start 2; i end; i) {dp[i] max(dp[i - 1], dp[i - 2] nums[i - 1]);}return dp[end];}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。
三、337、打家劫舍III 思路分析本题是打家劫舍I的变体原题目中的数组变成了二叉树。本题涉及到树形递归和动态规划我们就结合递归三部曲和动态规划五步骤
1、返回值和递归参数。我们需要判断一个节点要不要偷而偷不偷取决于动作带来的收益。因此我们需要返回一个节点偷与不偷的两个状态所得的金额。这就是一个长度为2的数组。这里我们假设这个二维数组第一个元素代表不偷的收益第二个元素代表偷的收益{ 0 , 1 不偷的收益偷的收益 {0, 1} {不偷的收益偷的收益} 0,1不偷的收益偷的收益}。输入参数是当前节点。2、确定终止条件。当遇到空节点就返回空节点不会带来收益。因此返{ 0 , 0 {0,0} 0,0}。 if (cur NULL) return vectorint{0, 0};3、确定遍历顺序。因为当前节点偷不偷需要根据左右孩子的返回值来进行判断所以 我们需要先得到左右孩子的返回值即先遍历左右孩子。在所有的遍历顺序中只有后序遍历左右中遍历顺序满足。 vectorint left robTree(cur-left); // 左vectorint right robTree(cur-right); // 右4、确定单层递归逻辑。对于当前节点来说只有两个情况。如果偷当前节点那么左右孩子节点就不能偷偷的收益左孩子不偷的收益右孩子不偷的收益。如果不偷当前节点那么左右孩子节点可偷可不偷至于究竟偷不偷就看那个收益大注意偷的收益未必更大偷了小的金额旁边大的金额就偷不了。不偷的收益 max左孩子不偷的收益左孩子偷的收益max右孩子不偷的收益右孩子偷的收益。将文字抽象成公式 int val1 cur-val left[0] right[0]; // 偷当前节点那么左右孩子节点不能偷int val2 max(left[0], left[1]) max(right[0], right[1]); // 不偷当前节点那么左右孩子节点可以偷也可以不偷取决于偷或者是不偷的金额。5、具体示例推导dp数组验证。 程序如下
// 337、打家劫舍III动态规划
class Solution {
public:int rob(TreeNode* root) {vectorint result robTree(root);return max(result[0], result[1]);}vectorint robTree(TreeNode* cur) { // 返回一个二维数组 {0 1} {不偷的金额偷的金额}if (cur NULL) return vectorint{0, 0};vectorint left robTree(cur-left);vectorint right robTree(cur-right);int val1 cur-val left[0] right[0]; // 偷当前节点那么左右孩子节点不能偷int val2 max(left[0], left[1]) max(right[0], right[1]); // 不偷当前节点那么左右孩子节点可以偷也可以不偷取决于偷或者是不偷的金额。return { val2, val1 };}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)每个节点只遍历了一次。空间复杂度 O ( l o g n ) O(log n) O(logn)算上递推系统栈的空间。
三、完整代码
// 打家劫舍I, II
# include iostream
# include vector
# include algorithm
using namespace std;// 198、打家劫舍动态规划
class Solution {
public:int rob(vectorint nums) {vectorint dp(nums.size() 1, 0);dp[1] nums[0];for (int i 2; i nums.size(); i) {dp[i] max(dp[i - 1], dp[i - 2] nums[i-1]);}return dp[nums.size()];}
};// 198、打家劫舍动态规划-内存优化
class Solution2 {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];int first nums[0], second max(nums[0], nums[1]);for (int i 2; i nums.size(); i) {int temp second;second max(second, first nums[i]);first temp;}return second;}
};// 213、打家劫舍II动态规划
class Solution3 {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];int result1 robRange(nums, 0, nums.size() - 2);int result2 robRange(nums, 1, nums.size() - 1);return max(result1, result2);}int robRange(vectorint nums, int start, int end) {if (end start) return nums[start];vectorint dp(nums.size(), 0);dp[start] nums[start];dp[start 1] max(nums[start], nums[start 1]);for (int i start 2; i end; i) {dp[i] max(dp[i - 1], dp[i - 2] nums[i - 1]);}return dp[end];}
};int main() {vectorint nums { 1,2,3,1 };Solution3 s1;int result s1.rob(nums);cout result endl;system(pause);return 0;
}// 337、打家劫舍III
# include iostream
# include vector
# include string
# include queue
using namespace std;// 树节点定义
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};templatetypename T
void my_print(T v, const string msg)
{cout msg endl;for (class T::iterator it v.begin(); it ! v.end(); it) {cout *it ;}cout endl;
}templateclass T1, class T2
void my_print2(T1 v, const string str) {cout str endl;for (class T1::iterator vit v.begin(); vit v.end(); vit) {for (class T2::iterator it (*vit).begin(); it (*vit).end(); it) {cout *it ;}cout endl;}
}// 前序遍历迭代法创建二叉树每次迭代将容器首元素弹出弹出代码还可以再优化
void Tree_Generator(vectorstring t, TreeNode* node) {if (!t.size() || t[0] NULL) return; // 退出条件else {node new TreeNode(stoi(t[0].c_str())); // 中if (t.size()) {t.assign(t.begin() 1, t.end());Tree_Generator(t, node-left); // 左}if (t.size()) {t.assign(t.begin() 1, t.end());Tree_Generator(t, node-right); // 右}}
}// 层序遍历
vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorvectorint result;while (!que.empty()) {int size que.size(); // size必须固定, que.size()是不断变化的vectorint vec;for (int i 0; i size; i) {TreeNode* node que.front();que.pop();vec.push_back(node-val);if (node-left) que.push(node-left);if (node-right) que.push(node-right);}result.push_back(vec);}return result;
}// 337、打家劫舍III动态规划
class Solution {
public:int rob(TreeNode* root) {vectorint result robTree(root);return max(result[0], result[1]);}vectorint robTree(TreeNode* cur) { // 返回一个二维数组 {0 1} {不偷的金额偷的金额}if (cur NULL) return vectorint{0, 0};vectorint left robTree(cur-left);vectorint right robTree(cur-right);int val1 cur-val left[0] right[0]; // 偷当前节点那么左右孩子节点不能偷int val2 max(left[0], left[1]) max(right[0], right[1]); // 不偷当前节点那么左右孩子节点可以偷也可以不偷取决于偷或者是不偷的金额。return { val2, val1 };}
};int main() {vectorstring t { 3, 2, NULL, 3, NULL, NULL, 3, NULL, 1, NULL, NULL}; // 前序遍历TreeNode* root new TreeNode(); // 生成根节点Tree_Generator(t, root); // 生成树vectorvectorint tree levelOrder(root); // 层序遍历my_print2vectorvectorint, vectorint(tree, 目标树:); // 打印层序遍历Solution s1;int result s1.rob(root);cout 最大金额为 result endl;system(pause);return 0;
}end
