Skip to content

Latest commit

 

History

History
105 lines (80 loc) · 2.59 KB

0672._Bulb_Switcher_II.md

File metadata and controls

105 lines (80 loc) · 2.59 KB

672. Bulb Switcher II

难度: Medium

刷题内容

原题连接

内容描述

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]
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].

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

这道题又是一个数学题。找规律呀找规律。 我们只需要考虑当 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

思路 2

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

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)