河南建设厅特种工报考网站,WordPress自动文章摘要,宁波网络公司怎么选,上海市人才服务中心网首页1049.最后一块石头的重量II 有一堆石头#xff0c;每块石头的重量都是正整数。 每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 x y。那么粉碎的可能结果如下#xff1a; 如果 x y#xff0c;那…1049.最后一块石头的重量II 有一堆石头每块石头的重量都是正整数。 每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下 如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下就返回 0。 示例 输入[2,7,4,1,8,1]输出1 解释 组合 2 和 4得到 2所以数组转化为 [2,7,1,8,1]组合 7 和 8得到 1所以数组转化为 [2,1,1,1]组合 2 和 1得到 1所以数组转化为 [1,1,1]组合 1 和 1得到 0所以数组转化为 [1]这就是最优值。 提示 1 stones.length 301 stones[i] 1000 本题要求最小的石头重量最好的情况就是最后剩下的两个石头重量一致结果为0。那也就跟昨天的分割子集的本质一样将这个数组分割成两个子集使得两个子集的元素和相等。因此看是否可以将石头重量集合拆分为总和为sum/2的子集。因为本题石头粉碎是不可逆的因此属于01背包问题那么就开始对应如下四点
背包的可容纳的重量为sum / 2背包要放入的石头的重量也就是石头的价值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入
动规五部曲
确定dp数组以及下标的含义dp[j]表示重量为j的背包最多可以背的重量为dp[j]确定递推公式dp[j]max(dp[j], dp[j-stones[i]]stones[i])dp数组如何初始化sumstones[i] targetsum/2递归顺序先遍历石头再遍历重量并且重量要倒序遍历
如果背包需要满足的容量为target当dp[target]target时背包就装满了也就是本题的结果为0。如果不能满足因为sum/2是向下取整所以sum-dp[target]一定大于dp[target]所以相撞以后剩下的石头重量为(sum-dp[target])-dp[target]
class Solution {public int lastStoneWeightII(int[] stones) {int sum0;for(int i0;istones.length;i){sumstones[i];}int targetsum1;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 (sum-dp[target])-dp[target]; }
}
注意这里不需要再单独判断一下dp[target]是否等于target了如果等于的话其实最后相当于sum-2*target0了如果多写了这一步判断反而会漏算情况。
并且sum/2的空间复杂度要比sum1移位运算高所以最好写后者。
494.目标和 给定一个非负整数数组a1, a2, ..., an, 和一个目标数S。现在你有两个符号 和 -。对于数组中的任意一个整数你都可以从 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例 输入nums: [1, 1, 1, 1, 1], S: 3输出5 解释 -11111 31-1111 311-111 3111-11 31111-1 3 一共有5种方法让最终目标和为3。 提示 数组非空且长度不会超过 20 。初始的数组的和不会超过 1000 。保证返回的最终结果能被 32 位整数存下。 这道题先用动态规划五部曲想了一下本题依然是只能取一次所以还是01背包思路
确定dp数组以及下标的含义dp[j]表示达到和为j的值有dp[j]种方法确定递推公式目前还不知道dp数组如何初始化dp[0]1因为当只有1个元素的时候那么就只有一种方法确定遍历顺序还是按照元素从前向后按照数值从后向前举例推导dp数组递推公式还没出来暂时举不出来例子
脑子比较累直接看了题解
本题要如何使表达式结果为target。首先因为有sum所以left right sumsum是固定的因此right sum - left。既然为target那么就一定有 left组合 - right组合 target这里left就是加法的总和right就是减法的总和公式来了 left - (sum - left) target 推导出 left (target sum)/2, target是固定的sum是固定的left就可以求出来。此时问题就是在集合nums中找出和为left的组合。此时问题就转化为装满容量为left的背包有几种方法。还要注意几种特殊的情况(target sum) / 2 应该担心计算的过程中向下取整有没有影响如果sum为5target为2那么无论怎样也不会到达target值也就是说当sumtarget为奇数时是没有解决方案的。并且如果target的的绝对值大于sum也是没有解决方法的直接返回0。 只要搞到nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。
例如dp[j]j 为5
已经有一个1nums[i] 的话有 dp[4]种方法 凑成 容量为5的背包。已经有一个2nums[i] 的话有 dp[3]种方法 凑成 容量为5的背包。已经有一个3nums[i] 的话有 dp[2]中方法 凑成 容量为5的背包已经有一个4nums[i] 的话有 dp[1]中方法 凑成 容量为5的背包已经有一个5 nums[i]的话有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。
所以求组合类问题的公式都是类似这种dp[j] dp[j - nums[i]]
import java.lang.Math;
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum0;for(int i0;inums.length;i){sumnums[i];}int left(sumtarget)1;if((sumtarget)%21) return 0;if(Math.abs(target)sum) return 0;int[] dp new int[left1];dp[0]1;for(int i0;inums.length;i){for(int jleft;jnums[i];j--){dp[j] dp[j-nums[i]];}}return dp[left];}
}
474.一和零 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的大小该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素集合 x 是集合 y 的 子集 。 示例 1 输入strs [10, 0001, 111001, 1, 0], m 5, n 3 输出4 解释最多有 5 个 0 和 3 个 1 的最大子集是 {10,0001,1,0} 因此答案是 4 。 其他满足题意但较小的子集包括 {0001,1} 和 {10,1,0} 。{111001} 不满足题意因为它含 4 个 1 大于 n 的值 3 。 示例 2 输入strs [10, 0, 1], m 1, n 1输出2解释最大的子集是 {0, 1} 所以答案是 2 。 提示 1 strs.length 6001 strs[i].length 100strs[i] 仅由 0 和 1 组成1 m, n 100 本题还是一个背包问题本题中strs 数组里的元素就是物品每个物品都是一个只能取一次因此还是01背包问题。这里限制了两个元素的大小这两个大小之间是没有什么制约关系的相当于有两个背包所以要定义一个二维dp数组dp[i][j]继续开始动规五部曲
确定dp数组以及下标的含义dp[i][j]表示最多取i个1和j个0后的最大子集的大小确定递推公式dp[i][j]是由前一个已经选好的子串推导而来假设前面那个子串已经有zero个0和one个1那么dp[i][j]dp[i-zero][j-one]1并且还要跟自己做比较取最大值。dp数组如何初始化初始化为0确定遍历顺序遍历物品要从前往后遍历背包要从后往前这里m和n都是背包所以都是从后往前遍历。举例推导dp数组以输入[10,0001,111001,1,0]m 3n 3为例最后dp数组的状态如下所示 class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m1][n1];for(String str:strs){int zero0, one0;for(char c : str.toCharArray()){if(c 0) zero;else one;}for(int im;izero;i--){for(int jn;jone;j--){dp[i][j]Math.max(dp[i][j], dp[i-zero][j-one]1);}}}return dp[m][n];}
}
