我遇到了一個需要建議的磁區問題。我得到了一個長度為偶數的一維陣列。我需要撰寫一個布爾方法來確定是否可以將陣列劃分為 2 個大小相等且總和相等的子陣列，不允許回圈。
例如，陣列 #1 {-3,5,-12,14,-9,13} 將回傳 false，因為 -3 5 -12 14 = -9 13，但是在左側有 4 個元素在另一邊 2。
陣列 #2 將回傳 true：{-3,14,12,5,-9,13} : -3 5 14 = 12 - 9 13
這是我到目前為止所做的：
public static boolean canBeDividedEqually(int[] arr)
{
if (arr.length %2 ==0){
return canBeDividedEquallyHelper(arr, 0, 0, 0);
}
return false;
}
public static boolean canBeDividedEquallyHelper(int[] arr, int i, int sum1, int sum2)
{
if (i == arr.length){
return sum1 == sum2;}
return canBeDividedEquallyHelper(arr, i 1, sum1 arr[i], sum2) ||
canBeDividedEquallyHelper(arr, i 1, sum1, sum2 arr[i]);
}
對于案例#2，它將按預期回傳true，但對于案例#1，它也會回傳true。我需要添加一個條件，該條件將取消型別 case #1 的陣列的資格。
uj5u.com熱心網友回復：
你快到了。除了總和，還要傳遞元素數：
public class Solver
{
public static boolean canBeDividedEqually(int[] arr)
{
return canBeDividedEquallyHelper(arr, 0, 0, 0, 0, 0);
}
public static boolean canBeDividedEquallyHelper(int[] arr, int i, int nb1, int sum1, int nb2, int sum2)
{
if (i == arr.length)
return nb1 == nb2 && sum1 == sum2;
return canBeDividedEquallyHelper(arr, i 1, nb1 1, sum1 arr[i], nb2, sum2) ||
canBeDividedEquallyHelper(arr, i 1, nb1, sum1, nb2 1, sum2 arr[i]);
}
public static void main(String[] args)
{
System.out.println(canBeDividedEqually(new int[]{-3, 5, -12, 14, -9, 13})); // false
System.out.println(canBeDividedEqually(new int[]{-3, 14, 12, 5, -9, 13})); // true
}
}
uj5u.com熱心網友回復：
試試這個。
static boolean canPartitioning(int[] arr) {
return new Object() {
int length = arr.length, half = length / 2;
boolean partition(int i, int selected, int sum, int rest) {
if (i >= length)
return selected == half && sum == rest;
return selected < half && partition(i 1, selected 1, sum arr[i], rest)
|| partition(i 1, selected, sum, rest arr[i]);
}
}.partition(0, 0, 0, 0);
}
public static void main(String[] args) {
System.out.println(canPartitioning(new int[] {-3, 5, -12, 14, -9, 13}));
System.out.println(canPartitioning(new int[] {-3, 14, 12, 5, -9, 13}));
}
輸出：
false
true
uj5u.com熱心網友回復：
這是一個不使用回圈的解決方案，
static int[] arrA, arrB;
public static boolean equalSplit(int[] arr) {
//Step 1
if (arr.length % 2 == 0) {
int sumA = 0, sumB = 0; // Two int variables to store the value of sum.
// Initializing the two new arrays with equal length.
arrA = new int[arr.length / 2];
arrB = new int[arr.length / 2];
// Copying the elements from the given array to the new arrays.
arrA = createArray(arrA, 0, arr, 0);
arrB = createArray(arrB, 0, arr, arr.length / 2);
//Calculating and storing the sum in the variables.
sumA = arraySum(arrA, arrA.length);
sumB = arraySum(arrB, arrB.length);
return sumA == sumB; // Checking the codition
} else {
return false;
}
}
private static int[] createArray(int[] arr, int index, int[] copyFrom, int copyFromIndex) {
if(index == arr.length) return arr;
arr[index] = copyFrom[copyFromIndex];
index ;
copyFromIndex ;
return createArray(arr, index, copyFrom, copyFromIndex);
}
private static int arraySum(int[] arr, int N) {
if (N <= 0) return 0;
return (arraySum(arr, N - 1) arr[N - 1]);
}
我對這個問題的態度是，
步驟 1 -> 檢查是否可以將給定的陣列拆分為兩個相等的陣列。如果是，接下來是第 2 步或回傳 false 而沒有任何進一步的步驟。
步驟 2 -> 使用遞回將給定的陣列元素復制到兩個不同但相等的陣列中。
步驟 3 -> 對新填充的兩個陣列求和并將其存盤在兩個不同的變數中。
第 4 步 -> 如果兩個新填充的陣列的總和相等，則函式回傳 true 否則回傳 false。
解釋 ：
創建兩個新的整數陣列，只有當給定的陣列可以分成兩個相等的部分時，它們才會被填充。這里是 arrA 和 arrB。
檢查給定陣列的長度是否可以被二整并有0個余數，因為這可以回答“這個陣列可以分為兩個相等的部分嗎？”的問題。此答案中的一段代碼是 arr.length % 2 == 0。如果給定的陣列滿足此條件，則將執行下面給出的步驟，否則將回傳 false。
初始化兩個整數變數以存盤兩個等分陣列的 Sum 值。
初始化兩個新創建的陣列，陣列長度為給定陣列的一半，即arr.length / 2。
然后將給定陣列元素的前半部分復制到第一個新初始化的陣列，然后將后半部分復制到第二個陣列。為了實作這個createArray(int[] arr, int index, int[] copyFrom, int copyFromIndex)方法被使用。arr 是傳遞要復制到的陣列的引數，index 應該是 0 因為它用作新創建的陣列的索引，copyFrom 是給定陣列的引數，其中包含所有元素，copyFromIndex 用于開始復制給定索引中的元素。
然后使用遞回函式計算總和并將其存盤在之前創建的單獨變數中。這里使用的函式是arraySum(int[] arr, int N).
回傳兩個 sum 變數是否相等。
uj5u.com熱心網友回復：
如果允許更改元素順序，則必須檢查陣列的每個可能排列：
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] a = {-3, 5, -12,14,-9,13};
int[] b = {-3,14, 12, 5,-9,13};
System.out.println(isEquallySplittable(a));
System.out.println(isEquallySplittable(b));
}
public static boolean isEquallySplittable(int[] array){
long arraySum = arraySum(array);
if(arraySum % 2 != 0) return false; //can not split an even sum by half
return isEquallySplittable(array, 0, 0, arraySum);
}
public static boolean isEquallySplittable(int[] array, int indexFrom, int indexTo, long sumArray){
if(indexTo == indexFrom) {
indexTo ;
}
if(indexTo >= array.length) {
indexTo = 0;
indexFrom ;
}
if(indexFrom >= array.length) return false;
long sumHalfArray = arraySum(Arrays.copyOf(array, array.length/2)); //sum first half of the array
if(sumArray == sumHalfArray * 2 ){
System.out.println(Arrays.toString(array) " can be split into 2 equal arrays");
return true;
}
//next permutation
int temp = array[indexTo];
array[indexTo] = array[indexFrom];
array[indexFrom] = temp;
return isEquallySplittable(array, indexFrom, indexTo, sumArray);
}
public static long arraySum(int[] arr) {
return arraySum(arr, 0, 0);
}
private static long arraySum(int[] arr, int index, long sum) {
if (index >= arr.length ) return sum;
sum = arr[index ];
return arraySum(arr,index,sum);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/392907.html