蚌埠网站建设文章,基于android的移动互联网开发,微信小程序平台官网登录入口,深圳建筑公司公章目录 讀題
1049. 最后一块石头的重量 II
自己看到题目的第一想法
看完代码随想录之后的想法
494. 目标和
自己看到题目的第一想法
看完代码随想录之后的想法
474.一和零
自己看到题目的第一想法
看完代码随想录之后的想法
1049. 最后一块石头的重量 II - 實作
思路 …目录 讀題
1049. 最后一块石头的重量 II
自己看到题目的第一想法
看完代码随想录之后的想法
494. 目标和
自己看到题目的第一想法
看完代码随想录之后的想法
474.一和零
自己看到题目的第一想法
看完代码随想录之后的想法
1049. 最后一块石头的重量 II - 實作
思路
Code
494. 目标和 - 實作
思路
Code
474.一和零 - 實作
思路
Code
總結
自己实现过程中遇到哪些困难
今日收获记录一下自己的学习时长
相關資料 讀題
1049. 最后一块石头的重量 II
自己看到题目的第一想法
初始化定義可以改成dp[j]代表重量為j 的狀態下最小的數值為dp[j]如果跟等和子集很像那我的最大的背包重量應該是stone sum但想了一陣子還是沒有想法思緒非常不清晰。
看完代码随想录之后的想法
重量總和近似的兩堆聽完就醍醐灌頂了程式一下子就寫出來了的去跟昨天的416很像但是真的沒有想到是氛圍重量總和近似的兩堆基本上有做過416這一題就聽到這個關鍵字基本就可以解出來了
494. 目标和
自己看到题目的第一想法
正與負可以想成取與不取根據卡哥的遞推公式還是沒有想得很清晰到底可以怎麼做。
看完代码随想录之后的想法
拆解問題
將這個數組分成兩個子集加法放一個集合(left)、減法放一個集合(right)
考慮’’ 與 ‘-’ 的狀況下公式如下
left ( -right) target → target 是題目提供的
left - right target
不考慮’’ 與 ‘-’ 的狀況下公式如下 left right sum 這個等式可以改為 right sum - left 將left 帶入考慮 ‘’ ‘-’的公式可以得到
left left - sum target
2 left target sum
left (target sum) / 2
因為target 跟 sum都是固定的
target 由題目提供
sum 透過數組總和得出
所以透過這兩個參數可以得出left這個變量需要為多少
轉換問題為01背包問題
在個問題題當中
正數總和 - 負數總和 target 也就是 left - right target
經過重新定義等式可以得到上面所得出的公式
left (target sum) / 2
而left 實際上代表選擇的正數總和
所以問題轉化成: 如何從數組中選擇一些數字使其總和為left
並且根據公式可以發現target sum / 2 是有可能不是正整數的
比如說target sum 5 那最後得到的left數字是 2.5
但我們在這個數組當中只有正整數無法得到一個集合內的數字為2.5也就是說無法得到一個解法此時這個數組並沒有解法。
延伸出來講回到公式定義 正數總和 - 負數總和 target
這裡得負數總和不能想像成left - ( - right) target
而是left - right target 不然思緒會感覺到混亂會想說負負得正
但實際上所謂的負數總和根據題意也是正整數相加後套上一個 - 號
那假設target sum 也就是目標值大於數組總和(全部都是正的) 那也無法得出一個解因為這件事情在這個題意當中無法達成。
474.一和零
自己看到题目的第一想法
不太清楚要怎麼處理這樣的題目看得有點矇
看完代码随想录之后的想法
原本的背包有只有一個維度這次的背包有兩個維度需要考慮並且因為物品的重量維度也有兩個所以在處理上比較複雜可以想像成是一個二維的滾動數組背包滾動的過程比較繁瑣需要考慮。 1049. 最后一块石头的重量 II - 實作
思路
aside 分為兩堆近似重量的兩者相撞就會是最小的。
/aside 定義DP數組以及下標的含意 target: 假設分割為兩個的重量近似的兩堆 dp[j] : 背包重量 j 的最大價值為dp[j] stones数組中重量與價值就是stones[i] 遞推公式 dp[j] max(dp[j], dp[j - stones[i]] stones[i]); 根據遞推公式確定DP數組如何初始化 dp[0]要初始化為0其他部分也要更新為正整數下的最小位数0 確定遍歷順序 避免覆蓋掉上一次的值所以要使用倒敘遍歷 打印dp數組 (debug);
Code
class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum 0;for(int i 0; i stones.size(); i) {sum stones[i];}int other sum;sum / 2;vectorint dp(sum 1, 0);for(int i 0; i stones.size(); i) {for(int j sum; j stones[i]; j--) {dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}int result other - (dp[sum] dp[sum]);return result;}
};494. 目标和 - 實作
思路
aside 之前的題目是求容量為j的背包最多能裝多少。 這次的題目是求容量為j的背包有多少方法可以裝滿。
/aside 定義DP數組以及下標的含意 dp[j]: 容量為j的背包有dp[j]個方法可以裝滿。 dp[i][j]: 使用下標[0,i]個物品在容量j的背包有dp[i][j]種方法可以裝滿 遞推公式 其實轉換一下思路可以知道之前求最大價值時會去透過dp[j - weight[i]] value[i] 的方法透過dp[j - weight[i]] 知道不包含目前重量的最大價值為多少 那目標和dp[j - nums[i]] 可以背包j在不包含當前的nums[i]數值有多少種方法可以裝滿 → dp[j - nums[i]] 以及背包在包含當前nums[i]的數值有多少種方法 → dp[j] 公式會長成 dp[j] dp[j] dp[j - nums[i]] 根據C語法可以簡化為 dp[j] dp[j - nums[i]] 根據遞推公式確定DP數組如何初始化 因為我們的問題轉化了所以是要找出nums中有多少子集它的和為正數總和所以我們就不能用原題意來看這道題目 dp[0] 代表組成正數總和為0的方法有多少種不選擇任何數字或者選取相互抵銷的正數或負數但在初始化的過程當中並沒有選取任何數可以想成說 aside 在不取任何數的狀況下來思考有多少方法可以匹配dp數組的定義 /aside 根據上面這個思路 假設背包大小為三其初始化數組應該如下 dp[0] 1 dp[1] 0 dp[2] 0 因為不取任何數的狀況下達成dp[0]的方法有1種dp[1]~dp[2] 因為根本沒有取任何數所以只有0種方法可以達成。 確定遍歷順序 根據遞推公式外層迴圈是for 物品的變化取與不取內層迴圈則是for 背包重量的變化由大到小進行遍歷。 打印dp數組 (debug);
输入nums: [1, 1, 1, 1, 1], S: 3
bagSize (S sum) / 2 (3 5) / 2 4
dp数组状态变化如下 Code
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for(int i 0; i nums.size(); i) {sum nums[i];}if(abs(target) sum) return 0;if((target sum) % 2 1) return 0;int bagsize (sum target) / 2;vectorint dp(bagsize 1, 0);dp[0] 1;for(int i 0; i nums.size(); i ) { //選擇物品for(int j bagsize; j nums[i]; j--) { //選擇背包dp[j] dp[j - nums[i]];}}return dp[bagsize];}
};474.一和零 - 實作
思路
aside 題意中的m與n可以想像成是兩個維度的背包物品也可以想成是有兩個維度的重量所組成
/aside 定義DP數組以及下標的含意 dp[i][j]: i個0與j個1所組成的最大子集合為dp[i][j] 遞推公式 先處理物品重量 每個字串由0跟1組成計算其01的個別重量為zeroNum、oneNum遞推公式 dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1] 根據遞推公式確定DP數組如何初始化 dp[0][0] 0 代表沒有組合可以放入這個背包當中其餘數組則初始化為0 避免影響結果 確定遍歷順序 先遍歷物品在遍歷二維背包 因為是滾動數組所以二維背包是由後往前遍歷
Code
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp (m1, vectorint(n1, 0));for(string str: strs) {int zeroNum0, oneNum0;for(char c: str) {if(c 0) zeroNum;else oneNum;}for(int i m; i zeroNum; i--) {for(int j n; j oneNum; j--) {dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);}}}return dp[m][n];}
};總結
自己实现过程中遇到哪些困难
在實現的過程中在494. 目标和其實真的思考了很久到底要怎麼解並且題解影片也看了好幾次也透過了線上AI不斷的去釐清自己的想法最終才寫了出來感覺這個過程中其實真的不容易理解上要花很多時間才能夠完全吸收但目前就是一刷繼續加油!
今日收获记录一下自己的学习时长
總共學習了4hr左右不斷的去釐清自己的想法最終終於釐清並且透過自己的語言寫下思路。
相關資料
● 今日学习的文章链接和视频链接
1049. 最后一块石头的重量 II
视频讲解动态规划之背包问题这个背包最多能装多少LeetCode1049.最后一块石头的重量II_哔哩哔哩_bilibili
https://programmercarl.com/1049.最后一块石头的重量II.html
494. 目标和
视频讲解动态规划之背包问题装满背包有多少种方法| LeetCode494.目标和_哔哩哔哩_bilibili
https://programmercarl.com/0494.目标和.html
474.一和零
视频讲解动态规划之背包问题装满这个背包最多用多少个物品| LeetCode474.一和零_哔哩哔哩_bilibili
https://programmercarl.com/0474.一和零.html
