解法一

所有灯泡的状态都和前四个灯泡有关，同一种操作重复两次也没有意义。由此可以大大缩小数据范围。注意考虑边界情况。

  1. import java.util.HashSet;
  2. import java.util.Set;
  4. class Solution {
  5.     Set<Integer> ans;
  7.     public int flipLights(int n, int m) {
  8.         // 其他灯泡的状态都可以通过前4个灯泡的状态导出
  9.         n = Math.min(4, n);
  10.         // 有效操作最多4次, 每种1次
  11.         m = Math.min(4, m);
  12.         switch (n) {
  13.             case 0:
  14.                 return 0;
  15.             case 1:
  16.                 if (m == 0) {
  17.                     return 1;
  18.                 } else {
  19.                     return 2;
  20.                 }
  22.             case 2:
  23.                 if (m == 0) {
  24.                     return 1;
  25.                 } else if(m==1){
  26.                     return 3;
  27.                 }else {
  28.                     return 4;
  29.                 }
  30.             case 3:
  31.                 switch (m) {
  32.                     case 0:
  33.                         return 1;
  34.                     case 1:
  35.                         return 4;
  36.                     case 2:
  37.                         return 7;
  38.                     default:
  39.                         return 8;
  40.                 }
  41.         }
  42.         ans = new HashSet<>();
  43.         bfs(m, 0b0000);
  44.         return ans.size();
  45.     }
  47.     private void bfs(int m, int status) {
  48.         if (m == 0) {
  49.             ans.add(status);
  50.             return;
  51.         }
  52.         bfs(m - 1, 0b1111 ^ status);
  53.         bfs(m - 1, 0b0101 ^ status);
  54.         bfs(m - 1, 0b1010 ^ status);
  55.         bfs(m - 1, 0b1001 ^ status);
  56.     }
  57. }