截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666
前面我們講過520，回溯演算法解火柴拼正方形，和這題類似，具體可以看下，第520題可以認為是把陣列分隔成4個元素和相等的子集，而這題是把陣列分隔成2個元素和相等的子集，如果資料量比較少的話，第520題的答案稍微修改一下就是這題的答案了，但如果資料量大的話就會超時，所以這題不能使用回溯演算法來解決，我們可以使用動態規劃，
這題判斷把陣列分成兩份，這兩份的元素和是否相等，首先我們需要計算陣列中所有元素的和sum，然后判斷sum是否是偶數：
如果不是偶數，說明不可能分割成完全相等的兩份，直接回傳false，
如果是偶數，我們只需要判斷是否存在一些元素的和等于sum/2，如果等于sum/2，那么剩下的肯定也等于sum/2，說明我們可以把陣列分為元素和相等的兩部分，
那么這個時候問題就很明朗了，假設sum/2是一個背包的容量，我們只需要找出一些元素把他放到背包中，如果背包中元素的最大和等于sum/2，說明我們可以把陣列分成完成相等的兩份，這不就是經典的0-1背包問題嗎，之前也講過371，背包問題系列之-基礎背包問題，具體可以看下，這里就不在重復介紹，我們在來找一下他的遞推公式，定義dp[i][j]表示把第i個物品放到容量為j的背包中所獲得的的最大值，
第i個物品的值是nums[i-1]：
如果nums[i-1]>j，說明背包容量不夠，第i件物品放不進去，所以我們不能選擇第i個物品，那么
dp[i][j]=dp[i-1][j]；
如果nums[i-1]<=j，說明可以把第j個物品放到背包中，我們可以選擇放也可以選擇不放，取最大值即可，如果放就會占用一部分背包容量，最大價值是
dp[i][j]=dp[i-1][j-nums[i-1]]+nums[i-1]
如果不放
dp[i][j]=dp[i-1][j]；
取兩者的最大值
最終遞推公式如下
if (j >= nums[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i-1][j - nums[i - 1]] + nums[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
我們來看下最終代碼
public boolean canPartition(int[] nums) {
//計算陣列中所有元素的和
int sum = 0;
for (int num : nums)
sum += num;
//如果sum是奇數，說明陣列不可能分成完全相等的兩份
if ((sum & 1) == 1)
return false;
//sum除以2
int target = sum >> 1;
int length = nums.length;
int[][] dp = new int[length + 1][target+1];
for (int i = 1; i <= length; i++) {
for (int j = 1; j <= target; j++) {
//下面是遞推公式
if (j >= nums[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i-1][j - nums[i - 1]] + nums[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
//判斷背包最大是否能存放和為target的元素
return dp[length][target] == target;
}
我們還可以這樣寫，二維陣列dp是boolean型別，dp[i][j]表示陣列中前i個元素的和是否可以組成和為j，很明顯dp[0][0]=true，表示前0個元素（也就是沒有元素）可以組成和為0，代碼如下
public boolean canPartition(int[] nums) {
//計算陣列中所有元素的和
int sum = 0;
for (int num : nums)
sum += num;
//如果sum是奇數，說明陣列不可能分成完全相等的兩份
if ((sum & 1) == 1)
return false;
//sum除以2
int target = sum >> 1;
int length = nums.length;
boolean[][]dp = new boolean[length + 1][target+1];
dp[0][0] = true;//base case
for (int i = 1; i <= length; i++) {
for (int j = 1; j <= target; j++) {
//遞推公式
if (j >= nums[i - 1]) {
dp[i][j] = (dp[i - 1][j] || dp[i-1][j - nums[i - 1]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[length][target];
}
我們看到上面二維陣列計算的時候當前值只和上面一行有關，所以我們可以把它改成一維的，注意第二個for回圈要倒敘，否則會把前面的值給覆寫掉導致結果錯誤，仔細看一下
dp[j] = (dp[j] || dp[j - nums[i - 1]]);
就明白了，相當于同一行后面的值依賴前面的，如果不是倒敘，前面的值被修改了，在計算后面的就會導致錯誤，我們來看下代碼，
public boolean canPartition(int[] nums) {
//計算陣列中所有元素的和
int sum = 0;
for (int num : nums)
sum += num;
//如果sum是奇數，說明陣列不可能分成完全相等的兩份
if ((sum & 1) == 1)
return false;
//sum除以2
int target = sum >> 1;
int length = nums.length;
boolean[] dp = new boolean[target + 1];
dp[0] = true;//base case
for (int i = 1; i <= length; i++) {
//注意這里j要倒敘
for (int j = target; j >= 1; j--) {
//遞推公式
if (j >= nums[i - 1]) {
dp[j] = (dp[j] || dp[j - nums[i - 1]]);
}
//else {//這里省略
// dp[j] = dp[j];
//}
}
}
return dp[target];
}
DFS解決
每種元素可以選擇也可以不選擇，只需要判斷他所有的可能組合中，元素和是否有等于sum/2的，我們可以把它看做是一棵二叉樹，左子節點表示選擇當前元素，右子節點表示不選擇當前元素，如下圖所示，橙色節點表示選擇當前元素，藍色表示不選擇，
我們來看下代碼
public boolean canPartition(int[] nums) {
//計算陣列中所有元素的和
int sum = 0;
for (int num : nums)
sum += num;
//如果sum是奇數，說明陣列不可能分成完全相等的兩份
if ((sum & 1) == 1)
return false;
return dfs(nums, sum >> 1, 0);
}
private boolean dfs(int[] nums, int target, int index) {
//targe等于0，說明存在一些元素的和等于sum/2，直接回傳true
if (target == 0)
return true;
//如果陣列元素都找完了，或者target小于0，直接回傳false
if (index == nums.length || target < 0)
return false;
//選擇當前元素和不選擇當前元素兩種情況
return dfs(nums, target - nums[index], index + 1)
|| dfs(nums, target, index + 1);
}
但很遺憾的是，因為計算量太大，會導致運行超時，我們可以優化一下，來看下代碼
public boolean canPartition(int[] nums) {
//計算陣列中所有元素的和
int sum = 0;
for (int num : nums)
sum += num;
//如果sum是奇數，說明陣列不可能分成完全相等的兩份
if ((sum & 1) == 1)
return false;
//sum除以2
int target = sum >> 1;
Boolean[][] map = new Boolean[nums.length][target + 1];
return dfs(nums, 0, target, map);
}
private boolean dfs(int[] nums, int index, int target, Boolean[][] map) {
//targe等于0，說明存在一些元素的和等于sum/2，直接回傳true
if (target == 0)
return true;
//如果陣列元素都找完了，或者target小于0，直接回傳false
if (index == nums.length || target < 0)
return false;
//從map中取
if (map[index][target] != null)
return map[index][target];
//選擇當前元素
boolean select = dfs(nums, index + 1, target - nums[index], map);
//不擇當前元素
boolean unSelect = dfs(nums, index + 1, target, map);
//只要有一個為true，就回傳true，否則回傳false
if (select || unSelect) {
map[index][target] = true;
return true;
}
map[index][target] = false;
return false;
}
位運算解決
這里能使用位運算，關鍵在于題中的一些限制條件，比如
- 正整數的非空陣列，
- 每個陣列中的元素不會超過 100，
- 陣列的大小不會超過 200等，
原理很簡單，我們只需要申請一個大小為sum+1的陣列bits[sum+1]，陣列中的數字只能是0和1，我們可以把它想象為一個很長的二進制位，因為int和long型別太短了，我們這里使用的是陣列，然后每遍歷陣列中的一個元素比如m，就把二進制位往左移m位然后在和原來的二進制位進行或運算，最后判斷bits[sum/2]是否是1，如果是1就回傳true，文字敘述不是很直接，我們就以示例1為例來畫個圖看一下
最后你會發現一個規律，就是最后運算的結果只要是1的位置，都可以使用陣列中的元素組合而成，只要是0的都不能使用陣列中的元素組合而成，搞懂了上面的程序，代碼就很容易寫了，因為我們只需要判斷二進制位中中間的那個值是否為1，所以我們只需要計算低位，高位完全不用計算，因為是往左移動的，高位不會對中間的值產生任何影響，所以這里能做一點優化，最后再來看下代碼
public boolean canPartition(int[] nums) {
//計算陣列中所有數字的和
int sum = 0;
for (int n : nums)
sum += n;
//如果sum是奇數，直接回傳false
if ((sum & 1) == 1)
return false;
int len = sum >> 1;
//這里bits的長度是len+1，因為我們只需要計算
//低位就行了，沒必要計算所有的
byte[] bits = new byte[len + 1];
bits[0] = 1;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int size = len - num;
for (int j = size; j >= 0; j--) {
bits[j + num] |= bits[j];
}
//判斷中位數如果是1，說明可以分成兩種相等的
//子集，直接回傳true，不需要再計算了
if ((bits[len] & 1) != 0)
return true;
}
return false;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/303626.html
標籤：其他
下一篇：Scala 必知必會