最近我遇到了一个问题陈述，它说：
Given an array of 0s and 1s, find the position of 0 to be
replaced with 1 to get longest continuous sequence of 1s.
For example : Array- 1,1,0,0,1,0,1,1,1,0,1,1,1
Output - index 9
我尝试了一种蛮力方法，将遇到的每个0替换为1，并在每次替换后计算最大连续重复序列中的1，并每次更新它。
这个问题有更好的方法/算法吗？
这应该有一个一次遍历的解决方案。 总体思路是计算1的数量，并在您进行时将每个零的长度相加。 好吧，不是每个零，只有上一个遇到的1和最长的0。
您需要跟踪两件事：
然后，该过程按以下方式进行：
开始遍历字符串，直到遇到零。 在此过程中跟踪1的数量。
当达到零时，请记住零的位置以及之前的1的数量。
计算到下一个零的1的数量。
返回到上一个零并将新的“1”添加到前一个“1”中。 如果这比最长链更长，则替换最长链。
记住这个零和之前的1。
重复此过程，直到您到达字符串的末尾。
在字符串末尾，返回并将长度添加到前一个零中，并在适当时替换最长链。
您可以想象您需要维护一组数字，其中只允许一个0存在，因此
1) walk over the array,
2) if you are getting a 1,
check a flag if you are already in a set, if no,
then you start one and keep track of the start,
else if yes, you just update the end point of set
3) if you get a 0, then check if it can be included in the set,
(i.e. if only one 0 surrounded by 1 "lonely zero" )
if no, reset that flag which tells you you are in a set
else
is this first time ? (store this 0 pos, initialized to -1)
yes, then just update the zero position
else okk, then previous set, of one..zero..one gets finished here,
now the new set's first half i.e. first consecutive ones are the previous set's last portion,
so set the beginning of the set marker to last zero pos +1, update the zero position.
那么什么时候检查当前集合是否具有最大长度？看，我们只在2-> else部分更新终点，所以在那个点上仅通过max start、max end等进行检查就足够了。
这是我的解决方案。它简洁明了，时间复杂度为O(n)，空间复杂度为O(1)。
public class Q1 {
public Q1() {
}
public static void doit(int[] data) {
int state = 0;
int left, right, max_seq, max_i, last_zero;
left = right = 0;
max_seq = -1;
max_i = -1;
// initialization
right = data[0];
last_zero = (data[0]==0) ? 0 : -1;
for (int i = 1; i < data.length; i++) {
state = data[i - 1] * 10 + data[i];
switch (state) {
case 00: //reset run
left = right = 0;
last_zero = i;
break;
case 01: // beginning of a run
right++;
break;
case 10:// ending of a run
if(left+right+1>max_seq){
max_seq = left+right+1;
max_i = last_zero;
}
last_zero = i; //saving zero position
left = right; // assigning left
right = 0; // resetting right
break;
case 11: // always good
right++;
break;
}
}
//wrapping up
if(left+right+1>max_seq){
max_seq = left+right+1;
max_i = last_zero;
}
System.out.println("seq:" + max_seq + " index:" + max_i);
}
public static void main(String[] args) {
//Q1.doit(new int[] { 1,1,0,0,1,0,1,1,1,0,1,1,1 });
Q1.doit(new int[] { 1,1,0,0,1,0,1,1,1,0,1,1,1 });
}
}
这里有一个稍微不同的算法
public static int zeroIndexToGetMaxOnes(int[] binArray) {
int prevPrevIndex = -1, prevIndex = -1,currentLenght= -1, maxLenght = -1, requiredIndex = -1;
for (int currentIndex = 0; currentIndex < binArray.length; currentIndex++) {
if (binArray[currentIndex] == 0) {
if (prevPrevIndex != -1) {
currentLenght = currentIndex - (prevPrevIndex + 1);
if (currentLenght > maxLenght) {
maxLenght = currentLenght;
requiredIndex = prevIndex;
}
}
prevPrevIndex = prevIndex;
prevIndex = currentIndex;
} else {// case when last element is not zero, and input contains more than 3 zeros
if (prevIndex != -1 && prevPrevIndex != -1) {
currentLenght = currentIndex - (prevPrevIndex + 1);
if (currentLenght > maxLenght) {
maxLenght = currentLenght;
requiredIndex = prevIndex;
}
}
}
}
if (maxLenght == -1) { // less than three zeros
if (prevPrevIndex != -1) { // 2 zeros
if (prevIndex > (binArray.length - prevPrevIndex - 1)) {
requiredIndex = prevPrevIndex;
} else {
requiredIndex = prevIndex;
}
} else { // one zero
requiredIndex = prevIndex;
}
}
return requiredIndex;
}
这里是单元测试
@Test
public void replace0ToGetMaxOnesTest() {
int[] binArray = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1};
int index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
assertThat(index, is(9));
binArray = new int[]{1,0,1,1,1,0};
index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
assertThat(index, is(1));
binArray = new int[]{0,1,1,1,0,1};
index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
assertThat(index, is(4));
binArray = new int[]{1,1,1,0,1,0};
index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
assertThat(index, is(3));
binArray = new int[]{0,1,1,1,0};
index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
assertThat(index, is(4));
binArray = new int[]{1,1,1,1,0};
index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
assertThat(index, is(4));
binArray = new int[]{0,1,1,1,1};
index = ArrayUtils.zeroIndexToGetMaxOnes(binArray);
assertThat(index, is(0));
}
使用动态规划可以解决这段代码。 时间复杂度为O(n)，空间复杂度为O(n)。
public static int Flipindex(String mystring){
String[] arr = mystring.split(",");
String [] arrays= new String[arr.length];
for(int i=0;i<arr.length;i++){
arrays[i]="1";
}
int lastsum = 0;
int[] sumarray =new int[arr.length];
for(int i=0;i<arr.length;i++){
if(!arr[i].equals(arrays[i])){
++lastsum;
}
sumarray[i]=lastsum;
}
int [] consecsum = new int [sumarray[sumarray.length-1]+1];
for(int i: sumarray){
consecsum[i]+=1;
}
int maxconsecsum=0,startindex=0;
for(int i=0;i<consecsum.length-1;i++){
if((consecsum[i]+consecsum[i+1])>maxconsecsum){
maxconsecsum=(consecsum[i]+consecsum[i+1]);
startindex=i;
}
}
int flipindex=0;
for(int i=0;i<=startindex;i++){
flipindex+=consecsum[i];
}
return flipindex;
}
public static void main(String[] args) {
String s= "1,1,0,0,1,0,1,1,1,0,1,1,1";
System.out.println(Flipindex(s));
}
通过控制台的试验，我得到了这个结果，修补一下边缘情况，然后你就可以开始了。
function getIndices(arr, val) {
var indexes = [], i = -1;
while ((i = arr.indexOf(val, i+1)) != -1){
indexes.push(i);
}
return indexes;
}
var a = [1,1,1,1,1,0,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0];
var z = getIndices(a, 0);
z.unshift(0);
var longestchain = 0;
var target = 0;
for(var i=0;i<z.length;i++) {
if(i == 0) { //first element
longestchain = z[i] + z[i+1];
target = i;
} else if (i == z.length-1) { //last element
var lastDistance = Math.abs(z[i] - z[i-1]);
if(lastDistance > longestchain) {
longestchain = lastDistance;
target = i;
}
} else {
if(Math.abs(z[i] - z[i+1]) > 1) { //consecutive 0s
//look before and ahead
var distance = Math.abs(z[i-1] - z[i]) + Math.abs(z[i] - z[i+1]);
if(distance > longestchain) {
longestchain = distance;
target = i;
}
}
}
}
console.log("change this: " + z[target]);
空间复杂度 - O(1)
时间复杂度 - O(n)
A = map(int, raw_input().strip().split(' '))
left = 0 #Numbers of 1 on left of current index.
right = 0 #Number of 1 on right of current index.
longest = 0 #Longest sequence so far
index = 0
final_index = 0 # index of zero to get the longest sequence
i = 0
while i < A.__len__():
if A[i] == 0:
left = right
index = i
i += 1
right = 0
while i < A.__len__() and A[i] != 0:
right += 1
i += 1
if left + right + 1 > longest:
final_index = index
longest = left + right + 1
else:
right += 1
i += 1
print final_index, longest
这段C代码实现基于@gordon-linoff以上提供的算法。
int maxOnesIndex1(bool arr[], int n)
{
int prevZeroPos = 0;
int oldOneCnt = 0;
int newOneCnt = 0;
int longestChainOfOnes = 0;
int longestChainPos = 0;
int i;
for(i=0; i<n; i++)
{
if(arr[i]!=0)
{
oldOneCnt++;
}
else // arr[i] == 0
{
prevZeroPos = i;
newOneCnt = 0;
// move by one to find next sequence of 1's
i++;
while(i<n && arr[i] == 1)
{
i++;
newOneCnt++;
}
if((oldOneCnt+newOneCnt) > longestChainOfOnes)
{
longestChainOfOnes = oldOneCnt+newOneCnt+1;
longestChainPos = prevZeroPos;
}
oldOneCnt = 0;
i = prevZeroPos;
}
}
if((oldOneCnt+newOneCnt) > longestChainOfOnes)
{
longestChainOfOnes = oldOneCnt+newOneCnt+1;
longestChainPos = prevZeroPos;
}
return longestChainPos;
}
def sol(arr):
zeros = [idx for idx, val in enumerate(arr) if val == 0]
if len(arr) == 0 or len(zeros) == 0:
return None
if len(arr) - 1 > zeros[-1]:
zeros.append(len(arr))
if len(zeros) == 1:
return zeros[0]
if len(zeros) == 2:
return max(zeros)
max_idx = None
diff = 0
for i in range(len(zeros) - 2):
# Calculating the difference of i+2 and i, since i+1 should be filled with 1 to find the max index
if zeros[i+2] - zeros[i] > diff:
diff = zeros[i + 2] - zeros[i] - 1
max_idx = zeros[i+1]
return max_idx
arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]
print(sol(arr))
arr = [0, 1]，那么你的代码返回值是2，而正确答案应该是0。 - plpm