Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/957.html
957. Prison Cells After N Days (Medium)
There are 8 prison cells in a row, and each cell is either occupied or vacant.
Each day, whether the cell is occupied or vacant changes according to the following rules:
- If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
- Otherwise, it becomes vacant.
(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)
We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.
Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)
Example 1:
Input: cells = [0,1,0,1,1,0,0,1], N = 7 Output: [0,0,1,1,0,0,0,0] Explanation: The following table summarizes the state of the prison on each day: Day 0: [0, 1, 0, 1, 1, 0, 0, 1] Day 1: [0, 1, 1, 0, 0, 0, 0, 0] Day 2: [0, 0, 0, 0, 1, 1, 1, 0] Day 3: [0, 1, 1, 0, 0, 1, 0, 0] Day 4: [0, 0, 0, 0, 0, 1, 0, 0] Day 5: [0, 1, 1, 1, 0, 1, 0, 0] Day 6: [0, 0, 1, 0, 1, 1, 0, 0] Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
Example 2:
Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000 Output: [0,0,1,1,1,1,1,0]
Note:
cells.length == 8cells[i]is in{0, 1}1 <= N <= 10^9
Companies: Amazon
Related Topics: Hash Table
Solution 1.
Simulate the process. Once find a cycle, we can get the result from within the cycle.
Since there are at most 256 states, we will get the result at at most 256th day. So the time and space complexity is O(1).
// OJ: https://leetcode.com/problems/prison-cells-after-n-days/
// Time: O(1)
// Space: O(1)
class Solution {
char next(char c) {
char ans = 0;
for (int i = 1; i < 7; ++i)
ans |= ((c >> (i - 1) & 1) == (c >> (i + 1) & 1)) << i;
return ans;
}
public:
vector<int> prisonAfterNDays(vector<int>& A, int N) {
char c = 0;
for (int i = 0; i < 8; ++i) c |= A[i] << i;
vector<char> v{c};
unordered_map<char, int> m{ {c, 0} };
for (int i = 1; i <= N; ++i) {
c = next(c);
if (m.count(c)) {
int d = i - m[c];
c = v[(N - i) % d + m[c]];
break;
}
v.push_back(c);
m[c] = i;
}
vector<int> ans(8);
for (int i = 0; i < 8; ++i) ans[i] = (c >> i) & 1;
return ans;
}
};
Or
// OJ: https://leetcode.com/problems/prison-cells-after-n-days/
// Time: O(1)
// Space: O(1)
class Solution {
char next(char c) {
char ans = 0;
for (int i = 0; i < 8; ++i)
ans |= (i > 0 && i < 7 && ((c >> (i - 1)) & 1) == ((c >> (i + 1)) & 1)) << i;
return ans;
}
public:
vector<int> prisonAfterNDays(vector<int>& A, int N) {
char c = 0;
for (int i = 0; i < 8; ++i) c |= A[i] << i;
unordered_map<char, int> m{ {c, 0} };
for (int i = 1; i <= N; ++i) {
c = next(c);
if (m.count(c)) {
int d = i - m[c];
N = (N - i) % d;
while (N--) c = next(c);
break;
}
m[c] = i;
}
vector<int> ans(8);
for (int i = 0; i < 8; ++i) ans[i] = (c >> i) & 1;
return ans;
}
};
-
class Solution { public int[] prisonAfterNDays(int[] cells, int N) { Map<String, Integer> stateDayMap = new HashMap<String, Integer>(); Map<Integer, int[]> dayStateMap = new HashMap<Integer, int[]>(); int[] prevCells = new int[8]; System.arraycopy(cells, 0, prevCells, 0, 8); int days = 0; int cycle = 0; while (days < N) { days++; int[] change = new int[8]; change[0] = 0; change[7] = 0; for (int i = 1; i < 7; i++) { if (prevCells[i - 1] == prevCells[i + 1]) change[i] = 1; } for (int i = 0; i < 8; i++) prevCells[i] = change[i]; String arrayStr = Arrays.toString(change); if (stateDayMap.containsKey(arrayStr)) { int prevDay = stateDayMap.get(arrayStr); cycle = days - prevDay; break; } else { stateDayMap.put(arrayStr, days); dayStateMap.put(days, change); } } if (days == N) return prevCells; int remainder = N % cycle; if (remainder == 0) remainder = cycle; return dayStateMap.get(remainder); } } -
// OJ: https://leetcode.com/problems/prison-cells-after-n-days/ // Time: O(1) // Space: O(1) class Solution { char next(char c) { char ans = 0; for (int i = 1; i < 7; ++i) ans |= ((c >> (i - 1) & 1) == (c >> (i + 1) & 1)) << i; return ans; } public: vector<int> prisonAfterNDays(vector<int>& A, int N) { char c = 0; for (int i = 0; i < 8; ++i) c |= A[i] << i; vector<char> v{c}; unordered_map<char, int> m{ {c, 0} }; for (int i = 1; i <= N; ++i) { c = next(c); if (m.count(c)) { int d = i - m[c]; c = v[(N - i) % d + m[c]]; break; } v.push_back(c); m[c] = i; } vector<int> ans(8); for (int i = 0; i < 8; ++i) ans[i] = (c >> i) & 1; return ans; } }; -
class Solution(object): def prisonAfterNDays(self, oldcells, N): """ :type cells: List[int] :type N: int :rtype: List[int] """ cells = copy.deepcopy(oldcells) count = 0 N %= 14 if N == 0: N = 14 while count < N: newCell = [0] * 8 for i in range(1, 7): if cells[i - 1] == cells[i + 1]: newCell[i] = 1 else: newCell[i] = 0 cells = newCell count += 1 return cells