自己的ip做网站,asp企业网站模版,太原 网站建设公司,怡梦姗网站做么一、分割等和子集
题目#xff1a;
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。 示例 1#xff1a;
输入#xff1a;nums [1,5,11,5]
输出#xff1a;true
解释#xff1a;数组可以分…一、分割等和子集
题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。
思路
可以用0-1背包的思路去思考问题首先对数组中所有元素的总和取半对第一层循环遍历数组第二层循环对加入的值比较取一个放入或者是不放入之间的最大值每循环一次判断是否达到了对应取半的值如果达到了说明剩下的值与其相等返回true
代码
public boolean canPartition(int[] nums) {int n nums.length;// 如果数组为空或长度为0无法分割为两个相等的子集if (nums null || nums.length 0)return false;// 计算数组元素的总和int sum 0;for (int i : nums) {sum i;}// 如果总和为奇数则无法分割为两个相等的子集if (sum % 2 1)return false;// 计算每个子集的目标和总和的一半int target sum / 2;// 创建动态规划数组dp[j] 表示是否可以达到和 jint[] dp new int[target 1];// 遍历每个数组元素for (int i 0; i n; i) {// 从目标和开始倒序遍历以避免使用当前元素多次for (int j target; j nums[i]; j--) {// 更新 dp[j]如果可以通过当前元素 nums[i] 达到和 jdp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}// 如果已经可以达到目标和直接返回 trueif (dp[target] target)return true;}// 返回 dp[target] 是否等于目标和来确定是否可以分割成两个相等的子集return dp[target] target;
}基本检查 确保数组 nums 不为空且长度大于 0。 总和计算 计算数组 nums 的总和 sum。 奇数检查 如果总和是奇数无法将其分割成两个相等的子集直接返回 false。 目标值设定 计算目标值 target即总和的一半。 动态规划数组初始化 使用 dp 数组其中 dp[j] 表示是否可以用数组中的元素组成和为 j 的子集。 动态规划更新 遍历数组中的每个元素从 target 向下更新 dp 数组。对于每个元素 nums[i]更新 dp[j]表示是否可以达到和 j。 检查目标和 如果在遍历过程中dp[target] 达到目标和则返回 true。 最终结果 返回 dp[target] 是否等于目标和决定是否可以分割数组成两个和相等的子集。 二、最后一块石头的重量2
题目
有一堆石头用整数数组 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
思路 首先定义dp数组这里的dp数组表示容量为 j 的背包可容的最大重量为dp[j]与分割等和子集类似也需要取数组总和的一半这样才能保证取到的两部分石头相撞后的数值一定最小这里明确总和为sum取整数半为target那么其最小剩余的重量就为 (sum-target)-target递推表达式为 dp[j] max(dp[j]dp[j-stone[i]]stone[i])
代码
public int lastStoneWeightII(int[] stones) {int n stones.length;// 如果数组为空或长度为0则返回0if (stones null || stones.length 0)return 0;// 计算所有石头的总重量int sum 0;for (int i : stones) {sum i;}// 目标是总重量的一半int target sum / 2;// 创建动态规划数组 dpdp[j] 表示能否通过选择一些石头获得重量 jint[] dp new int[target 1];// 遍历每个石头for (int i 0; i n; i) {// 从目标重量向下遍历以避免重复使用同一个石头for (int j target; j stones[i]; j--) {// 更新 dp[j]如果通过当前石头 stones[i] 能达到重量 jdp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);}}// 返回最终结果总重量减去两倍的 dp[target]即为最后剩余的石头重量return sum - dp[target] - dp[target];
}基础检查 确保数组 stones 不为空且长度大于 0。 总和计算 计算所有石头的总重量 sum。 目标值设定 目标值 target 是总重量的一半。 动态规划数组初始化 使用 dp 数组dp[j] 表示是否可以通过选择一些石头组成重量 j。 动态规划更新 遍历每个石头 stones[i]从目标值 target 向下更新 dp 数组确保每个石头只被使用一次。 结果计算 最终结果是 sum - dp[target] - dp[target]其中 dp[target] 是最接近目标值的重量两倍的 dp[target] 代表了通过选择这些石头可以达到的最大重量。剩余的就是最后剩余的石头重量。 今天的学习就到这里
