我可以用相等的和将数组划分为两部分的次数

本文关键字：划分 两部分 数组 我可以 | 更新日期: 2023-09-27 17:59:52

我想找到多次可以将数组划分为2个非空部分的次数，以便左分区中的元素之和等于右分区中元素之和。

在每个成功的分区之后，我们丢弃左分区或右分区，并使用剩余的分区作为数组继续播放。

最初，有一个数组a，包含N个整数。N <= 2^14

static int Compute(int[] a, int arraySize)
{
     return ComputeNumberOfPartition(a.ToList(), arraySize,  0);
}
static int ComputeNumberOfPartition(List<int> a, int N, int points)
{
     List<int> left = new List<int>();
     List<int> right = new List<int>();
     for (int i = 0; i < N; ++i)
     {
         if (sum(left) <= sum(right)) { left.Add(a[i]);  }
         else                         { right.Add(a[i]); }
     }
     if (sum(left) == sum(right))
     {
         return left.Count >= right.Count ? 
                ComputeNumberOfPartition(left, left.Count, ++points) :
                ComputeNumberOfPartition(right, right.Count, ++points);
     }
     return points;
}
static int sum(List<int> a)
{
     int sum = 0;
     for (int i = 0; i < a.Count; ++i)
     {
         sum += a[i];
     }
     return sum;
}

例如：

input1 3 3 3

output1 0

我们不能分成两个和相等的部分。因此，她的最大可能得分为0。

input2 4 1 0 1 1 0 1

output2 3

我的解决方案很慢。我们如何才能更有效地解决这个问题？这个问题来自hackerrank

我可以用相等的和将数组划分为两部分的次数

public Tuple<int[], int[]> SplitIntArray(int[] array, int index) {
    return new Tuple<int[], int[]>(
        array.Take(index).ToArray(),
        array.Skip(index).ToArray()
    );
}
public string AggregateSumString(int[] array) {
    return array.Select(i => i.ToString()).Aggregate((sumString, next) => 
        String.IsNullOrEmpty(sumString) ? next : String.Format("{0} + {1}", sumString, next))
}

然后，

int[] array;
var results = new List<Tuple<int[], int[]>>();
for (int i = 0; i < array.Length; i++) {
    var tuple = SplitIntArray(array, i);
    if (tuple.Item1.Sum() == tuple.Item2.Sum()) {
        results.Add(tuple);
    }            
}
// results contains all pairs of arrays that sum to the same value.
foreach (var tuple in results) {
    Console.WriteLine(
        String.Format("{0} == {1}", AggregateSumString(tuple.Item1), AggregateSumString(tuple.Item2)));
}

这里有一个非常有效的方法：

static int CalcScore(int[] a)
{
    return CalcScore(a, 0, a.Length - 1, a.Sum(n => (long)n));
}
static int CalcScore(int[] a, int startPos, int endPos, long totalSum)
{
    long leftSum = 0;
    long rightSum = totalSum;
    for (int splitPos = startPos; splitPos < endPos; splitPos++)
    {
        leftSum += a[splitPos];
        rightSum -= a[splitPos];
        if (leftSum > rightSum) break;
        if (leftSum == rightSum)
        {
            int leftScore = CalcScore(a, startPos, splitPos, leftSum);
            int rightScore = CalcScore(a, splitPos + 1, endPos, rightSum);
            return 1 + Math.Max(leftScore, rightScore);
        }
    }
    return 0;
}

主要算法在第二种递归方法中。首先，它使用预先计算的总和。其次，它使用由startPos和endPos定义的包含数组索引范围，这使我们能够避免内存分配。然后，它从开始到结束进行简单的迭代——1将当前值添加到左和，然后从右和中减去，直到左和变得大于右和，在这种情况下，它会提前退出（这是基于值不为负的约束），或者如果两个和相等，它会对拆分进行计数，并递归地添加左部分和右部分的最大拆分。

更新：考虑到只有当总和可以被2整除时，数组范围才能被相等和的两部分分割（因此目标左右和应该是总和的一半），递归部分可以进一步优化如下：

static int CalcScore(int[] a, int startPos, int endPos, long totalSum)
{
    long halfSum = totalSum / 2;
    if (halfSum + halfSum != totalSum) return 0;
    long leftSum = 0;
    for (int splitPos = startPos; splitPos < endPos; splitPos++)
    {
        leftSum += a[splitPos];
        if (leftSum > halfSum) break;
        if (leftSum == halfSum)
        {
            int leftScore = CalcScore(a, startPos, splitPos, halfSum);
            int rightScore = CalcScore(a, splitPos + 1, endPos, halfSum);
            return 1 + Math.Max(leftScore, rightScore);
        }
    }
    return 0;
}
相关文章：