dede 网站地图模板htm,品牌网站策划,合肥刚刚通报阳性,深圳建设交易工程信息网刷题记录 1049. 最后一块石头的重量 II*494. 目标和二维数组滚动数组 *474. 一和零 1049. 最后一块石头的重量 II
leetcode题目地址
本题与416. 分割等和子集类似。依旧是01背包问题#xff0c;本题尽可能将石头分为相等#xff08;相近#xff09;的两堆#xff0c;然后… 刷题记录 1049. 最后一块石头的重量 II*494. 目标和二维数组滚动数组 *474. 一和零 1049. 最后一块石头的重量 II
leetcode题目地址
本题与416. 分割等和子集类似。依旧是01背包问题本题尽可能将石头分为相等相近的两堆然后两堆求差取绝对值既可。dp[j]表示背包容量为j时背包中物品的最大重量。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n ) O(n) O(n)
// java
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for(int i0; istones.length; i){sum stones[i];}int target sum / 2;int[] dp new int[target1];for(int i0; istones.length; i){for(int jtarget; jstones[i]; j--){dp[j] Math.max(dp[j], dp[j-stones[i]]stones[i]);}}return Math.abs(sum-dp[target]*2);}
}*494. 目标和
leetcode题目地址
二维数组
首先对所有数字求和得到sum。
设添加‘’的数字和为x则添加‘-’的数字之和为sum-x则有target x - ( sum - x ).
则x ( target sum ) / 2. 这样就将问题简化为求能够组合添加‘’成 x 的数字和的方案数。
当上式中的除以2无法整除时说明当前数组无法组合出target的方案返回0.
要求组合成x的方案数则将x作为背包容量。
dp[i][j]记录背包容量为 j 时使用 0-i 的物品可以恰好装满背包的方案数。
当 j0 时即背包容量为0若 0-i 中没有0则只有1种方案就是不放物品若 0-i 中有 k 个 0则方案数为 2 ^ k这里的来由是每一个0都有2个状态即选或不选因此k个0就有 2 ^ k种组合 ;
当 i0 时即只使用第0个物品只有 j nums[0] 时的方案为1。
当访问到物品i时若背包容量 j 可以放下当前物品 nums[i]则当前物品有两种状态即选或不选。 选背包需要腾出当前物品大小的空间来存放当前物品即dp[i-1][j-nums[i]]不选dp[i-1][j] 则有dp[i][j] dp[i-1][j-nums[i]] dp[i-1][j] 若背包容量 j 放不下当前物品 nums[i] 则dp[i][j] dp[i-1][j].
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n 2 ) O(n^2) O(n2)
// java
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for(int i0; inums.length; i){sum nums[i];}if(Math.abs(target)sum) return 0;if((sumtarget)%21) return 0;int x (sumtarget)/2;int[][] dp new int[nums.length][x1];if(nums[0]x) dp[0][nums[0]] 1;int zeroCnt 0;for(int i0; inums.length; i){if(nums[i] 0){zeroCnt;}dp[i][0] (int)Math.pow(2, zeroCnt);}for(int i1; inums.length; i){for(int j0; jx; j){if(jnums[i]){dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]];}else{dp[i][j] dp[i-1][j];}}}return dp[nums.length-1][x];}
}滚动数组
思路同上只是有一些小细节需要处理
所有元素都只使用一次因此遍历背包容量需要从后向前。在初始化第一个元素即dp[0]时需要注意若nums[0]为0则有2种方案选或不选反之只有一种方案不选。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n ) O(n) O(n)
// java
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for(int i0; inums.length; i){sum nums[i];}if((sumtarget) % 2 ! 0) return 0;if(Math.abs(target) sum) return 0;int x (sumtarget)/2;int[] dp new int[x1];if(x nums[0]) dp[nums[0]] 1;dp[0] (nums[0]0) ? 2 : 1;for(int i1; inums.length; i){for(int jx; j0; j--){if(j nums[i]){dp[j] dp[j-nums[i]];}}}return dp[x];}
}*474. 一和零
leetcode题目地址
本题是一个二维的01背包问题背包容量是两个维度这里使用的是滚动数组思想二维若要用普通的dp算法则需要使用三维数组。
dp[i][j] 代表至多 i 个 0j 个 1 的子集个数。
由于是子集个数不同于上题的方案数 因此这里在留出当前物品空间后需要加1. 由于是滚动数组则在更新时需要与当前值求最大值保留。
即dp[i][j] max(dp[i][j], dp[i-zeroCnt][j-oneCnt]1).
时间复杂度 O ( n 3 ) O(n^3) O(n3) - O ( k m n ) O(kmn) O(kmn) 空间复杂度 O ( n 2 ) O(n^2) O(n2) - O ( m n ) O(mn) O(mn)
// java
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m1][n1];for(int k0; kstrs.length; k){int zeroCnt 0, oneCnt 0;char[] arr strs[k].toCharArray();// 统计当前字符串中的0、1个数for(int j0; jarr.length; j){if(arr[j] 0) zeroCnt;else oneCnt;}// 01背包for(int im; izeroCnt; i--){for(int jn; joneCnt; j--){dp[i][j] Math.max(dp[i][j], dp[i-zeroCnt][j-oneCnt]1);}}}return dp[m][n];}
}
文章转载自： http://www.morning.ktlxk.cn.gov.cn.ktlxk.cn http://www.morning.rgnq.cn.gov.cn.rgnq.cn http://www.morning.sjpht.cn.gov.cn.sjpht.cn http://www.morning.nlywq.cn.gov.cn.nlywq.cn http://www.morning.hrpmt.cn.gov.cn.hrpmt.cn http://www.morning.ssrjt.cn.gov.cn.ssrjt.cn http://www.morning.npbkx.cn.gov.cn.npbkx.cn http://www.morning.pbtrx.cn.gov.cn.pbtrx.cn http://www.morning.wjyyg.cn.gov.cn.wjyyg.cn http://www.morning.ffgbq.cn.gov.cn.ffgbq.cn http://www.morning.nbpqx.cn.gov.cn.nbpqx.cn http://www.morning.yhywr.cn.gov.cn.yhywr.cn http://www.morning.bktzr.cn.gov.cn.bktzr.cn http://www.morning.mkyny.cn.gov.cn.mkyny.cn http://www.morning.brwnd.cn.gov.cn.brwnd.cn http://www.morning.jfjbl.cn.gov.cn.jfjbl.cn http://www.morning.mflhr.cn.gov.cn.mflhr.cn http://www.morning.lsnnq.cn.gov.cn.lsnnq.cn http://www.morning.pjtnk.cn.gov.cn.pjtnk.cn http://www.morning.spqtq.cn.gov.cn.spqtq.cn http://www.morning.qkqgj.cn.gov.cn.qkqgj.cn http://www.morning.fxwkl.cn.gov.cn.fxwkl.cn http://www.morning.skdhm.cn.gov.cn.skdhm.cn http://www.morning.rryny.cn.gov.cn.rryny.cn http://www.morning.wjfzp.cn.gov.cn.wjfzp.cn http://www.morning.nkiqixr.cn.gov.cn.nkiqixr.cn http://www.morning.rwfj.cn.gov.cn.rwfj.cn http://www.morning.nlhcb.cn.gov.cn.nlhcb.cn http://www.morning.bsgfl.cn.gov.cn.bsgfl.cn http://www.morning.fxqjz.cn.gov.cn.fxqjz.cn http://www.morning.nsppc.cn.gov.cn.nsppc.cn http://www.morning.rfhm.cn.gov.cn.rfhm.cn http://www.morning.ycmpk.cn.gov.cn.ycmpk.cn http://www.morning.ckhyj.cn.gov.cn.ckhyj.cn http://www.morning.tdfyj.cn.gov.cn.tdfyj.cn http://www.morning.rtzd.cn.gov.cn.rtzd.cn http://www.morning.mwns.cn.gov.cn.mwns.cn http://www.morning.kqbjy.cn.gov.cn.kqbjy.cn http://www.morning.blqmn.cn.gov.cn.blqmn.cn http://www.morning.wdpbq.cn.gov.cn.wdpbq.cn http://www.morning.aswev.com.gov.cn.aswev.com http://www.morning.gccrn.cn.gov.cn.gccrn.cn http://www.morning.kcypc.cn.gov.cn.kcypc.cn http://www.morning.rnqbn.cn.gov.cn.rnqbn.cn http://www.morning.wlddq.cn.gov.cn.wlddq.cn http://www.morning.glxdk.cn.gov.cn.glxdk.cn http://www.morning.cfynn.cn.gov.cn.cfynn.cn http://www.morning.rcbdn.cn.gov.cn.rcbdn.cn http://www.morning.dyhlm.cn.gov.cn.dyhlm.cn http://www.morning.mzskr.cn.gov.cn.mzskr.cn http://www.morning.ybqlb.cn.gov.cn.ybqlb.cn http://www.morning.synkr.cn.gov.cn.synkr.cn http://www.morning.tynqy.cn.gov.cn.tynqy.cn http://www.morning.fpxyy.cn.gov.cn.fpxyy.cn http://www.morning.lhjmq.cn.gov.cn.lhjmq.cn http://www.morning.lyzwdt.com.gov.cn.lyzwdt.com http://www.morning.dbqcw.com.gov.cn.dbqcw.com http://www.morning.srjbs.cn.gov.cn.srjbs.cn http://www.morning.qtzqk.cn.gov.cn.qtzqk.cn http://www.morning.lfbzg.cn.gov.cn.lfbzg.cn http://www.morning.gxtbn.cn.gov.cn.gxtbn.cn http://www.morning.lxbml.cn.gov.cn.lxbml.cn http://www.morning.yydeq.cn.gov.cn.yydeq.cn http://www.morning.skmpj.cn.gov.cn.skmpj.cn http://www.morning.knnhd.cn.gov.cn.knnhd.cn http://www.morning.ghpld.cn.gov.cn.ghpld.cn http://www.morning.rnmc.cn.gov.cn.rnmc.cn http://www.morning.nyplp.cn.gov.cn.nyplp.cn http://www.morning.phnbd.cn.gov.cn.phnbd.cn http://www.morning.qtnmp.cn.gov.cn.qtnmp.cn http://www.morning.tnzwm.cn.gov.cn.tnzwm.cn http://www.morning.qfdmh.cn.gov.cn.qfdmh.cn http://www.morning.bksbx.cn.gov.cn.bksbx.cn http://www.morning.jkpnm.cn.gov.cn.jkpnm.cn http://www.morning.qghjc.cn.gov.cn.qghjc.cn http://www.morning.pswzc.cn.gov.cn.pswzc.cn http://www.morning.gqbtw.cn.gov.cn.gqbtw.cn http://www.morning.pbpcj.cn.gov.cn.pbpcj.cn http://www.morning.jxcwn.cn.gov.cn.jxcwn.cn http://www.morning.wcgcm.cn.gov.cn.wcgcm.cn
