建立企业网站的形式有哪几种网站优化什么意思
刷题记录
- 1049. 最后一块石头的重量 II
- *494. 目标和
- 二维数组
- 滚动数组
- *474. 一和零
1049. 最后一块石头的重量 II
leetcode题目地址
本题与416. 分割等和子集类似。依旧是01背包问题,本题尽可能将石头分为相等(相近)的两堆,然后两堆求差取绝对值既可。dp[j]表示背包容量为j时背包中物品的最大重量。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n ) O(n) O(n)
// java
class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for(int i=0; i<stones.length; i++){sum += stones[i];}int target = sum / 2;int[] dp = new int[target+1];for(int i=0; i<stones.length; i++){for(int j=target; j>=stones[i]; j--){dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);}}return Math.abs(sum-dp[target]*2);}
}
*494. 目标和
leetcode题目地址
二维数组
首先对所有数字求和得到sum。
设添加‘+’的数字和为x,则添加‘-’的数字之和为sum-x,则有:target = x - ( sum - x ).
则,x = ( target + sum ) / 2. 这样就将问题简化为求能够组合(添加‘+’)成 x 的数字和的方案数。
当上式中的除以2无法整除时,说明当前数组无法组合出target的方案,返回0.
要求组合成x的方案数,则将x作为背包容量。
dp[i][j]记录背包容量为 j 时,使用 0-i 的物品可以(恰好)装满背包的方案数。
当 j=0 时,即背包容量为0,若 0-i 中没有0,则只有1种方案就是不放物品;若 0-i 中有 k 个 0,则方案数为 2 ^ k(这里的来由是:每一个0都有2个状态,即选或不选,因此k个0就有 2 ^ k种组合) ;
当 i=0 时,即只使用第0个物品,只有 j == nums[0] 时的方案为1。
- 当访问到物品i时,若背包容量 j 可以放下当前物品 nums[i],则当前物品有两种状态,即选或不选。
- 选:背包需要腾出当前物品大小的空间来存放当前物品,即dp[i-1][j-nums[i]]
- 不选:dp[i-1][j]
则有:dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j]
- 若背包容量 j 放不下当前物品 nums[i], 则dp[i][j] = dp[i-1][j].
时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n 2 ) O(n^2) O(n2)
// java
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i=0; i<nums.length; i++){sum += nums[i];}if(Math.abs(target)>sum) return 0;if((sum+target)%2==1) return 0;int x = (sum+target)/2;int[][] dp = new int[nums.length][x+1];if(nums[0]<=x) dp[0][nums[0]] = 1;int zeroCnt = 0;for(int i=0; i<nums.length; i++){if(nums[i] == 0){zeroCnt++;}dp[i][0] = (int)Math.pow(2, zeroCnt);}for(int i=1; i<nums.length; i++){for(int j=0; j<=x; j++){if(j>=nums[i]){dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];}else{dp[i][j] = dp[i-1][j];}}}return dp[nums.length-1][x];}
}
滚动数组
思路同上,只是有一些小细节需要处理:
- 所有元素都只使用一次,因此遍历背包容量需要从后向前。
- 在初始化第一个元素即dp[0]时,需要注意,若nums[0]为0,则有2种方案(选或不选),反之只有一种方案(不选)。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n ) O(n) O(n)
// java
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i=0; i<nums.length; i++){sum += nums[i];}if((sum+target) % 2 != 0) return 0;if(Math.abs(target) > sum) return 0;int x = (sum+target)/2;int[] dp = new int[x+1];if(x >= nums[0]) dp[nums[0]] = 1;dp[0] = (nums[0]==0) ? 2 : 1;for(int i=1; i<nums.length; i++){for(int j=x; j>=0; j--){if(j >= nums[i]){dp[j] += dp[j-nums[i]];}}}return dp[x];}
}
*474. 一和零
leetcode题目地址
本题是一个二维的01背包问题,背包容量是两个维度,这里使用的是滚动数组思想(二维),若要用普通的dp算法则需要使用三维数组。
dp[i][j] 代表至多 i 个 0,j 个 1 的子集个数。
由于是子集个数,不同于上题的方案数, 因此这里在留出当前物品空间后需要加1.
由于是滚动数组,则在更新时需要与当前值求最大值保留。
即:dp[i][j] = max(dp[i][j], dp[i-zeroCnt][j-oneCnt]+1).
时间复杂度: O ( n 3 ) O(n^3) O(n3) -> O ( k m n ) O(kmn) O(kmn)
空间复杂度: O ( n 2 ) O(n^2) O(n2) -> O ( m n ) O(mn) O(mn)
// java
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];for(int k=0; k<strs.length; k++){int zeroCnt = 0, oneCnt = 0;char[] arr = strs[k].toCharArray();// 统计当前字符串中的0、1个数for(int j=0; j<arr.length; j++){if(arr[j] == '0') zeroCnt++;else oneCnt++;}// 01背包for(int i=m; i>=zeroCnt; i--){for(int j=n; j>=oneCnt; j--){dp[i][j] = Math.max(dp[i][j], dp[i-zeroCnt][j-oneCnt]+1);}}}return dp[m][n];}
}