【算法与数据结构】198、213、337LeetCode打家劫舍I, II, III

文章目录

  • 一、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 j=2开始。
  • 第五步，打印结果。
      程序如下：
// 198、打家劫舍，动态规划
class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> 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(vector<int>& 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(vector<int>& 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(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> 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 vector<int>{0, 0};
  • 3、确定遍历顺序。因为当前节点偷不偷需要根据左右孩子的返回值来进行判断，所以 我们需要先得到左右孩子的返回值，即先遍历左右孩子。在所有的遍历顺序中，只有后序遍历（左右中遍历顺序）满足。
	vector<int> left = robTree(cur->left); // 左
	vector<int> 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) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    vector<int> robTree(TreeNode* cur) {    // 返回一个二维数组， {0， 1} = {不偷的金额，偷的金额}
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> 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(vector<int>& nums) {
        vector<int> 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(vector<int>& 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(vector<int>& 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(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> 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() {
    vector<int> 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) {}
};

template<typename 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;
}

template<class 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(vector<string>& 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);             // 右
        }
    }
}

// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    if (root != NULL) que.push(root);
    vector<vector<int>> result;
    while (!que.empty()) {
        int size = que.size();  // size必须固定, que.size()是不断变化的
        vector<int> 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) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    vector<int> robTree(TreeNode* cur) {    // 返回一个二维数组， {0， 1} = {不偷的金额，偷的金额}
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> 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() {
    vector<string> t = { "3", "2", "NULL", "3", "NULL", "NULL", "3", "NULL", "1", "NULL", "NULL"};   // 前序遍历
    TreeNode* root = new TreeNode();    // 生成根节点
    Tree_Generator(t, root);            // 生成树
    vector<vector<int>> tree = levelOrder(root);    // 层序遍历
    my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");  // 打印层序遍历

    Solution s1;
    int result = s1.rob(root);
    cout << "最大金额为：" << result << endl;
    system("pause");
    return 0;
}

end

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/361148.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【蓝桥杯选拔赛真题62】python不重复字符最长子串 第十五届青少年组蓝桥杯python 选拔赛比赛真题解析

【蓝桥杯选拔赛真题62】python不重复字符最长子串 第十五届青少年组蓝桥杯python 选拔赛比赛真题解析

目录 python不重复字符最长子串 一、题目要求 1、编程实现 2、输入输出
阅读更多...
如何在Excel中清除单元格的格式？这里有详细步骤

如何在Excel中清除单元格的格式？这里有详细步骤

Microsoft Excel提供了大量样式选项来自定义电子表格的外观。但是&#xff0c;如果你需要删除格式&#xff0c;则可以很容易地删除选定单元格和整个工作表的格式。我们将向你展示如何操作。 ​注意&#xff1a;清除格式只会删除文本的样式&#xff1b;将保留你的实际文本。 如…
阅读更多...
Modern C++ std::get＜n＞(tuple)的原理

Modern C++ std::get＜n＞(tuple)的原理

1. 前言 前面我们讲过std::tuple的实现原理&#xff0c;但没有讲如何取出数据&#xff0c;本节着重讲讲这点。本节与之前的blog有较大关联&#xff0c;如果您没看&#xff0c;这里有链接&#xff0c;链接已按由浅入深排好序&#xff0c;您可以按顺序阅读。如果时间少可以直接看…
阅读更多...
安卓视图基础

安卓视图基础

目录 设置视图的宽高 设置视图的间隔 设置视图的对齐方式 设置视图的宽高 设置视图的间隔 设置视图的对齐方式 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"a…
阅读更多...
vue使用mpegts.js教程

vue使用mpegts.js教程

vue使用mpegts.js教程 最简单好用的H265网页播放器-mpegts.js简介特征受限性 使用步骤安装引入HTML 中添加视频标签video知识扩展 在容器里创建播放器 最简单好用的H265网页播放器-mpegts.js H265是新一代视频编码规范&#xff0c;与H264相比压缩比更高&#xff0c;同样的码率下…
阅读更多...
计算机网络-调度算法-2（时间片轮转 优先级调度算法 多级反馈队列调度算法 多级队列调度算法）

计算机网络-调度算法-2（时间片轮转 优先级调度算法 多级反馈队列调度算法 多级队列调度算法）

文章目录 总览时间片轮转时间片大小为2时间片大小为5若按照先来先服务算法 优先级调度算法例题&#xff08; 非抢占式优先级调度算法&#xff09;例题&#xff08; 抢占式优先级调度算法&#xff09;补充 思考多级反馈队列调度算法例题 小结多级队列调度算法 总览 时间片轮转 …
阅读更多...
ESP32 LED PWM 控制器

ESP32 LED PWM 控制器

ESP32 具有 LED PWM 控制器&#xff0c;具有 16 个独立通道&#xff0c;可配置为生成具有不同属性的 PWM 信号。 使用 Arduino IDE 通过 PWM 对 LED 进行调光时必须遵循以下步骤&#xff1a; 1.首先&#xff0c;您需要选择一个PWM通道。从 0 到 15 有 16 个通道&#xff0c;一…
阅读更多...
初谈C++：引用

初谈C++：引用

文章目录 前言概述引用特性应用场景做参数做返回值 传值、传引用效率比较引用和指针的区别 前言 在学习C语言的时候会遇到指针&#xff0c;会有一级指针、二级指针…很容易让人头昏脑胀。在C里面&#xff0c;引入了引用的概念&#xff0c;会减少对指针的使用。引用相当于给一个…
阅读更多...
【FFmpeg】ffplay 命令行参数 ① ( 设置播放分辨率 | 禁用 音频 / 视频 / 字幕 选项 )

【FFmpeg】ffplay 命令行参数 ① ( 设置播放分辨率 | 禁用 音频 / 视频 / 字幕 选项 )

文章目录 一、ffplay 命令行参数 - 设置播放分辨率1、强制设置通用播放分辨率 -x -y 参数2、命令行示例 - 正常播放视频3、命令行示例 - 强制设置播放分辨率4、设置 YUV 播放分辨率 -video_size 和 像素设置 -pixel_format5、全屏播放 -fs 参数 二、ffplay 命令行参数 - 禁用 音…
阅读更多...
跨境卖家：如何利用自养号测评抢占市场先机？

跨境卖家：如何利用自养号测评抢占市场先机？

在当今的跨境电商领域&#xff0c;产品的销量和评价是影响产品在市场上的表现的关键因素。对于卖家而言&#xff0c;自行养号进行产品测评不仅有助于提升销量&#xff0c;更成为了他们在这个竞争激烈的市场中保持竞争力的必备策略。 相较于一些卖家仍然依赖于服务商进行测评&a…
阅读更多...
【网络】 WireShark实现TCP三次握手和四次挥手

【网络】 WireShark实现TCP三次握手和四次挥手

目录 一、WireShark介绍 二、什么是TCP 三、TCP三次握手 四、TCP四次挥手 一、WireShark介绍 WireShark是一个开源的网络分析工具&#xff0c;用于捕获和分析网络数据包。它可以在多个操作系统上运行&#xff0c;包括Windows、Mac OS和Linux。 使用WireShark&#xff0c;…
阅读更多...
【体验有奖】5 分钟函数计算部署 AI 艺术字应用，晒姓氏头像赢 Cherry 键盘！

【体验有奖】5 分钟函数计算部署 AI 艺术字应用，晒姓氏头像赢 Cherry 键盘！

作者&#xff1a;姜曦&#xff08;筱姜&#xff09; 目前&#xff0c;大多数开发者使用的 AI 绘画项目 Stable Diffusion WebUI 难以适应企业多用户、多场景的复杂需求&#xff0c;用户急需一套成熟解决方案去进行基于 Stable Diffusion 的 AI 绘画创业&#xff0c;本实验基于…
阅读更多...
【lesson3】高并发内存池的三层框架介绍

【lesson3】高并发内存池的三层框架介绍

文章目录 高并发内存池需要考虑的问题高并发内存池的3个核心部分thread cachecentral cachepage cache 高并发内存池需要考虑的问题 现代很多的开发环境都是多核多线程&#xff0c;在申请内存的场景下&#xff0c;必然存在激烈的锁竞争问题。malloc本身其实已经很优秀&#xf…
阅读更多...
代码随想录 Leetcode538. 把二叉搜索树转换为累加树

代码随想录 Leetcode538. 把二叉搜索树转换为累加树

题目&#xff1a; 代码(首刷看解析 2024年1月31日&#xff09;&#xff1a; class Solution { public:int pre 0;TreeNode* convertBST(TreeNode* root) {if (!root) return nullptr;root->right convertBST(root->right);if (pre 0) {pre root->val;}else {root…
阅读更多...
万物简单AIoT 端云一体实战案例学习 之 智能小车

万物简单AIoT 端云一体实战案例学习 之 智能小车

学物联网，来万物简单IoT物联网！！ 下图是本案的3步导学，每个步骤中实现的功能请参考图中的说明。 1、简介 1.1、背景 市面上各种遥控的小车很多，小车的性能不同具备的能力也不一样，大概实现的逻辑就是通过遥控器控制小车的前进、后退、左转或者右转。遥控小车具备一定…
阅读更多...
【lesson4】高并发内存池ThreadCache（线程缓存）层实现

【lesson4】高并发内存池ThreadCache（线程缓存）层实现

文章目录 ThreadCache层的结构申请内存逻辑释放内存逻辑自由链表的实现自由链表的成员变量自由链表的成员函数自由链表的完整实现 ThreadCache申请内存过程的实现ThreadCache需要的成员变量ThreadCache需要的成员函数ThreadCache.h文件代码Allocate的实现Deallocate的实现 封装…
阅读更多...
实验3：利用Linux的消息队列通信机制实现三个线程间的通信

实验3：利用Linux的消息队列通信机制实现三个线程间的通信

调用原型 POSIX信号量–无名信号量 POSIX信号量是Pthread线程库提供的一种同步机制&#xff0c;包括无名信号量和有名信号量两种机制。无名信号量&#xff0c;常用于多线程间的同步&#xff0c;也可用于相关进程间的同步&#xff08;需置于相关进程间的共享内存区中&#xff…
阅读更多...
自定义vue通用左侧菜单组件（未完善版本）

自定义vue通用左侧菜单组件（未完善版本）

使用到的技术&#xff1a; vue3、pinia、view-ui-plus 实现的功能&#xff1a; 传入一个菜单数组数据&#xff0c;自动生成一个左侧菜单栏。菜单栏可以添加、删除、展开、重命名&#xff0c;拖动插入位置等。 效果预览&#xff1a; 代码&#xff1a; c-menu-wrap.vue <t…
阅读更多...
模拟电路之运放

模拟电路之运放

滞回比较器&#xff1a; 小幅度波动时候不受影响&#xff0c;除非超过一点范围 当输入信号慢慢增加到UT&#xff0c;就变成负电压 当输入信号慢慢减压到—UT&#xff0c;就变成正电压 电路反向接信号 正反馈&#xff0c;串联电阻接地 调整回差的方法 1.调整电阻的分压 2.…
阅读更多...
学习在微信小程序使用富文本修改图片大小的代码，超简单

学习在微信小程序使用富文本修改图片大小的代码，超简单

学习在微信小程序使用富文本修改图片大小的代码&#xff0c;超简单 前言代码 前言 自带img图片或大或小&#xff0c;不适应小程序页面 代码 1、replace方法全局添加图片img标签的style样式 let txt www.qipa250.com //富文本内容 txt txt.replace(/<img/gi,<img s…
阅读更多...
最新文章

Copyright @ 2022~2023