Ich arbeite an folgendem Problem von Leetcode:Game of Life Programm
ein Brett mit m von n-Zellen gegeben, jede Zelle einen Anfangszustand Live (1) oder tot (0). Jede Zelle interagiert mit seinen acht Nachbarn (horizontal, vertikal, diagonal) mit den folgenden vier Regeln ( aus dem obigen Wikipedia-Artikel entnommen):
Alle lebenden Zellen mit weniger als zwei Live-Nachbarn sterben, als ob verursacht durch Unterbevölkerung. Jede lebende Zelle mit zwei oder drei lebenden Nachbarn lebt auf der nächsten Generation. Jede lebende Zelle mit mehr als drei lebenden Nachbarn stirbt, als ob durch Überbevölkerung. Jede tote Zelle mit genau drei lebenden Nachbarn wird eine lebende Zelle, als ob durch Fortpflanzung. Schreibe eine Funktion, um den nächsten Zustand (nach einem Update) der Karte aufgrund ihres aktuellen Status zu berechnen.
Follow-up: Können Sie es an Ort und Stelle lösen? Denken Sie daran, dass die Karte gleichzeitig aktualisiert werden muss: Sie können einige Zellen nicht zuerst aktualisieren und dann ihre aktualisierten Werte verwenden, um andere Zellen zu aktualisieren.
Meine Lösung ist der Lösung nachempfunden, die von einem anderen Benutzer auf der Website angeboten wird, und fügt daher ihre Lösungsbeschreibung hinzu.
Zu Beginn ist jede Zelle entweder 00 oder 01. Beachten Sie, dass der erste Zustand unabhängig vom zweiten Zustand ist. Stellen Sie sich vor, alle Zellen ändern sofort vom 1. in den 2. Zustand, zur gleichen Zeit. Lassen Sie uns # von Nachbarn vom 1. Staat zählen und 2. Zustandsbit setzen. Da jeder 2.Status standardmäßig tot ist, muss der Übergang 01 -> 00 nicht in Betracht gezogen werden. Im Ende den 1. Zustand jeder Zelle löschen, indem man >> 1. für das erste Bit der Zelledie 8 Pixel um sich selbst prüft, und setze das 2. Bit der Zelle.
Transition 01 -> 11: 1, wenn Brett == und lebt> = 2 & & Leben < = 3. Transition 00 -> 10: wenn Brett == 0 und lebt == 3.
Mein Code versagt und ich bin mir nicht sicher warum. Hier ist die Ausgabe vs erwartet:
Input:
[[0,0,0,0,0],[0,0,1,0,0],[0,0,1,0,0],[0,0,1,0,0],[0,0,0,0,0]]
Output:
[[0,0,0,0,0],[0,0,0,0,0],[0,1,1,1,0],[0,1,0,1,0],[0,0,1,1,0]]
Expected:
[[0,0,0,0,0],[0,0,0,0,0],[0,1,1,1,0],[0,0,0,0,0],[0,0,0,0,0]]
Es scheint, wie später Zeilen aktualisiert werden, basierend auf früheren Updates in früheren Zeilen, aber ich glaube, ich für diese entfielen .. Wer weiß, was das Problem ist?Meine Lösung unter:
# @param {Integer[][]} board
# @return {Void} Do not return anything, modify board in-place instead.
def game_of_life(board)
#error conditions
return nil if (board.nil? || board.length == 0) #empty or nil arr
row = 0
col = 0
m = board.length
n = board[0].length
until row == m
col = 0
until col == n
live_count = adj_live_counter(board, row, col) #leaving out two conditions because by default second bit is 0
if alive?(board, row, col) && live_count == 2 || live_count == 3
board[row][col] = 3
elsif dead?(board, row, col) && live_count == 3
board[row][col] = 2
end
col+=1
end
row+=1
end
p board
#when the above is done, grab second bit for every cell.
#board = clear_first_bit(board)
clear_first_bit(board)
p board
end
private
def adj_live_counter(board, row, col)
m = board.length
n = board[0].length
count = 0
r = [row - 1, 0].max #start: either 0 or the above element
until r > [row + 1, m - 1].min #end: below element or end of arr
c = [col - 1, 0].max #start: at left element or 0
until c > [col + 1, n - 1].min #end: at right element or end of arr
count += board[r][c] & 1
#p count
c += 1
end
r += 1
end
count -= board[row][col] & 1
count
end
def clear_first_bit(board)
m = board.length
n = board[0].length
row = 0
col = 0
until row == m
col = 0
until col == n
board[row][col] >>= 1
col += 1
end
row += 1
end
end
def alive?(board, row, count)
board[row][count] & 1 == 1
end
def dead?(board, row, count)
board[row][count] & 1 == 0
end
Lösung von Website angeboten werden (in Java):
public void gameOfLife(int[][] board) {
if (board == null || board.length == 0) return;
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int lives = liveNeighbors(board, m, n, i, j);
// In the beginning, every 2nd bit is 0;
// So we only need to care about when will the 2nd bit become 1.
if (board[i][j] == 1 && lives >= 2 && lives <= 3) {
board[i][j] = 3; // Make the 2nd bit 1: 01 ---> 11
}
if (board[i][j] == 0 && lives == 3) {
board[i][j] = 2; // Make the 2nd bit 1: 00 ---> 10
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] >>= 1; // Get the 2nd state.
}
}
}
public int liveNeighbors(int[][] board, int m, int n, int i, int j) {
int lives = 0;
for (int x = Math.max(i - 1, 0); x <= Math.min(i + 1, m - 1); x++) {
for (int y = Math.max(j - 1, 0); y <= Math.min(j + 1, n - 1); y++) {
lives += board[x][y] & 1;
}
}
lives -= board[i][j] & 1;
return lives;
}