LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 按两次同一个按钮，效果与不按等价，如果已按 4 次按钮，第 5 次必然按下的是前 4 次按过的按钮之一，相当于按 3 次按钮，由此可知，只需要遍历出按 1 到 4 次按钮的所有可能情况即可。而按 4 次按钮时，如果每个按钮都按了一次，按 1 号按钮与 23 按钮的功能等价，相当于只按了 4 号按钮，因此最后只需要遍历按 1 到 3 次按钮的所有可能情况
• 每次按下按钮，每 6 个灯泡的状态必然相同，因此只需要检查前 6 个灯泡即可。而前 6 个灯泡中，可以分前 3 个灯泡和后 3 个灯泡考虑。按 1 或 4 号按钮对前 3 个灯泡和后 3 个灯泡的影响相同。按 2 号按钮时，会改变前 3 个灯泡的中间灯泡状态，改变后 3 个灯泡的两侧灯泡状态，此时后 3 个灯泡的状态即与前 3 个灯泡互补。3 号按钮同理，因此前 3 个灯泡的状态即可确定后 3 个灯泡状态，因此只需要检查前 3 个灯泡状态即可

class Solution {
 public:
  int flipLights(int n, int m) {
    bitset<3> b;
    unordered_set<bitset<3>> s;
    dfs(b, s, min(m, 3), min(n, 3));
    return size(s);
  }

  void dfs(bitset<3>& b, unordered_set<bitset<3>>& s, int m, int n) {
    if (!m) {
      s.emplace(b);
      return;
    }
    bitset<3> t = b;
    flip_all(b, n);
    dfs(b, s, m - 1, n);
    flip_even(b, n);
    dfs(b, s, m - 1, n);
    flip_odd(b, n);
    dfs(b, s, m - 1, n);
    flip_3k_append_1(b, n);
    dfs(b, s, m - 1, n);
    b = t;
  }

  void flip_all(bitset<3>& b, int n) {
    for (int i = 0; i < n; ++i) {
      b.flip();
    }
  }

  void flip_even(bitset<3>& b, int n) {
    for (int i = 1; i < n; i += 2) {
      b.flip(i);
    }
  }

  void flip_odd(bitset<3>& b, int n) {
    for (int i = 0; i < n; i += 2) {
      b.flip(i);
    }
  }

  void flip_3k_append_1(bitset<3>& b, int n) {
    for (int i = 0; i < n; i += 3) {
      b.flip(i);
    }
  }
};

• 由于搜索范围不大，也可以手算所有结果硬编码

class Solution {
 public:
  int flipLights(int n, int m) {
    if (!n || !m) {
      return 1;
    }
    if (n == 1) {
      return 2;
    }
    if (n == 2) {
      if (m == 1) {
        return 3;
      }
      return 4;
    }
    if (m == 1) {
      return 4;
    }
    if (m == 2) {
      return 7;
    }
    return 8;
  }
};