解決Java中的磁帶平衡問題
1. 概述
在本教程中，我們將介紹磁帶平衡問題並找到有效的解決方案。這個問題是常見的面試問題。我們將看到解決這個問題的一個好方法依賴於識別數組的平衡索引。
2. 問題的提出
給定一個大小為N的整數數組A ，其中N>=2 ，目標是找到透過在任意位置P拆分數組而創建的兩個非空部分之和之間的最小絕對差（其中0<P<N 。
例如，讓我們考慮數組{-1, 6, 8, -4, 7} ：
-
|A[0] – (A[1] + A[2] + A[3] + A[4])| = |(-1) – (6 + 8 + (-4) + 7)| = 18 -
|(A[0] + A[1]) – (A[2] + A[3] + A[4])| = |((-1) + 6) – (8 + (-4) + 7)| = 6 -
|(A[0] + A[1] + A[2]) – (A[3] + A[4])| = |((-1) + 6 + 8) – ((-4) + 7)| = 10 -
|(A[0] + A[1] + A[2] + A[3]) – A[4]| = |((-1) + 6 + 8 + (-4)) – 7| = 2
由於2小於6和18 ，在這種情況10 ， A的帶平衡為2 。
由於我們的書寫方式，較低索引元素的和通常稱為左和，而較高索引元素的和分別稱為右和。
3. 演算法
計算數組磁帶平衡的簡單解決方案是計算每個索引處左右總和之間的差異。然而，這需要對數組元素進行內部迭代，這會損害演算法的效能。
因此，我們更願意從計算數組的部分和開始。索引i處的部分和是A中索引低於或等於i的所有元素的總和。
換句話說，部分和陣列包含每個索引處的左側和。然後，我們可以注意到索引i處的正確總和是索引i處的總和與部分和之間的差，因為A[i+1] + A[i+2] + … + A[N-1] = (A[0] + A[1] + … + A[i] + A[i+1] + … + A[N-1]) – (A[0] + A[1] + … + A[i]) 。
簡而言之，我們可以從部分和陣列中檢索兩個和。此解只需要對數組進行兩次連續迭代：演算法複雜度為O(N) 。
4. 計算部分和
讓我們計算部分和陣列：索引i處的值是原始陣列中索引低於或等於i的所有元素的總和：
int[] partialSums = new int[array.length];
partialSums[0] = array[0];
for (int i = 1; i < array.length; i++) {
partialSums[i] = partialSums[i - 1] + array[i];
}5. 給定索引處左右和之間的絕對差
讓我們寫一個方法來計算給定索引處的絕對差異。正如我們所說，索引i處的正確總和等於數組總和減去索引i處的部分和。此外，我們可以注意到總數組和也是索引N-1處的部分和陣列的值：
int absoluteDifferenceAtIndex(int[] partialSums, int index) {
return Math.abs((partialSums[partialSums.length - 1] - partialSums[index]) - partialSums[index]);
}我們以一種明確的方式編寫該方法，以明確哪個和是正確的，哪個是左邊的。
6. 檢索磁帶平衡
我們現在可以回顧一下一切：
int calculateTapeEquilibrium(int[] array) {
int[] partialSums = new int[array.length];
partialSums[0] = array[0];
for (int i = 1; i < array.length; i++) {
partialSums[i] = partialSums[i - 1] + array[i];
}
int minimalDifference = absoluteDifferenceAtIndex(partialSums, 0);
for (int i = 1; i < array.length - 1; i++) {
minimalDifference = Math.min(minimalDifference, absoluteDifferenceAtIndex(partialSums, i));
}
return minimalDifference;
}首先，我們計算部分和，然後迭代所有數組索引以查找左右和之間的最小差異。
正如我們將類別命名為TapeEquilibriumSolver一樣，我們現在可以檢查範例陣列是否獲得了正確的結果：
@Test
void whenCalculateTapeEquilibrium_thenReturnMinimalDifference() {
int[] array = {-1, 6, 8, -4, 7};
assertEquals(2, new TapeEquilibriumSolver().calculateTapeEquilibrium(array));
}七、結論
在本文中，我們解決了 Java 中著名的磁帶平衡問題。在實作之前，我們確保選擇了一種有效的演算法。
與往常一樣，程式碼可以在 GitHub 上取得。