2019.10.24 #程式員筆試必備# LeetCode 從零單刷個人筆記整理(持續更新)
github:https://github.com/ChopinXBP/LeetCode-Babel
這題表面上是一道遞歸問題,好在遞歸層數也不是特别多,每層分支也不是很爆炸,是以直接遞歸也不會逾時。不過這題有個更巧妙的方法,能夠轉換成一個01背包問題。
将資料N看成AB兩個部分,A符号全取正,B符号全取負,有
sumA - sumB = S
等式變換有
2 * sumA = S + sumA + sumB = S + sumN = target (令target = S + sumN)
是以隻要在數組裡找到一個集合A滿足
sumA = target / 2
即為一個可行解。問題轉換為01背包問題:
建立動态規劃數組dp,dp[i]代表構成和為i的集合的數量,空集存在是以dp[0] = 1。狀态轉移方程為:
dp[i] += dp[i - num]; (i >= num)
傳送門:目标和
You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
給定一個非負整數數組,a1, a2, …, an, 和一個目标數,S。現在你有兩個符号 + 和 -。對于數組中的任意一個整數,你都可以從 + 或 -中選擇一個符号添加在前面。
傳回可以使最終數組和為目标數 S 的所有添加符号的方法數。
示例 1:
輸入: nums: [1, 1, 1, 1, 1], S: 3
輸出: 5
解釋:
-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
一共有5種方法讓最終目标和為3。
注意:
數組非空,且長度不會超過20。
初始的數組的和不會超過1000。
保證傳回的最終結果能被32位整數存下。
/**
*
* You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -.
* For each integer, you should choose one from + and - as its new symbol.
* Find out how many ways to assign symbols to make sum of integers equal to target S.
* 給定一個非負整數數組,a1, a2, ..., an, 和一個目标數,S。現在你有兩個符号 + 和 -。對于數組中的任意一個整數,你都可以從 + 或 -中選擇一個符号添加在前面。
* 傳回可以使最終數組和為目标數 S 的所有添加符号的方法數。
*
*/
public class TargetSum {
//遞歸
public int findTargetSumWays(int[] nums, int S) {
result = 0;
Solution(nums, 0, 0, S);
return result;
}
private int result;
public void Solution(int[] nums, int idx, int curNum, int sum){
if(idx == nums.length){
result = curNum == sum ? result + 1 : result;
return;
}
Solution(nums, idx + 1, curNum + nums[idx], sum);
Solution(nums, idx + 1, curNum - nums[idx], sum);
}
//動态規劃:01背包
//将資料N看成AB兩個部分,A符号全取正,B符号全取負,有sumA-sumB = S
//等式變換有2sumA = S+sumA+sumB = S+sumN = target
//是以隻要找到一個集合A滿足sumA=target/2,即為一個可行解。
public int findTargetSumWays2(int[] nums, int S) {
int sumN = 0;
for(int num : nums){
sumN += num;
}
//如果數組之和不比S大,或者target是奇數則沒有可行解
if(sumN < S || ((sumN + S) & 1) == 1){
return 0;
}
//dp[i]代表構成和為i的集合的數量,空集存在dp[0] = 1;
int target = (sumN + S) >> 1;
int[] dp = new int[target + 1];
dp[0] = 1;
for(int num : nums){
for(int i = target; i >= num; i--){
dp[i] += dp[i - num];
}
}
return dp[target];
}
}
#Coding一小時,Copying一秒鐘。留個言點個贊呗,謝謝你#