957. Prison Cells After N Days
leetcode medium
Task
Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста.
Каждый день статус камеры, занята она или пуста, меняется по следующим правилам:
Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой.
В противном случае, она становится пустой.
Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей.
Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n.
Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше).
Пример:
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]
C# solution
matched/originalpublic class Solution {
protected int CellsToBitmap(int[] cells) {
int stateBitmap = 0;
foreach (int cell in cells) {
stateBitmap = (stateBitmap << 1) | cell;
}
return stateBitmap;
}
protected int[] NextDay(int[] cells) {
int[] newCells = new int[cells.Length];
for (int i = 1; i < cells.Length - 1; ++i) {
newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
}
return newCells;
}
public int[] PrisonAfterNDays(int[] cells, int N) {
Dictionary<int, int> seen = new Dictionary<int, int>();
bool isFastForwarded = false;
while (N > 0) {
if (!isFastForwarded) {
int stateBitmap = CellsToBitmap(cells);
if (seen.ContainsKey(stateBitmap)) {
N %= seen[stateBitmap] - N;
isFastForwarded = true;
} else {
seen[stateBitmap] = N;
}
}
if (N > 0) {
N--;
cells = NextDay(cells);
}
}
return cells;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
protected int CellsToBitmap(vector<int>& cells) {
int stateBitmap = 0;
foreach (int cell in cells) {
stateBitmap = (stateBitmap << 1) | cell;
}
return stateBitmap;
}
protected vector<int>& NextDay(vector<int>& cells) {
vector<int>& newCells = new int[cells.size()];
for (int i = 1; i < cells.size() - 1; ++i) {
newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
}
return newCells;
}
public vector<int>& PrisonAfterNDays(vector<int>& cells, int N) {
unordered_map<int, int> seen = new unordered_map<int, int>();
bool isFastForwarded = false;
while (N > 0) {
if (!isFastForwarded) {
int stateBitmap = CellsToBitmap(cells);
if (seen.count(stateBitmap)) {
N %= seen[stateBitmap] - N;
isFastForwarded = true;
} else {
seen[stateBitmap] = N;
}
}
if (N > 0) {
N--;
cells = NextDay(cells);
}
}
return cells;
}
}Java solution
auto-draft, review before submitimport java.util.*;
import java.math.*;
// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
protected int CellsToBitmap(int[] cells) {
int stateBitmap = 0;
foreach (int cell in cells) {
stateBitmap = (stateBitmap << 1) | cell;
}
return stateBitmap;
}
protected int[] NextDay(int[] cells) {
int[] newCells = new int[cells.length];
for (int i = 1; i < cells.length - 1; ++i) {
newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
}
return newCells;
}
public int[] PrisonAfterNDays(int[] cells, int N) {
HashMap<int, int> seen = new HashMap<int, int>();
boolean isFastForwarded = false;
while (N > 0) {
if (!isFastForwarded) {
int stateBitmap = CellsToBitmap(cells);
if (seen.containsKey(stateBitmap)) {
N %= seen[stateBitmap] - N;
isFastForwarded = true;
} else {
seen[stateBitmap] = N;
}
}
if (N > 0) {
N--;
cells = NextDay(cells);
}
}
return cells;
}
}Python solution
matched/originalclass Solution:
def cellsToBitmap(self, cells):
stateBitmap = 0
for cell in cells:
stateBitmap = (stateBitmap << 1) | cell
return stateBitmap
def nextDay(self, cells):
newCells = [0] * len(cells)
for i in range(1, len(cells) - 1):
newCells[i] = 1 if cells[i - 1] == cells[i + 1] else 0
return newCells
def prisonAfterNDays(self, cells, N):
seen = {}
isFastForwarded = False
while N > 0:
if not isFastForwarded:
stateBitmap = self.cellsToBitmap(cells)
if stateBitmap in seen:
N %= seen[stateBitmap] - N
isFastForwarded = True
else:
seen[stateBitmap] = N
if N > 0:
N -= 1
cells = self.nextDay(cells)
return cellsGo solution
matched/originalfunc cellsToBitmap(cells []int) int {
stateBitmap := 0
for _, cell := range cells {
stateBitmap = (stateBitmap << 1) | cell
}
return stateBitmap
}
func nextDay(cells []int) []int {
newCells := make([]int, len(cells))
for i := 1; i < len(cells)-1; i++ {
newCells[i] = 0
if cells[i-1] == cells[i+1] {
newCells[i] = 1
}
}
return newCells
}
func prisonAfterNDays(cells []int, N int) []int {
seen := make(map[int]int)
isFastForwarded := false
for N > 0 {
if !isFastForwarded {
stateBitmap := cellsToBitmap(cells)
if _, ok := seen[stateBitmap]; ok {
N %= seen[stateBitmap] - N
isFastForwarded = true
} else {
seen[stateBitmap] = N
}
}
if N > 0 {
N--
cells = nextDay(cells)
}
}
return cells
}Explanation
Algorithm
Преобразуйте текущее состояние камер в целое число с помощью битовой маски. Это позволит удобно отслеживать повторяющиеся состояния.
Симулируйте изменение состояния камер день за днем, записывая каждое состояние в хэш-таблицу. Если обнаруживается повторяющееся состояние, вычислите длину цикла и уменьшите количество оставшихся дней с учетом этого цикла.
Продолжайте симуляцию, пока не достигнете заданного числа дней, либо используйте цикл для ускорения процесса.
😎