假设我有一组仅包含0和1的定长数组。我的目标是找出是否在任何数组旋转后,该数组元素之和不超过1。
例如,假设我有以下三个数组:
现在,我的问题是,如何快速确定这对于任意数量的数组是否可能?例如,无法旋转
当前的启发式算法是:显然,如果长度为n的数组之和超过n,则显然不可能。目前我能想到的最好的方法是,取两个数组,并找到将它们合并在一起的方法,然后将结果反转。然后,我们将这个结果和下一个数组一起使用,重复此过程。但是,此方法不能保证找到解决方案。
我的问题是,在尝试每种可能的旋转之前,如何解决这个问题的好算法?
例如,假设我有以下三个数组:
[1, 0, 0, 0]
、[1, 0, 1, 0]
和 [1, 0, 0, 0]
。我可以将第二个数组旋转一个元素,将第三个数组旋转两个元素,得到数组 [1, 0, 0, 0], [0, 1, 0, 1], [0, 0, 1, 0]
,其元素之和为 [1, 1, 1, 1]
。但是如果我没有应用这些旋转,我会得到一个和为[3, 0, 1, 0]
的结果,其中一个元素(即3)大于1,这不符合我的要求。现在,我的问题是,如何快速确定这对于任意数量的数组是否可能?例如,无法旋转
[1, 0, 0, 0], [1, 0, 1, 0], [1, 0, 1, 0]
,使得总和的元素不超过1。当前的启发式算法是:显然,如果长度为n的数组之和超过n,则显然不可能。目前我能想到的最好的方法是,取两个数组,并找到将它们合并在一起的方法,然后将结果反转。然后,我们将这个结果和下一个数组一起使用,重复此过程。但是,此方法不能保证找到解决方案。
我的问题是,在尝试每种可能的旋转之前,如何解决这个问题的好算法?