网站建设创始人,制作网站 太原,洛阳建网站,wordpress 音乐播放器 歌词最后一块石头重量转化为将一个集合分隔成两个集合#xff0c;两个集合之间的差值最小#xff0c;就是最后剩下最小的石头重量。这里可以求集合的一个平均值#xff0c;如果正好等于平均值#xff0c;说明可以抵消#xff0c;这时候重量为0#xff0c;如果不行#xff0c…最后一块石头重量转化为将一个集合分隔成两个集合两个集合之间的差值最小就是最后剩下最小的石头重量。这里可以求集合的一个平均值如果正好等于平均值说明可以抵消这时候重量为0如果不行就把这个平均值作为背包的容量往这里面放东西当放的重量最接近这个背包重量时就是最优解。dp[i][j]表示背包的重量也就是价值i表示第i个石头j表示背包的容量。最后用一个res来表示背包和平均值之间的最小差值。
目标和将数组集合分成两个子集一个表示加号一个表示减号。利用关系add加号中的数字和 diff减号的数字和 sum整个集合的和以及add - diff target推导出add (target sum) / 2;不满足这个关系就说明上式不成立也就是不能分成满足条件的两份。dp[i][j] 表示放入的方法i表示集合中的第i个数j表示现在背包容量也就是add。最后的dp[nums.length ][add]就是nums集合中添加add个数的最多方法。
一和零dp[i][j] 表示的是放入的最大子集的个数i表示0的容量j表示1的容量。有点像双背包需要往这两个背包里面装东西。而加一个外循环k来挨个遍历物品strs。
1049. 最后一块石头的重量 II
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。
示例 1
输入stones [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]这就是最优值。 示例 2
输入stones [31,26,33,21,40] 输出5 提示
1 stones.length 30 1 stones[i] 100
class Solution {public int lastStoneWeightII(int[] stones) {int len stones.length;if(len 1){return stones[0];}int sum 0;for(int wight : stones){sum wight;}int target sum / 2 ;//这里加1个k主要是当sum是奇数时那么最后的重量差要加上这个修正值。//比如说stones [2,7,4,1,8,1]那么sum 23算出来target 11//如果最后背包和这个target的差值0那么最后剩下的重量就是1也就是修正值//如果背包和这个target的差值2那么剩下的重量就是2 * 2 1也就是2倍的差值加上修正值。//因为差值为2时一个背包为9剩下为1413 1差值就是5.int k sum % 2;int res sum;int[][] dp new int [len][target 1];for(int i 0; i len; i){dp[i][0] 0;}for(int j 0; j target; j){if(j stones[0]){dp[0][j] stones[0];}}for(int i 1; i len; i){for(int j 1; j target; j){if(j stones[i]){dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] stones[i]);}else{dp[i][j] dp[i - 1][j];} }res Math.min(res, target - dp[i][target]);}// for (int i 0; i len; i) {// for (int j 0; j target; j) {// System.out.print(dp[i][j] );// }// System.out.println();// }return 2 * res k;//这是另外一种输出也就不用计算修正值和比较背包之间差值的最小值直接计算背包容量//装的最大的石头重量然后剩余的重量减去背包的重量就是差值。//return (sum - dp[stones.length - 1][target]) - dp[stones.length - 1][target];}
}
494. 目标和
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1
输入nums [1,1,1,1,1], target 3 输出5 解释一共有 5 种方法让最终目标和为 3 。 -1 1 1 1 1 3 1 - 1 1 1 1 3 1 1 - 1 1 1 3 1 1 1 - 1 1 3 1 1 1 1 - 1 3 示例 2
输入nums [1], target 1 输出1 提示
1 nums.length 20 0 nums[i] 1000 0 sum(nums[i]) 1000 -1000 target 1000
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum 0;for(int n : nums){sum n;}int add 0;int diff 0;add (target sum) / 2;//如果和是奇数那肯定是不能得到合适的式子if((target sum) % 2 ! 0 || add 0){return 0;}int [][] dp new int[nums.length 1][add 1];dp[0][0] 1;for(int i 1; i nums.length; i){for(int j 0; j add; j){if(j nums[i - 1]){dp[i][j] dp[i - 1][j - nums[i - 1]] dp[i - 1][j];}else{dp[i][j] dp[i - 1][j];}}}return dp[nums.length ][add];}
}
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 600 1 strs[i].length 100 strs[i] 仅由 0 和 1 组成 1 m, n 100
class Solution {public int findMaxForm(String[] strs, int m, int n) {int len strs.length;int[] zero new int[len];int[] one new int[len];for(int i 0; i len; i){for(int j 0; j strs[i].length(); j){if(strs[i].charAt(j) 0){zero[i] ;}else{one[i];}} }int[][] dp new int[m 1][n 1];for(int k 0; k len; k){for(int i m; i zero[k]; i--){for(int j n; j one[k]; j--){dp[i][j] Math.max(dp[i][j], dp[i - zero[k]][j - one[k]] 1);}}}return dp[m][n];}
}
