This is the sixth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

Given an array arr of length N, the value in arr is either 0 or 1. Arr [I] indicates the state of the i-th stack light, 0 indicates off, 1 indicates on. Each stack light has a switch, but pressing the switch of the I-th stack light will change the state of i-1, I, and I +1 simultaneously

Question 1: If the N stack lights line up in a straight line, how many times should I press the switch?

Question 2: If the N stack lights are arranged in a circle, how many times can you press the switch at least to make the lights on

A, analysis,

N Stack lights in a straight line:

  1. When I is in the middle position, the switch of I lamp can affect I -1, I and I +1
  2. The switch of lamp 0 can only affect the lamps in position 0 and 1
  3. The switch of the N-1 lamp can only affect the lamps in the N-2 and N-1 positions

N Stack lights arranged in a circle:

  1. When I is in the middle position, the switch of I lamp can affect I -1, I and I +1
  2. The switch of no. 0 lamp can affect the lamps in position N-1, 0 and 1
  3. The switch of the N-1 lamp can affect the lamps in position N-2, N-1 and 0

Try the model from left to right

This left to right trial model is different from the previous one, because the lights in the middle will affect the left and right lights (not fixed), as well as themselves.

Define the function f(I,p,c) : the next position, the previous state, the current state

  1. I represents the position next to the current position
  2. I-1 is the current position
  3. P represents the state of the previous position i-2
  4. C is the status of the current position

For example: arr [0,1,1,0…].

  1. Press the switch at position 0. 0=>1

    I go to 1, I is the next position, so I = 2, the previous state,0 flipped the switch, so it became 1, the current state went from 1 to 0, so f should be f of 2,1,0.

  2. Do not press the switch at position 0

    F (2, 1)

Second, the implementation

    public static int noLoopMinStep(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0] ^ 1;
        }
        if (arr.length == 2) {
            return arr[0] != arr[1]? Integer.MAX_VALUE : (arr[0] ^ 1);
        }
        // Change the state of position 0
        int p1 = process(arr, 2, arr[0], arr[1]);
        // Change the state of position 0
        int p2 = process(arr, 2, arr[0] ^ 1, arr[1] ^ 1);
        if(p2 ! = Integer.MAX_VALUE) { p2++; }return Math.min(p1, p2);
    }

    Nextindex-1 = cur, cur!
    // cur - 1 preStatus
    // cur curStatus
    / / 0... Cur-2 all bright!
    public static int process(int[] arr, int nextIndex, int preStatus, int curStatus) {
        if (nextIndex == arr.length) { // The last switch is now in position
            returnpreStatus ! = curStatus ? (Integer.MAX_VALUE) : (curStatus ^1);
        }
        // Not to the last button!
        // i < arr.length
        if (preStatus == 0) { // Do change
            curStatus ^= 1;
            int cur = arr[nextIndex] ^ 1;
            int next = process(arr, nextIndex + 1, curStatus, cur);
            return next == Integer.MAX_VALUE ? next : (next + 1);
        } else { // It must not be changed
            return process(arr, nextIndex + 1, curStatus, arr[nextIndex]); }}Copy the code

Third, summary

Only one of the two recursions can be executed, further optimization, parameter reuse!

Question 2 is a bit difficult!!