贵阳装饰装修公司网站,sem搜索引擎营销,微网站 具有哪方面的优势,如何制作一个注册网站1049. 最后一块石头的重量 II
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
解题思路#xff1a;尽量让石头分成重量相同的两堆#xff0c;相撞之后剩下的石头最小#xff0c;这样就化解成01背包问题了。
java#xff1…1049. 最后一块石头的重量 II
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
解题思路尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。
java
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int i : stones) {sum i;}int target sum 1;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 sum - 2 * dp[target];}
}
494. 目标和
题目链接
解题思路left right sum而sum是固定的。right sum - left公式来了 left - (sum - left) target 推导出 left (target sum)/2 。
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 ( target 0 sum -target) return 0;if ((target sum) % 2 ! 0) return 0;int size (target sum) / 2;if(size 0) size -size;int[] dp new int[size 1];dp[0] 1;for (int i 0; i nums.length; i) {for (int j size; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[size];}
}
474.一和零
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
解题思路dp[i][j] 可以由前一个strs里的字符串推导出来strs里的字符串有zeroNum个0oneNum个1。dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] 1。
java
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m 1][n 1];int oneNum, zeroNum;for (String str : strs) {oneNum 0;zeroNum 0;for (char ch : str.toCharArray()) {if (ch 0) {zeroNum;} else {oneNum;}}for (int i m; i zeroNum; i--) {for (int j n; j oneNum; j--) {dp[i][j] Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);}}}return dp[m][n];}
}
