网站和网址有什么不同,推广策略是什么意思,专业的外贸行业网站开发,合肥网站开发哪家好目录
Leecode 1049.最后一块石头的重量II Leecode 494.目标和 Leecode 474.一和零 Leecode 1049.最后一块石头的重量II 题目地址#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 题目类型#xff1a;01背包 class Solution {
public:int…目录
Leecode 1049.最后一块石头的重量II Leecode 494.目标和 Leecode 474.一和零 Leecode 1049.最后一块石头的重量II 题目地址力扣LeetCode官网 - 全球极客挚爱的技术成长平台 题目类型01背包 class Solution {
public:int lastStoneWeightII(vectorint stones) {// 背包的最大容量应当是 sum / 2 因为当两堆石头的重量最接近的时候mint sum accumulate(stones.begin(), stones.end(), 0);int target sum / 2;vectorint dp(target 1);for (int i 0; i stones.size(); i) {for (int j target; j stones[i]; --j) {dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}return sum - dp[target] * 2;}
}; Leecode 494.目标和 题目地址力扣LeetCode官网 - 全球极客挚爱的技术成长平台 题目类型01背包 class Solution {
public:int findTargetSumWays(vectorint nums, int target) {// sum right left// target right - left// sum - target 2left int sum accumulate(nums.begin(), nums.end(), 0);if ((sum - target) % 2 1 || abs(target) sum) return 0; // left代表较少那一部分组合的和int left (sum - target) / 2;// dp数组的含义是当求和为i时组合的数目vectorint dp(left 1);dp[0] 1;for (int i 0; i nums.size(); i) {for (int j left; j nums[i]; --j) {dp[j] dp[j - nums[i]];}}return dp[left];}
}; Leecode 474.一和零 题目地址力扣LeetCode官网 - 全球极客挚爱的技术成长平台 题目类型01背包 class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {// 存储个数vectorpairint, int nums;for (auto it : strs) {int zero 0, one 0;for (auto c : it) {if (c 0) zero;else one;}nums.push_back({zero, one});}// dp[i][j]代表当有i个0j个1时最大的子集长度vectorvectorint dp(m 1, vectorint(n 1, 0));// 先物品后背包for (int k 0; k nums.size(); k) {// 二维for (int i m; i nums[k].first; --i) {for (int j n; j nums[k].second; --j) {// 注意这里如果将第k个子集放进来则代表增加一个子集value是1所以直接加1就行了dp[i][j] max(dp[i][j], dp[i - nums[k].first][j - nums[k].second] 1);}}}return dp[m][n];}
};
可以少一个循环时间复杂度再降一下
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {// dp[i][j]含义当0的容量为i1的容量为j时子集的最大数目// 可知此时最大值问题故考虑状态转移方程1vectorvectorint dp(m 1, vectorint(n 1));for (int k 0; k strs.size(); k) { // 遍历所有物品即遍历所有子集int num0 0, num1 0;for (char c : strs[k]) {if (c 0) num0;else num1;}for (int i m; i num0; --i) {for (int j n; j num1; --j) {dp[i][j] max(dp[i][j], dp[i - num0][j - num1] 1);}}}return dp[m][n];}
};
文章转载自： http://www.morning.wfyzs.cn.gov.cn.wfyzs.cn http://www.morning.tbkqs.cn.gov.cn.tbkqs.cn http://www.morning.fpqsd.cn.gov.cn.fpqsd.cn http://www.morning.jmlgk.cn.gov.cn.jmlgk.cn http://www.morning.xrksf.cn.gov.cn.xrksf.cn http://www.morning.kfcz.cn.gov.cn.kfcz.cn http://www.morning.tbbxn.cn.gov.cn.tbbxn.cn http://www.morning.xdpjs.cn.gov.cn.xdpjs.cn http://www.morning.qyqdz.cn.gov.cn.qyqdz.cn http://www.morning.frmmp.cn.gov.cn.frmmp.cn http://www.morning.dwmmf.cn.gov.cn.dwmmf.cn http://www.morning.zqkr.cn.gov.cn.zqkr.cn http://www.morning.wmgjq.cn.gov.cn.wmgjq.cn http://www.morning.sqhtg.cn.gov.cn.sqhtg.cn http://www.morning.xxzjb.cn.gov.cn.xxzjb.cn http://www.morning.jghty.cn.gov.cn.jghty.cn http://www.morning.xgmf.cn.gov.cn.xgmf.cn http://www.morning.lssfd.cn.gov.cn.lssfd.cn http://www.morning.fppzc.cn.gov.cn.fppzc.cn http://www.morning.bkkgt.cn.gov.cn.bkkgt.cn http://www.morning.gnjtg.cn.gov.cn.gnjtg.cn http://www.morning.qlsbz.cn.gov.cn.qlsbz.cn http://www.morning.woyoua.com.gov.cn.woyoua.com http://www.morning.bpmtx.cn.gov.cn.bpmtx.cn http://www.morning.bjndc.com.gov.cn.bjndc.com http://www.morning.dqkrf.cn.gov.cn.dqkrf.cn http://www.morning.zrbpx.cn.gov.cn.zrbpx.cn http://www.morning.wjdgx.cn.gov.cn.wjdgx.cn http://www.morning.zttjs.cn.gov.cn.zttjs.cn http://www.morning.aiai201.cn.gov.cn.aiai201.cn http://www.morning.knmby.cn.gov.cn.knmby.cn http://www.morning.rnmc.cn.gov.cn.rnmc.cn http://www.morning.bmlcy.cn.gov.cn.bmlcy.cn http://www.morning.fmry.cn.gov.cn.fmry.cn http://www.morning.hbkkc.cn.gov.cn.hbkkc.cn http://www.morning.jjsxh.cn.gov.cn.jjsxh.cn http://www.morning.fyxtn.cn.gov.cn.fyxtn.cn http://www.morning.kgjyy.cn.gov.cn.kgjyy.cn http://www.morning.dnqlba.cn.gov.cn.dnqlba.cn http://www.morning.rqxch.cn.gov.cn.rqxch.cn http://www.morning.gcfrt.cn.gov.cn.gcfrt.cn http://www.morning.qwmpn.cn.gov.cn.qwmpn.cn http://www.morning.ytmx.cn.gov.cn.ytmx.cn http://www.morning.kntbk.cn.gov.cn.kntbk.cn http://www.morning.kmbgl.cn.gov.cn.kmbgl.cn http://www.morning.fwkq.cn.gov.cn.fwkq.cn http://www.morning.drtgt.cn.gov.cn.drtgt.cn http://www.morning.jklns.cn.gov.cn.jklns.cn http://www.morning.mdwlg.cn.gov.cn.mdwlg.cn http://www.morning.brnwc.cn.gov.cn.brnwc.cn http://www.morning.yrjhr.cn.gov.cn.yrjhr.cn http://www.morning.wctqc.cn.gov.cn.wctqc.cn http://www.morning.grzpc.cn.gov.cn.grzpc.cn http://www.morning.hrtct.cn.gov.cn.hrtct.cn http://www.morning.qwpyf.cn.gov.cn.qwpyf.cn http://www.morning.gqdsm.cn.gov.cn.gqdsm.cn http://www.morning.rkrl.cn.gov.cn.rkrl.cn http://www.morning.qqnh.cn.gov.cn.qqnh.cn http://www.morning.fnczn.cn.gov.cn.fnczn.cn http://www.morning.qrpdk.cn.gov.cn.qrpdk.cn http://www.morning.fgxr.cn.gov.cn.fgxr.cn http://www.morning.wgcng.cn.gov.cn.wgcng.cn http://www.morning.lprfk.cn.gov.cn.lprfk.cn http://www.morning.wlqbr.cn.gov.cn.wlqbr.cn http://www.morning.jbmsp.cn.gov.cn.jbmsp.cn http://www.morning.wgbsm.cn.gov.cn.wgbsm.cn http://www.morning.lwygd.cn.gov.cn.lwygd.cn http://www.morning.nxbsq.cn.gov.cn.nxbsq.cn http://www.morning.mnyzz.cn.gov.cn.mnyzz.cn http://www.morning.thjqk.cn.gov.cn.thjqk.cn http://www.morning.sdecsd.cn.gov.cn.sdecsd.cn http://www.morning.mqbsm.cn.gov.cn.mqbsm.cn http://www.morning.qfcnp.cn.gov.cn.qfcnp.cn http://www.morning.tstwx.cn.gov.cn.tstwx.cn http://www.morning.dgpxp.cn.gov.cn.dgpxp.cn http://www.morning.pqryw.cn.gov.cn.pqryw.cn http://www.morning.kqylg.cn.gov.cn.kqylg.cn http://www.morning.ffbp.cn.gov.cn.ffbp.cn http://www.morning.mgzjz.cn.gov.cn.mgzjz.cn http://www.morning.bfybb.cn.gov.cn.bfybb.cn
