设计网站网站名称,哈尔滨造价信息网官网,百度惠生活商家怎么入驻,微商城网站建设怎么样1.按摩师#xff08;打家劫舍 I#xff09;
题目连接#xff1a;面试题 17.16. 按摩师 一个有名的按摩师会收到源源不断的预约请求#xff0c;每个预约都可以选择接或不接。在每次预约服务之间要有休息时间#xff0c;因此她不能接受相邻的预约。给定一个预约请求序列打家劫舍 I
题目连接面试题 17.16. 按摩师 一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。 注意本题相对原题稍作改动
1.1.题目解析 按摩师可以任意选择预约接还是不接说明不一定能是从第一个开始。在每次预约服务之间要有休息时间只要是不相邻即可那有两个问题从那个地方开始接服务完之后一次跳过多少个预约
1.2.解决问题
(1)、状态表示 假设以某个位置未结尾或者某个位置未起始 定义一个dp[i]就可以表示找到最优的预约集合。这里定义状态表示以第i个位置为结尾表示此时dp[i]表示了预约时间最长 但是这里有一个问题第i个位置选还是不选的问题。假设nums [1 2]如果i为2这个位置选还是不选这里的问题在于不能相邻那要看第1个位置所以划分两种情况 g[i]表示此时第i个位置必选此时为最长预约时间 f [i]表示此时第i个位置不选此时为最长预约时间
(2)、状态转移⽅程 (3)、初始化 g[0] nums[0]f[0] 0 (4)、初始化顺序 这里根据题目要求根据状态转移方程从左往右将两个dp填充。 (5)、返回值 返回max(f[i],g[i])即为结果
1.3.参考代码
C版本
class Solution {
public:int massage(vectorint nums) {if(nums.empty()) return 0;int n nums.size();vectorint f(n);vectorint g(n);f[0] nums[0];for(int i 1;in;i){f[i] g[i -1] nums[i];g[i] max(g[i -1],f[i -1]);}return max(f[n -1],g[n -1]);}
};Java版本
class Solution {public int massage(int[] nums) {int n nums.length;if(n 0) return 0;int g[] new int[n];int f[] new int[n];g[0] nums[0];for(int i 1;i n;i){g[i] f[i -1] nums[i];f[i] Math.max(f[i -1],g[i -1]); }return Math.max(f[n-1],g[n-1]);}
}2.打家劫舍 II
题目链接213. 打家劫舍 II 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
2.1.解决问题
这个的问题和上一题唯一不同的点在于第一个房子的处理。**情况一**如果第一个房屋选第一个房屋的值加上从第三个房屋开始到倒数第二个房屋的最大值。**情况二**如果第一个房屋不选那么从第二个房屋到最后一个房屋退化第一题的解决方案。
2.2.参考代码
C版本
class Solution {
public:int rob(vectorint nums) {int n nums.size();return max(nums[0] rob_(nums,2,n-1),rob_(nums,1,n));}int rob_(vectorint nums,int start,int end){if(start end) return 0;int n end - start;vectorint g(n);vectorint f(n);f[0] nums[start];for(int i 1;i n;i){f[i] g[i -1] nums[i start];g[i] max(f[i -1],g[i -1]);}return max(f[n-1],g[n-1]);}
};Java版本
class Solution {public int rob(int[] nums) {int n nums.length;return Math.max(nums[0] rob_(nums,2,n -1),rob_(nums,1,n));}public int rob_(int[] nums,int start,int end){if(end - start 0) return 0;int n end - start;int f[] new int[n];int g[] new int[n];f[0] nums[start];for(int i 1;i n;i){f[i] g[i -1] nums[start i];g[i] Math.max(f[i -1],g[i - 1]);} return Math.max(f[n -1],g[n -1]);}
}3.删除并获得点数
题目链接740. 删除并获得点数 给你一个整数数组 nums 你可以对它进行一些操作。 每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除 所有 等于 nums[i] - 1 和 nums[i] 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数
3.1.解决问题
能不能不删除当然可以如果在多一步删除操作岂不是多做无用功。另外nums数组是无序的也麻烦不管三七二十一排序可以将nums做预处理映射到一个arr中。 最后映射成arr之后就又变成的了。对arr数组的i位置的选还是不选又变成了打家劫舍的问题。
3.2.参考代码
C版本
class Solution {
public:int deleteAndEarn(vectorint nums) {const int N 10001;vectorint arr(N);for(auto e : nums) arr[e] e;vectorint f(N);vectorint g(N);for(int i 1;i N;i){f[i] g[i -1] arr[i];g[i] max(f[i- 1],g[i -1]);} return max(f[N -1],g[N -1]);}
};
