当前位置: 首页 > news >正文

佛山网站策划公司目前较好的crm系统

佛山网站策划公司,目前较好的crm系统,网页制作公司网站,网站做预览文档目录 LeetCode:198.打家劫舍 基本思路 C代码 LeetCode:213.打家劫舍II 基本思路 C代码 LeetCode:337.打家劫舍III 基本思路 C代码 LeetCode:198.打家劫舍 力扣题目链接 文字讲解:LeetCode:198.打家劫舍 视频讲解:动态规划,偷不偷这个…

目录

LeetCode:198.打家劫舍

基本思路

C++代码

LeetCode:213.打家劫舍II

基本思路

C++代码

LeetCode:337.打家劫舍III

基本思路

C++代码


LeetCode:198.打家劫舍

力扣题目链接

文字讲解:LeetCode:198.打家劫舍

视频讲解:动态规划,偷不偷这个房间呢?

基本思路

        看到这个问题,很容易想到,需要对当前房屋偷与不偷两种状态进行判断,而这个状态和前一个房间和前两个房间是否被偷有很大的关系

        通过动规五部曲进行分析:

  • 确定dp数组(dp table)以及下标的含义

        dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]

  • 确定递推公式

        首先决定dp[i]的因素就是第i房间偷还是不偷。而如果偷了第i个房间,那么其偷盗金额就和前两个房间有关;如果不偷第i个房间,显然dp[i]和前一个房间的金额相同。

        因此容易推出递推公式为:dp[i] = max(dp[i-1],dp[i-2]+nums[i]);

  • dp数组如何初始化

        因为题目明确说明街道上存在一个以上的房屋,当街道上只有一个房屋时,我们直接返回nums[0],如果大于等于两个房屋时,我们令dp[0]为nums[0],令dp[1] = max(nums[0],nums[1]);

  • 确定遍历顺序

        dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历!

for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
  • 举例推导dp数组

以示例二,输入[2,7,9,3,1]为例,红框dp[nums.size() - 1]为结果。

C++代码

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];vector<int> dp(nums.size());dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
};

LeetCode:213.打家劫舍II

力扣题目链接

文字讲解:LeetCode:213.打家劫舍II

视频讲解:动态规划,房间连成环了那还偷不偷呢?

基本思路

        这个题目相对于上一个题目,不同点在于街道上的房子练成了一个圈,那么我们到底应不应该选择第一个房屋和最后一个房屋呢?

        很容易想到可以分成三种情况:

  • 情况一:考虑不包含首尾元素

  • 情况二:考虑包含首元素,不包含尾元素

  • 情况三:考虑包含尾元素,不包含首元素

        而在情况二和情况三种我们提到可以考虑包含首尾元素,而不是一定包含,因此情况一的情形实际上是包含在情况二和情况三中的。

        这个样子我们和容易和上个题目中的动规五部曲进行相同的分析了。无非就是进行判断的区间有所不同。

C++代码

// 注意注释中的情况二情况三,以及把198.打家劫舍的代码抽离出来了
class Solution {
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);}// 198.打家劫舍的逻辑int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());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 - 2] + nums[i], dp[i - 1]);}return dp[end];}
};

LeetCode:337.打家劫舍III

力扣题目链接

文字讲解:LeetCode:337.打家劫舍III

视频讲解:动态规划,房间连成树了,偷不偷呢?

基本思路

        这个题目结合了二叉树的相关知识,如果忘记了的同学可以重新回顾一下二叉树相关的知识和题目。这个题目当然也可以使用二叉树递归的方法进行求解,但是我们知道二叉树的时间复杂度远大于动态规划的时间复杂度,这就很容易导致出现超时的情况。

        这道题目算是树形dp的入门题目,因为是在树上进行状态转移,我们在讲解二叉树的时候说过递归三部曲,那么下面我以递归三部曲为框架,其中融合动规五部曲的内容来进行讲解

  • 确定递归函数的参数和返回值

        我们需要传入的是根节点,而返回的是所能偷到的最大金额,因此返回值是int类型。对于每个二叉树节点,我们需要求出对于当前节点偷与不偷两个状态。我们还需要设置一个函数,用来记录每个节点偷与不偷状态下所能获得的最大金额。传入的为当前节点的指针,返回为一个数组。

int rob(TreeNode* root)
vector<int> robTree(TreeNode* cur)
  • 确定终止条件

        对二叉树的所有节点进行遍历,当节点为空节点时,表示无论是否偷空节点,偷到的金额都为零,此时返回{0,0}。

if (cur == NULL) return vector<int>{0, 0};
  • 确定遍历顺序

        因为是否偷当前节点需要根据是否偷左右孩子获得的最大金额决定。因此需要先遍历左右孩子,在遍历中间节点,即遍历方式采用后序遍历。

  • 确定单层递归的逻辑

        遍历当前节点时,如果偷当前节点,那么就不能偷左右孩子,即取left[0]和right[0];如果不偷当前节点,那么就对左右节点是否偷盗的可以获得的金额求最大值。

vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右// 偷cur
int val1 = cur->val + left[0] + right[0];
// 不偷cur
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};
  • 举例推导dp数组

        以示例1为例,dp数组状态如下:

        最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱

C++代码

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}// 长度为2的数组,0:不偷,1:偷vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);// 偷cur,那么就不能偷左右节点。int val1 = cur->val + left[0] + right[0];// 不偷cur,那么可以偷也可以不偷左右节点,则取较大的情况int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};
http://www.zhongyajixie.com/news/16903.html

相关文章:

  • 如何做自己官方网站百度做广告费用
  • 苗木网站模板互联网宣传方式有哪些
  • 动态网站制作教程百度号码认证平台官网首页
  • 哪些网站做推广营销培训内容有哪些
  • 网站做好了怎么办爱站网关键词挖掘工具熊猫
  • javaee做的是网站吗李江seo
  • 政府网站群建设sem是什么意思职业
  • 深圳建设局网站投诉电话网站推广优化服务
  • 咨询公司成本费用包括哪些内容网站seo设计
  • 国家建设材料检测网站免费推广
  • 网站开发发展方向北京营销型网站
  • 查做空运磁检的网站爱站网关键词查询工具
  • 创业网站模板免费下载直播代运营公司
  • 中国铁道工程建设协会查证网站如何建立企业网站
  • 佛山专业网站制作百度域名购买
  • 医院网站可信认证必须做吗专门做排名的软件
  • python做网站 要学多久360摄像头海澳門地区限制解除
  • 做外贸的如何上国外网站seo还有前景吗
  • 合肥网站建设开发电话郑州本地seo顾问
  • cad外包网站网推什么平台好用
  • 网站图片上传不上去怎么办产品软文范例
  • 网站建设公司的职责百度上广告怎么搞上去的
  • 可以做免费的网站吗吉林关键词排名优化软件
  • 让别人访问自己做的网站烘焙甜点培训学校
  • 内销网站要怎么做seo描述是什么意思
  • 绍兴柯桥建设局网站百度站长提交
  • gif网站banner怎么做免费培训seo网站
  • 哪个网站的域名到期直接注册表电商软文范例300字
  • 深圳做外贸网站如何做一个网站的seo
  • wordpress改网站logo网上销售方法