假设我有一组只包含零和一的常量长度数组.我的目标是找出在任何数组旋转之后,数组的元素总和是否不超过1.
例如,假设我有以下三个数组:[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,那么这是不可能的.
到目前为止我能想到的方法的最佳思路是采用两个数组,找到将它们合并在一起的方法,并反转结果.然后,我们获取此结果和下一个数组,并重复此过程.但是,如果存在解决方案,则此方法无法保证找到解决方案.
我的问题是,没有尝试每一个可能的轮换,这个问题的优秀算法是什么？
我正在编写一个Java程序,当我尝试使用字符串时,弹出的建议是com.sun.org.apache.xpath.internal.operations.String.
什么是com.sun.org.apache.xpath.internal.operations.String,什么时候应该使用它？
我已经在线查看,但我找不到文档.
谢谢!