最小交替二进制系列计数(抛硬币问题)

Minimum alternating binary series count (coin flip problem)

给定连续 N 个硬币,我需要计算使该系列完美交替所需的最小变化。例如,[1, 1, 0, 1, 1] 必须变为 [0, 1, 0, 1, 0],这只需要 2 次更改。请注意 [1, 0, 1, 0, 1] 是不正确的,因为它需要 3 处更改。我这里有一个主要功能程序:

public int solution(int[] num) {
    int[] sequence = num;//Make a copy of the incoming array so I can change values
    int flips = 0;//Store values here
    boolean changeNeeded = false;//How to know if a flip must occur
    for (int i = 1; i < sequence.length; i++) {//Count entire array, starting with index 1 so the pprevious entry can be checked for diplicity
        if (sequence[i] == sequence[i - 1]) {//checking previous entry
            flips++;//increment neccessary flip
            changeNeeded = true;//Make sure to change the value so it doesn't get incremented twice
        }
        if (sequence[i] == 1 && changeNeeded) {//Change a 1 to a 0
        sequence[i] = 0; 
        changeNeeded = false;
        } else if (sequence[i] == 0 && changeNeeded) {//change a 0 to a 1
        sequence[i] = 1;
        changeNeeded = false;
        }
    }
    return flips;//done
}

但是,因为它是从index = 1开始计数的,所以不能正确解决上面的问题。我还没有找到一种方法来计算结束边界并保持在边界内。

解决方案: 我设法调整了我的代码,直到它正常工作,尽管这是“我不知道为什么,但这有效”的答案之一。我标记的答案要好得多。

boolean changeNeeded = false; //Just as the name says, it checks for when an integer change if it is necessary
    int flips = 0;
    int[] sequence = num; //So I can copy and edit the incoming array if needed
    for (int i = 0; i < num.length; i++) {
        sequence[i] = A[i];//Copy all elements
    }
    for (int i = 0; i < sequence.length - 1; i++) { //Count the array, capping our count so we avoid indexOutOfBounds errors
        
        if (sequence[i] == sequence[i + 1]) //Compare current to next entry
        {
            flips++;//increment a fix
            changeNeeded = true;//tell the system that a digit needs changed
        }
        if (sequence[i] == 1 && changeNeeded) //change a 1 to a 0
        {
            sequence[i] = 0;
            changeNeeded = false; //reset our change detection
        }
        else if (sequence[i] == 0 && changeNeeded) //change a 0 to a 1
        {
            sequence[i] = 1;
            changeNeeded = false; //see above
        }
    }
    if (sequence[0] == sequence[1]) {//The above system skips properly adjusting the 0th index, so it needs to be checked after
        flips++;
        //If checked within the loop it will add an extra, unnecessary flip. I don't know why.
    }
    return flips;

根本不需要修改原数组

IIUC 有两种选择:您需要将序列更改为 1010... 或 0101... 您应该计算 return 分钟和

需要多少更改?

因此,对于每个偶数索引,如果值不为 0,则递增 changesWithLeading0。 对于每个奇数索引,如果值不为 1,则递增 changesWithLeading0。

对于 changesWithLeading1 你做相反的事情。

public int solution(int[] num) {
  int changesWithLeading0 = 0;
  int changesWithLeading1 = 0;
  for int(i = 0; i < sequence.length; i++) {
    if (sequence[i] == 1 - (i % 2)) {
      changesWithLeading0 ++;
    }
    if (sequence[i] == i % 2) {
      changesWithLeading1 ++;
    }
  }
  return Math.min(changesWithLeading0, changesWithLeading1);
}