js-leetcode前端動態(tài)規(guī)劃第 3 天打卡「打家劫舍」,一個函數(shù)解決兩個...
- 這是小獅子學(xué)習(xí)動態(tài)規(guī)劃的第 3?天?-
最近，和組里大佬聊了聊，突然就扯到了算法這塊，想當(dāng)初為了參與比賽，面試等準(zhǔn)備了許多的算法題，但現(xiàn)在成為一名社畜之后對這塊領(lǐng)域知識接觸的變少了，甚至覺得這個沒必要做了。
聊著聊著大佬就說了幾句：保持練習(xí)，題到做時方恨菜。
啊確實，過去打開 leetcode 就一股腦兒想著刷題，現(xiàn)在的感受已經(jīng)變了，當(dāng)我打開官網(wǎng)，我的手習(xí)慣性的用快捷鍵關(guān)閉了當(dāng)前窗口，并沒有刷題的想法了。
與大佬溝通后，還是覺得工作之余得保持刷題的習(xí)慣，這個對鍛煉思維很有幫助。
那么就給自己定一個小目標(biāo)吧，保持每個工作日 1～2 個題，在 10 月份左右開始參與一些周賽，我覺得還是得參與一些挑戰(zhàn)。
對于文章的話，目前主要是記錄吧，當(dāng)我把一系列專題刷完之后，會打算出合集視頻吧，也算是自己的總結(jié)與回饋，所以趁現(xiàn)在關(guān)注我，以后就是老粉啦。
198. 打家劫舍
198. 打家劫舍
解題思路
明白這道題，「213. 打家劫舍 II」也就自然明白了。
首先，亮出 dp 狀態(tài)方程
dp[i]?=?Math.max(dp[i-1],?dp[i-2]+?nums[i]);
只有一家的時候，廢話不多說，偷就完事了。
兩家的話，對比一下，看哪一家有錢就偷哪家。
重點在于有三家以上的情況，對于這題來說，從第 2 家開始，如果偷這家，那就加上前兩家的金錢（非累計）
如果不偷，就加上前一家的金錢（非累計）
看最后兩家相鄰的房屋累計的結(jié)果值最大
代碼
/**
?*?@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]);
????????}
????????//?看最后兩家相鄰的房屋累計的結(jié)果值最大
????????return?Math.max(dp[right],?dp[right-1]);
????}
}
var?rob?=?function(nums)?{
????return?robValue(nums,?0,?nums.length-1);
};
213. 打家劫舍 II
解題思路
這個和「198. 打家劫舍」對比來說，就多個條件。
那么，我們在上一題的基礎(chǔ)上調(diào)用兩次封裝的函數(shù)就好了。
一次調(diào)用條件是去掉第一家，二次調(diào)用條件是去掉最后一家，這樣就不會出現(xiàn)首尾都偷的情況了，最后我們比對最大值返回就好了。
/**
?*?@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]);
????????}
????????//?看最后兩家相鄰的房屋累計的結(jié)果值最大
????????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. 刪除并獲得點數(shù)
解題思路
這個轉(zhuǎn)換了之后和「打家劫舍」的題型就差不多了，原理都是撈最多的價值，但是左右不能相鄰撈，因此可以將數(shù)據(jù)重復(fù)值通過索引數(shù)組來存，具體做法如下：
let?maxLen?=?Math.max.apply(null,?nums);
//?創(chuàng)建索引數(shù)組
let?arr?=?new?Uint32Array(maxLen+1);
nums.map(item?=>?arr[item]++);
之后，開始「打家劫舍」。
也是分兩種情況：
- 如果當(dāng)前戶人家要偷的話，那就得加上前面兩家（非累計）獲得金錢，但本題不同的是，因為數(shù)據(jù)有重復(fù)項，由于之前處理過索引值，因此直接將當(dāng)前索引與值相乘即可。
- 如果當(dāng)前戶人家不偷的話，那就加上前一家（非累計）獲得金錢。
數(shù)據(jù)量 10^4，在暗示我們用動態(tài)規(guī)劃了。
狀態(tài)方程如下，從第 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);
????//?創(chuàng)建索引數(shù)組
????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 -
如下是小獅子春秋招過程中學(xué)習(xí)整理的思維導(dǎo)圖以及 PDF 文檔，會不斷更新，目前已有 9?份思維導(dǎo)圖，現(xiàn)在分享給大家，在公眾號后臺回復(fù)「小獅子」，關(guān)注領(lǐng)取
學(xué)如逆水行舟，不進(jìn)則退
點贊 + 在看，好文不白嫖嗷~