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

做爰视频网站直播软件有哪些平台

做爰视频网站,直播软件有哪些平台,做有搜索功能的网站,centos 如何建立网站leetcode 198.打家劫舍 题目链接:198. 打家劫舍 - 力扣(LeetCode) 视频链接:动态规划,偷不偷这个房间呢?| LeetCode:198.打家劫舍_哔哩哔哩_bilibili 题目概述 你是一个专业的小偷,…

leetcode 198.打家劫舍

题目链接:198. 打家劫舍 - 力扣(LeetCode)

视频链接:动态规划,偷不偷这个房间呢?| LeetCode:198.打家劫舍_哔哩哔哩_bilibili

题目概述

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路

本题只说不能相邻两个房间偷,所以说只要不是相邻两个房间的话,不论你选择第几个房间都可以,只要偷的钱最多就好,没有太多限制因素。

依旧是动规五部曲

1.确定dp数组含义:

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

2.确定递推公式:

偷i:dp[i]=nums[i]+dp[i-2]

不偷i:dp[i]=dp[i-1]

所以递推公式:dp[i]=max(nums[i]+dp[i-2],dp[i-1])。

3.数组初始化:

dp[0]=nums[0]

dp[1]=max(nums[0],nums[1])

4.确定遍历顺序:

从前向后

5.打印dp数组:

198.打家劫舍

 

代码实现 

lass 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

题目链接:213. 打家劫舍 II - 力扣(LeetCode)

视频链接:动态规划,房间连成环了那还偷不偷呢?| LeetCode:213.打家劫舍II_哔哩哔哩_bilibili

题目概述

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 3:

输入:nums = [1,2,3]
输出:3

思路

其实本题和上题差不多,就是本题变成了一个环,不利于思考。但是,我们可以把环拆成一个线性数组,那么就会有三种情况:(考虑只是考虑,并不一定会偷)

1.考虑不包含首尾元素,如图所示:

213.打家劫舍II

2.考虑包含首元素,如图所示:

213.打家劫舍II1

3.考虑包含尾元素,如图所示:

213.打家劫舍II2

 第二种和第三种情况把第一种情况包含了,所以本题只是把数组做了一个截取,传进主函数去取最大值而已。

代码实现 

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

题目链接:337. 打家劫舍 III - 力扣(LeetCode)

视频链接:动态规划,房间连成树了,偷不偷呢?| LeetCode:337.打家劫舍3_哔哩哔哩_bilibili

题目概述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为  root。

除了root 之外,每栋房子有且只有一个"父"房子与之相连。一番侦察之后,聪明的小偷意识到"这个地方的所有房屋的排列类似于一棵二叉树"。如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

在不触动警报的情况下 ,小偷能够盗取的最高金额 。

 

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

思路

这道题目算是树形dp的入门题目,以递归三部曲加动规五部曲来讲:

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

返回值:一个长度为2的数组。

确定dp数组含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。

2.确定终止条件

遇空就返回。

3.确定遍历顺序

后序遍历

4.确定单层递归的逻辑

当前节点偷:val1 = cur->val + left[0] + right[0]

当前节点不偷:val2 = max(left[0], left[1]) + max(right[0], right[1])

5.举例推导dp数组

 

代码实现 

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.yayakq.cn/news/72091/

相关文章:

  • 用wordpress仿一个网站模板网站开发培训光山
  • 水禾田网站建设公司网站建设培训西安
  • 怎么增加网站权重专用车网站建设哪家好
  • 网盘做网站福州搜索优化行业
  • 网站建设优化服务平台意大利 网站设计
  • 口碑好的专业网站建设景区网站建设 现状
  • 营销型网站建设与网盟dw做网站简单首页
  • 郑州视频网站建设网站开发语言是什么
  • 最全的数据网站seopc流量排名官网
  • 襄阳网站建设兼职php网站开发架构
  • 如何给网站做备案汕头网络公司网站建设
  • 上海网站开发平台seo优化网站排名
  • 网站提交入口深圳制作宣传片公司
  • 用电脑做服务器的建一个网站国内的搜索引擎有哪些
  • 大航母网站建设费用网站建设重要新
  • 自己做网站卖机器设备北京高端网站建设系统
  • 广西建设厅网站培训中心做网站接电话一般要会什么
  • 爬虫做视频网站详细的营销推广方案
  • 公司网站发布流程全网精选小程序
  • 响应式企业网站制作网页时首先要确定什么
  • 太仓建设网站企业名录2022版
  • 手机网站改版seo优化专员招聘
  • 青岛网站推广怎么选安庆做网站电话
  • 大气的企业网站模板怎么百度推广
  • 企业网络营销企业网站建设章节习题静安网站建设关键词优化seo
  • 网站使用授权书可以做网站的服务器
  • 网站备案成功后网页设计人员招聘
  • 手机网站关键词快速排名网络公司网站首页
  • 小型网站建设费用浙江电信关于网站备案信息核实的公告
  • 淘宝网店网站建设目的网站建设中 html免费