672 Bulb Switcher II

672. Bulb Switcher II

题目: https://leetcode.com/problems/Bulb-Switcher-II/

难度:

Medium

思路

这道题又是一个数学题。找规律呀找规律。 我们只需要考虑当 n<=2 and m < 3 的特殊情形。因为当 n >2 and m >=3, 结果肯定是 8. The four buttons:

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

如果我们使用了 button 1 和 2, 其效果等同于使用 button 3 。 类似的..

• 1 + 2 --> 3
• 1 + 3 --> 2
• 2 + 3 --> 1

所以，只有 8 种情形。

灯全亮, 操作1, 操作2, 操作3, 操作4, 操作1+4, 操作2+4, 操作3+4

并且当 n>2 and m>=3 时，我们就能够获得所有的情形。

m\n	0	1	2	3	4
0	1	1	1	1	1
1	1	2	3	4	4
2	1	2	4	7	7
3	1	2	3	8	8

class Solution(object):
    def flipLights(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        if m * n == 0: return 1
        if n == 1: return 2
        if n == 2: return 4 - (m % 2)
        if m == 1: return 4
        if m == 2: return 7
        return 8

还有两位大佬的两行解法：

class Solution(object):
    def flipLights(self, n, m):
        m, n = min(3, m), min(3, n)
        return 1 if n * m == 0 else self.flipLights(n - 1,  m) + self.flipLights( n - 1, m - 1) 

class Solution(object):
    def flipLights(self, n, m):
        n = min(n, 3)
        return min(1<<n, 1+m*n)

---

我们一直在努力

apachecn/AiLearning

---