Skip to content

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)



回到顶部