Prison Cells After N Days

tags: Medium、Hash_table

https://leetcode.com/problems/prison-cells-after-n-days/

本题的标签是 Hash Table，说明了数组的状态可能是会有重复的，就是说可能是有一个周期循环的，这样就完全没有必要每次都算一遍。正确的做法的应该是建立状态和当前N值的映射，一旦当前计算出的状态在 HashMap 中出现了，说明周期找到了，这样就可以通过取余来快速的缩小N值。为了使用 HashMap 而不是 TreeMap，这里首先将数组变为字符串，然后开始循环N，将当前状态映射为 N-1，然后新建了一个长度为8，且都是0的字符串。更新的时候不用考虑首尾两个位置，因为前面说了，首尾两个位置一定会变为0。更新完成了后，便在 HashMap 查找这个状态是否出现过，是的话算出周期，然后N对周期取余。最后再把状态字符串转为数组即可

• 我的寫法

class Solution
{
public:
  vector<int> prisonAfterNDays(vector<int> &cells, int n)
  {
    int sz = cells.size(), cycleLength = 0;
    unordered_set<string> seen;
    bool hasCycle = false;
    for (int i = 0; i < n; ++i)
    {
      auto nextCells = getNext(cells, sz);
      auto s = vec2string(nextCells);
      if (seen.find(s) == seen.end())
      {
        seen.insert(s);
        ++cycleLength;
      }
      else
      {
        hasCycle = true;
        break;
      }
      cells = nextCells;
    }
    if (hasCycle)
    {
      for (int i = 0; i < n % cycleLength; ++i)
      {
        cells = getNext(cells, sz);
      }
    }
    return cells;
  }

private:
  vector<int> getNext(vector<int> &cells, int sz)
  {
    vector<int> nextCells(sz, 0);
    for (int i = 1; i < sz - 1; ++i)
    {
      nextCells[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
    }
    return nextCells;
  }
  string vec2string(vector<int> cells)
  {
    string output;
    for (auto &cell : cells)
    {
      output += to_string(cell);
    }
    return output;
  }
};

• 大神寫法