企业网站适合响应式嘛,广州网站建设优化,做淘宝客建网站要多少费用,建设银行网站首页是多少1049.最后一块石头的重量II
题目要求#xff1a;有一堆石头#xff0c;每块石头的重量都是正整数。
每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 x y。那么粉碎的可能结果如下#xff1a; …1049.最后一块石头的重量II
题目要求有一堆石头每块石头的重量都是正整数。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎
如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下就返回 0。
思路
目标是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就转化成01背包问题了。
dp[j]表示容量为j的背包可以装载的最大重量为dp[j]
遍历顺序如果使用一维dp数组物品遍历的for循环放在外层遍历背包的for循环房子啊内层且内层for循环倒序遍历。
分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum-dp[target]
在计算target时候targetsum/2是向下取整。所以sum-dp[target]一定大于等于dp[target]。那么相撞后剩下的最小石头重量就是(sum-dp[target])-dp[target]
class Solution {
public:int lastStoneWeightII(vectorint stones) {vectorint dp(15001, 0);int sum 0;for (int i 0; i stones.size(); i) {sum stones[i];}int target sum / 2;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] - dp[target];}
};
时间复杂度O(m × n) , m是石头总重量准确的说是总重量的一半n为石头块数空间复杂度O(m)
494.目标和
题目要求给定一个非负整数数组a1, a2, ..., an, 和一个目标数S。现在你有两个符号 和 -。对于数组中的任意一个整数你都可以从 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
思路
目前我们已经有了目标targets假设加法的总和为x那么减法对应的总和就是sum-x。所以我们要求的是x-(sum-x)targetx(targetsum)/2。此时问题就转化为装满容量为x的背包有几种方法。
x的计算是向下取整的所以如果targetsum为奇数那么本提无解。如果S的绝对值大于sum也是无解的。
装满背包有几种方法其实就是一个组合问题了。
递推公式只要有nums[i]凑成dp[j]就有dp[j - nums[i]] 种方法。
那么凑整dp[5]有多少方法呢也就是把 所有的 dp[j - nums[i]] 累加起来。
dp数组的初始化
从递推公式可以看出在初始化的时候dp[0] 一定要初始化为1因为dp[0]是在公式中一切递推结果的起源如果dp[0]是0的话递推结果将都是0。
这里有录友可能认为从dp数组定义来说 dp[0] 应该是0也有录友认为dp[0]应该是1。
其实不要硬去解释它的含义咱就把 dp[0]的情况带入本题看看应该等于多少。
如果数组[0] target 0那么 bagSize (target sum) / 2 0。 dp[0]也应该是1 也就是说给数组里的元素 0 前面无论放加法还是减法都是 1 种方法。
所以本题我们应该初始化 dp[0] 为 1。
可能有同学想了那 如果是 数组[0,0,0,0,0] target 0 呢。
其实 此时最终的dp[0] 32也就是这五个零 子集的所有组合情况但此dp[0]非彼dp[0]dp[0]能算出32其基础是因为dp[0] 1 累加起来的。
dp[j]其他下标对应的数值也应该初始化为0从递推公式也可以看出dp[j]要保证是0的初始值才能正确的由dp[j - nums[i]]推导出来。
确定遍历顺序
我们讲过对于01背包问题一维dp的遍历nums放在外循环target在内循环且内循环倒序。
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for (int i 0; i nums.size(); i) sum nums[i];if (abs(target) sum) return 0;if ((target sum) % 2 1) return 0;int bagSize (target sum) / 2;vectorint dp(bagSize 1, 0);dp[0] 1;for (int i 0; i nums.size(); i) {for (int j bagSize; j nums[i]; --j) {dp[j] dp[j-nums[i]];}}return dp[bagSize];}
};
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 。
思路
本题中strs 数组里的元素就是物品每个物品都是一个
而m 和 n相当于是一个背包两个维度的背包。
只不过这个背包有两个维度一个是m 一个是n而不同长度的字符串就是不同大小的待装物品。
确定dp数组dp table以及下标的含义
dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来strs里的字符串有zeroNum个0oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] 1。
然后我们在遍历的过程中取dp[i][j]的最大值。
所以递推公式dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);
此时大家可以回想一下01背包的递推公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);
对比一下就会发现字符串的zeroNum和oneNum相当于物品的重量weight[i]字符串本身的个数相当于物品的价值value[i]。
这就是一个典型的01背包 只不过物品的重量有了两个维度而已。
dp数组如何初始化
因为物品价值不会是负数初始为0保证递推的时候dp[i][j]不会被初始值覆盖。
确定遍历顺序
01背包一定是外层for循环遍历物品内层for循环遍历背包容量且从后向前遍历
那么本题也是物品就是strs里的字符串背包容量就是题目描述中的m和n。
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1, vectorint (n1, 0));for (string str : strs) {int oneNum 0, zeroNum 0;for (char c : str) {if (c 0) zeroNum;else oneNum;}for (int i m; i zeroNum; --i) {for (int j n; j oneNum; --j) {dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);}}}return dp[m][n];}
};
时间复杂度: O(kmn)k 为strs的长度空间复杂度: O(mn)
