Java

  • /**
     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:
    
     Flip all the lights.
     Flip lights with even numbers.
     Flip lights with odd numbers.
     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]
    
    
     Note: n and m both fit in range [0, 1000].
    
    
     */
    
    public class Bulb_Switcher_II {
    
    
    
    /*
    
    由于这道题最多只有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;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/bulb-switcher-ii/
    // Time: O(1)
    // Space: O(1)
    // Ref: https://leetcode.com/problems/bulb-switcher-ii/solution/
    class Solution {
    public:
        int flipLights(int n, int m) {
            unordered_set<int> seen;
            n = min(n, 6);
            int shift = 6 - n;
            for (int i = 0; i < 16; ++i) {
                int cnt = __builtin_popcount(i);
                if (cnt % 2 == m % 2 && cnt <= m) {
                    int lights = 0;
                    if ((i >> 0) & 1) lights ^= 0b111111 >> shift;
                    if ((i >> 1) & 1) lights ^= 0b010101 >> shift;
                    if ((i >> 2) & 1) lights ^= 0b101010 >> shift;
                    if ((i >> 3) & 1) lights ^= 0b100100 >> shift;
                    seen.insert(lights);
                }
            }
            return seen.size();
        }
    };
    
  • class Solution:
        def flipLights(self, n, m):
            """
            :type n: int
            :type m: int
            :rtype: int
            """
            if m == 0:
                return 1
            if n >= 3:
                return 4 if m == 1 else 7 if m == 2 else 8
            if n == 2:
                return 3 if m == 1 else 4
            if n == 1:
                return 2
    

All Problems

All Solutions