672. Bulb Switcher II

 

There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.

Suppose n lights are labeled as number [1, 2, 3 …, n], function of these 4 buttons are given below:

  1. Flip all the lights.
  2. Flip lights with even numbers.
  3. Flip lights with odd numbers.
  4. Flip lights with (3k + 1) numbers, k = 0, 1, 2, …

 

Example 1:

Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]

 

Example 2:

Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]

 

Example 3:

Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].

 

Note: n and m both fit in range [0, 1000].

 

这道题是之前那道Bulb Switcher的拓展,但是关灯的方式改变了。现在有四种关灯方法,全关,关偶数灯,关奇数灯,关3k+1的灯。现在给我们n盏灯,允许m步操作,问我们总共能组成多少种不同的状态。博主开始想,题目没有让列出所有的情况,而只是让返回总个数。那么博主觉得应该不能用递归的暴力破解来做,一般都是用DP来做啊。可是想了半天也没想出递推公式,只得作罢。只好去参考大神们的做法,发现这道题的结果并不会是一个超大数,最多情况只有8种。转念一想,也是,如果结果是一个超大数,一般都会对一个超大数10e7来取余,而这道题并没有,所以是一个很大的hint,只不过博主没有get到。博主应该多列几种情况的,说不定就能找出规律。下面先来看一种暴力解法,首先我们先做一个小小的优化,我们来分析四种情况:

第一种情况: 123456789101112131415 ,…

第二种情况:1, 2 ,3, 4 ,5, 6 ,7, 8 ,9, 10 ,11, 12 ,13, 14 ,15,…

第三种情况: 1 ,2, 3 ,4, 5 ,6, 7 ,8, 9 ,10, 11 ,12, 13 ,14, 15 ,…

第四种情况: 1 ,2,3, 4 ,5,6, 7 ,8,9, 10 ,11,12, 13 ,14,15,…

通过观察上面的数组,我们可以发现以6个为1组,都是重复的pattern,那么实际上我们可以把重复的pattern去掉而且并不会影响结果。如果n大于6,我们则对其取余再加上6,新的n跟使用原来的n会得到同样的结果,但这样降低了我们的计算量。

下面我们先来生成n个1,这里1表示灯亮,0表示灯灭,然后我们需要一个set来记录已经存在的状态,用一个queue来辅助我们的BFS运算。我们需要循环m次,因为要操作m次,每次开始循环之前,先统计出此时queue中数字的个数len,然后进行len次循环,这就像二叉树中的层序遍历,必须上一层的结点全部遍历完了才能进入下一层,当然,在每一层开始前,我们都需要情况集合s,这样每个操作之间才不会互相干扰。然后在每层的数字循环中,我们取出队首状态,然后分别调用四种方法,突然感觉,这很像迷宫遍历问题,上下左右四个方向,周围四个状态算出来,我们将不再集合set中的状态加入queue和集合set。当m次操作遍历完成后,队列queue中状态的个数即为所求,参见代码如下:

 

解法一:

class Solution {
public:
    int flipLights(int n, int m) {
        n == (n <= 6) ? n : (n % 6 + 6);
        int start = (1 << n) - 1;
        unordered_set<int> s;
        queue<int> q{{start}};
        for (int i = 0; i < m; ++i) {
            int len = q.size();
            s.clear();
            for (int k = 0; k < len; ++k) {
                int t = q.front(); q.pop();
                vector<int> next{flipAll(t, n), flipEven(t, n), flipOdd(t, n), flip3k1(t, n)};
                for (int num : next) {
                    if (s.count(num)) continue;
                    q.push(num);
                    s.insert(num);
                }
            }
        }
        return q.size();
    }
    
    int flipAll(int t, int n) {
        int x = (1 << n) - 1;
        return t ^ x;
    }
    
    int flipEven(int t, int n) {
        for (int i = 0; i < n; i += 2) {
            t ^= (1 << i);
        }
        return t;
    }
    
    int flipOdd(int t, int n) {
        for (int i = 1; i < n; i += 2) {
            t ^= (1 << i);
        }
        return t;
    }
    
    int flip3k1(int t, int n) {
        for (int i = 0; i < n; i += 3) {
            t ^= (1 << i);
        }
        return t;
    }
};

 

上面那个方法虽然正确,但是有些复杂了,由于这道题最多只有8中情况,所以很适合分情况来讨论:

- 当m和n其中有任意一个数是0时,返回1

- 当n = 1时

只有两种情况,0和1

- 当n = 2时,

这时候要看m的次数,如果m = 1,那么有三种状态 00,01,10

当m > 1时,那么有四种状态,00,01,10,11

- 当m = 1时,

此时n至少为3,那么我们有四种状态,000,010,101,011

- 当m = 2时,

此时n至少为3,我们有七种状态:111,101,010,100,000,001,110

- 当m > 2时,

此时n至少为3,我们有八种状态:111,101,010,100,000,001,110,011

 

解法二:

class Solution {
public:
    int flipLights(int n, int m) {
        if (n == 0 || m == 0) return 1;
        if (n == 1) return 2;
        if (n == 2) return m == 1 ? 3 : 4;
        if (m == 1) return 4;
        return m == 2 ? 7 : 8;
    }
};

 

下面这种简洁到变态的方法是史蒂芬大神观察规律得到的,他自己也在帖子中说不清为啥这样可以,但是就是叼,贴上来纯属娱乐吧~

 

解法三:

class Solution {
public:
    int flipLights(int n, int m) {
        n = min(n, 3);
        return min(1 << n, 1 + m * n);
    }
};

 

类似题目:

Bulb Switcher

 

参考资料:

https://discuss.leetcode.com/topic/102022/c-concise-code-o-1

https://discuss.leetcode.com/topic/102395/2-short-lines-simple-formula

https://discuss.leetcode.com/topic/102227/short-and-clean-java-o-1-solution

https://discuss.leetcode.com/topic/102107/easy-to-understand-java-bfs-solution-o-m

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation