【数组】灯泡开关 Ⅱ

题目描述

房间中有 n 只已经打开的灯泡，编号从 1 到 n 。墙上挂着 4 个开关 。

这 4 个开关各自都具有不同的功能，其中：

开关 1 ：反转当前所有灯的状态（即开变为关，关变为开）
开关 2 ：反转编号为偶数的灯的状态（即 2, 4, ...）
开关 3 ：反转编号为奇数的灯的状态（即 1, 3, ...）
开关 4 ：反转编号为 j = 3k + 1 的灯的状态，其中 k = 0, 1, 2, ...（即 1, 4, 7, 10, ...）
你必须 恰好 按压开关 presses 次。每次按压，你都需要从 4 个开关中选出一个来执行按压操作。

给你两个整数 n 和 presses ，执行完所有按压之后，返回 不同可能状态 的数量。

示例 1：

输入：n = 1, presses = 1
输出：2
解释：状态可以是：
- 按压开关 1 ，[关]
- 按压开关 2 ，[开]

解题思路

这道题可以通过数学方法找到规律，这里我提供一套暴力思路和代码实现，如果直接跑会超时：

• 准备4个计算方法，分别实现开关1、开关2、开关3、开关4的计算；
• 准备一个set用于记录每次计算后的结果，并且做去重操作，从数据上分析重复度很高；
• 准备一个list用于记录做4个计算方法后的结果情况；
• 数据准备阶段将int[] array = new int[n]; 初始化，全部设置成1；并且加入到List种
• 从0到presses进行遍历
  • 遍历List中所有的元素；
    • 执行4中计算方法；
    • 如果不在newSet中，则放到newList中和newSet中；
  • 遍历完成List，更新 list = newList ; set = newSet；
• 遍历完成后返回list.size();

按照上述思路代码实现如下：

import java.util.*;
 
class Solution1 {
    public int flipLights(int n, int presses) {
 
        if (presses == 0) {
            return 1;
        }
 
        int[] array = new int[n];
        Arrays.fill(array, 1);
 
        Set set = new HashSet<>();
        set.add(Arrays.toString(array));
        List<int[]> list = new ArrayList<>();
        list.add(array);
 
        for (int i = 0; i < presses; i++) {
            Set newSet = new HashSet<>();
            List<int[]> newList = new ArrayList<>();
            for (int[] arr : list) {
                int[] arr1 = cal1(arr);
                String s1 = Arrays.toString(arr1);
                if (!newSet.contains(s1)) {
                    newList.add(arr1);
                    newSet.add(s1);
                }
 
                int[] arr2 = cal2(arr);
                String s2 = Arrays.toString(arr2);
                if (!newSet.contains(s2)) {
                    newList.add(arr2);
                    newSet.add(s2);
                }
 
                int[] arr3 = cal3(arr);
                String s3 = Arrays.toString(arr3);
                if (!newSet.contains(s3)) {
                    newList.add(arr3);
                    newSet.add(s3);
                }
 
                int[] arr4 = cal4(arr);
                String s4 = Arrays.toString(arr4);
                if (!newSet.contains(s4)) {
                    newList.add(arr4);
                    newSet.add(s4);
                }
            }
            list = newList;
        }
        return list.size();
    }
 
    int[] cal1(int[] array) {
        int[] res = Arrays.copyOf(array, array.length);
        for (int i = 0; i < res.length; i++) {
            res[i] ^= 1;
        }
        return res;
    }
 
    int[] cal2(int[] array) {
        int[] res = Arrays.copyOf(array, array.length);
        for (int i = 0; i < res.length; i++) {
            if (i % 2 == 0) {
                res[i] ^= 1;
            }
        }
        return res;
    }
 
    int[] cal3(int[] array) {
        int[] res = Arrays.copyOf(array, array.length);
        for (int i = 0; i < res.length; i++) {
            if (i % 2 == 1) {
                res[i] ^= 1;
            }
        }
        return res;
    }
 
    int[] cal4(int[] array) {
        int[] res = Arrays.copyOf(array, array.length);
        for (int i = 0; i < res.length; i++) {
            if (i % 3 == 0) {
                res[i] ^= 1;
            }
        }
        return res;
    }
 
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
 
        System.out.println(solution.flipLights(1, 1));
        System.out.println(solution.flipLights(2, 1));
        System.out.println(solution.flipLights(3, 1));
    }
}

总结

这道题直接按照这个代码实现，执行时会超时；说明这道题不能按照暴力方法来解决，那么可以通过分析规律来解决；这里我暂时不提供解决方案，欢迎回复更简洁、高效的思路。