/*
 * 给定一个数组arr，长度为N，arr中的值不是0就是1
 * arr[i]表示第i栈灯的状态，0代表灭灯，1代表亮灯
 * 每一栈灯都有开关，但是按下i号灯的开关，会同时改变i-1、i、i+1栈灯的状态
 * 问题一：
 * 如果N栈灯排成一条直线,请问最少按下多少次开关,能让灯都亮起来
 * 排成一条直线说明：
 * i为中间位置时，i号灯的开关能影响i-1、i和i+1
 * 0号灯的开关只能影响0和1位置的灯
 * N-1号灯的开关只能影响N-2和N-1位置的灯
 * 
 * */

暴力版本

   public static int noLoopRight(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0] == 1 ? 0 : 1;
        }
        if (arr.length == 2) {
            return arr[0] != arr[1] ? Integer.MAX_VALUE : (arr[0] ^ 1);
        }
        return f1(arr, 0);
    }
    // arr[0...i-1]的灯，不需要管
    // arr[i......]的灯上，按开关
    // 1) i位置的开关，不改变，走一个分支
    // 2) i位置的开关，改变，走一个分支
    private static int f1(int[] arr, int i) {
        if (i == arr.length) {
            return valid(arr) ? 0 : Integer.MAX_VALUE;
        }
        // 决定，在i位置，不改变开关
        int p1 = f1(arr, i + 1);
        // 决定，在i位置，改变开关
        change1(arr, i);
        int p2 = f1(arr, i + 1);
        change1(arr, i);
        p2 = (p2 == Integer.MAX_VALUE) ? p2 : p2 + 1;
        return Math.min(p1, p2);
    }
    private static void change1(int[] arr, int i) {
        if (i == 0) {
            arr[0] ^= 1;
            arr[1] ^= 1;
        } else if (i == arr.length - 1) {
            arr[i - 1] ^= 1;
            arr[i] ^= 1;
        } else {
            arr[i - 1] ^= 1;
            arr[i] ^= 1;
            arr[i + 1] ^= 1;
        }
    }
    private static boolean valid(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                return false;
            }
        }
        return true;
    }

优良递归版本

• 这个递归函数在前态做决定

!image.png

public static int noLoopMinStep1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0] == 1 ? 0 : 1;
        }
        if (arr.length == 2) {
            return arr[0] != arr[1] ? Integer.MAX_VALUE : (arr[0] ^ 1);
        }
        //不改变0位置的状态
        int p1 = process1(arr, 2, arr[0], arr[1]);
        //改变0位置的状态
        int p2 = process1(arr, 2, arr[0] ^ 1, arr[1] ^ 1);
        if (p2 != Integer.MAX_VALUE) {
            p2++;
        }
        return Math.min(p1, p2);
    }
    // index : 来到的位置，不能在这个位置上做改变！
    // pre：前一个位置的状态，这个是要改变的！
    // prepre：前前状态
    public static int process1(int[] arr, int index, int prepre, int pre) {
        if (index == arr.length) { //pre压中最后一盏灯
            return prepre != pre ? Integer.MAX_VALUE : (pre ^ 1);
        }
        if (prepre == 0) {// 一定要改变
            // pre这个灯，一定要变，pre前灯的状态，改变！ 前前 -> 1
            pre ^= 1;
            int cur = arr[index] ^ 1;
            int next = process1(arr, index + 1, pre, cur);
            return next == Integer.MAX_VALUE ? next : next + 1;
        } else {// 一定不能改变
            return process1(arr, index + 1, pre, arr[index]);
        }
    }

迭代版本

  public static int noLoopMinStep2(int[] arr) {
         if (arr == null || arr.length == 0) {
             return 0;
         }
         if (arr.length == 1) {
             return arr[0] == 1 ? 0 : 1;
         }
         if (arr.length == 2) {
             return arr[0] != arr[1] ? Integer.MAX_VALUE : (arr[0] ^ 1);
         }
         int p1 = traceNoLoop(arr, arr[0], arr[1]);
         int p2 = traceNoLoop(arr, arr[0] ^ 1, arr[1] ^ 1);
         p2 = (p2 == Integer.MAX_VALUE) ? p2 : (p2 + 1);
         return Math.min(p1, p2);
     }
    public static int traceNoLoop(int[] arr, int prepre, int pre) {
        int i = 2;
        int op = 0;
        while (i != arr.length) {
            if (prepre == 0) {
                op++;
                prepre = pre ^ 1;
                pre = arr[i++] ^ 1;
            } else {
                prepre = pre;
                pre = arr[i++];
            }
        }
        return (prepre != pre) ? Integer.MAX_VALUE : (op + (pre ^ 1));
    }