js-leetcode前端动态规划第 3 天打卡「打家劫舍」,一个函数解决两个...
共 3384字，需浏览 7分钟
· 2021-08-11
- 这是小狮子学习动态规划的第 3 天 -
最近，和组里大佬聊了聊，突然就扯到了算法这块，想当初为了参与比赛，面试等准备了许多的算法题，但现在成为一名社畜之后对这块领域知识接触的变少了，甚至觉得这个没必要做了。
聊着聊着大佬就说了几句：保持练习，题到做时方恨菜。
啊确实，过去打开 leetcode 就一股脑儿想着刷题，现在的感受已经变了，当我打开官网，我的手习惯性的用快捷键关闭了当前窗口，并没有刷题的想法了。
与大佬沟通后，还是觉得工作之余得保持刷题的习惯，这个对锻炼思维很有帮助。
那么就给自己定一个小目标吧，保持每个工作日 1～2 个题，在 10 月份左右开始参与一些周赛，我觉得还是得参与一些挑战。
对于文章的话，目前主要是记录吧，当我把一系列专题刷完之后，会打算出合集视频吧，也算是自己的总结与回馈，所以趁现在关注我，以后就是老粉啦。
198. 打家劫舍
198. 打家劫舍
解题思路
明白这道题，「213. 打家劫舍 II」也就自然明白了。
首先，亮出 dp 状态方程
dp[i] = Math.max(dp[i-1], dp[i-2]+ nums[i]);
只有一家的时候，废话不多说，偷就完事了。
两家的话，对比一下，看哪一家有钱就偷哪家。
重点在于有三家以上的情况，对于这题来说，从第 2 家开始，如果偷这家，那就加上前两家的金钱（非累计）
如果不偷，就加上前一家的金钱（非累计）
看最后两家相邻的房屋累计的结果值最大
代码
/**
* @param {number[]} nums
* @return {number}
*/
var robValue = function(nums, left, right) {
if(nums.length === 1) return nums[left];
else if(nums.length ===2) return Math.max(nums[left], nums[right]);
else {
let dp = new Array(nums.length);
dp[left] = nums[left];
dp[left+1] = nums[left+1];
// 从第 2 家开始，如果偷这家，那就加上前两家的金钱（非累计）
// 如果不偷，就加上前一家的金钱（非累计）
for(let i=left+1;i<=right;i++){
// 边界条件
if(i-2 < 0 || i-2 < left) dp[i-2] = 0;
dp[i] = Math.max(dp[i-1], dp[i-2]+ nums[i]);
}
// 看最后两家相邻的房屋累计的结果值最大
return Math.max(dp[right], dp[right-1]);
}
}
var rob = function(nums) {
return robValue(nums, 0, nums.length-1);
};
213. 打家劫舍 II
解题思路
这个和「198. 打家劫舍」对比来说，就多个条件。
那么，我们在上一题的基础上调用两次封装的函数就好了。
一次调用条件是去掉第一家，二次调用条件是去掉最后一家，这样就不会出现首尾都偷的情况了，最后我们比对最大值返回就好了。
/**
* @param {number[]} nums
* @return {number}
*/
var robValue = function(nums, left, right) {
if(nums.length === 1) return nums[left];
else if(nums.length ===2) return Math.max(nums[left], nums[right]);
else {
let dp = new Array(nums.length);
dp[left] = nums[left];
dp[left+1] = nums[left+1];
// 从第 2 家开始，如果偷这家，那就加上前两家的金钱（非累计）
// 如果不偷，就加上前一家的金钱（非累计）
for(let i=left+1;i<=right;i++){
// 边界条件
if(i-2 < 0 || i-2 < left) dp[i-2] = 0;
dp[i] = Math.max(dp[i-1], dp[i-2]+ nums[i]);
}
// 看最后两家相邻的房屋累计的结果值最大
return Math.max(dp[right], dp[right-1]);
}
}
var rob = function(nums) {
if(nums.length === 1) return nums[0];
else if(nums.length === 2) return Math.max(nums[0], nums[1]);
else {
return Math.max(robValue(nums, 0, nums.length-2), robValue(nums, 1, nums.length-1));
}
};
740. 删除并获得点数
解题思路
这个转换了之后和「打家劫舍」的题型就差不多了，原理都是捞最多的价值，但是左右不能相邻捞，因此可以将数据重复值通过索引数组来存，具体做法如下：
let maxLen = Math.max.apply(null, nums);
// 创建索引数组
let arr = new Uint32Array(maxLen+1);
nums.map(item => arr[item]++);
之后，开始「打家劫舍」。
也是分两种情况：
- 如果当前户人家要偷的话，那就得加上前面两家（非累计）获得金钱，但本题不同的是，因为数据有重复项，由于之前处理过索引值，因此直接将当前索引与值相乘即可。
- 如果当前户人家不偷的话，那就加上前一家（非累计）获得金钱。
数据量 10^4，在暗示我们用动态规划了。
状态方程如下，从第 2 家开始
dp[i] = Math.max(dp[i-1], dp[i-2]+arr[i]*i);
/**
* @param {number[]} nums
* @return {number}
*/
var deleteAndEarn = function(nums) {
let maxLen = Math.max.apply(null, nums);
// 创建索引数组
let arr = new Uint32Array(maxLen+1);
nums.map(item => arr[item]++);
// 开始「打家劫舍」
let dp = new Array(arr.length);
dp[0] = arr[0];
dp[1] = arr[1];
for(let i=1;i<arr.length;i++){
if(i-2 < 0) dp[i-2] = 0;
dp[i] = Math.max(dp[i-1], dp[i-2]+arr[i]*i);
}
return dp[arr.length-1];
};
- END -
如下是小狮子春秋招过程中学习整理的思维导图以及 PDF 文档，会不断更新，目前已有 9 份思维导图，现在分享给大家，在公众号后台回复「小狮子」，关注领取
学如逆水行舟，不进则退
点赞 + 在看，好文不白嫖嗷~