Screenshot from 2016-01-24 16:19:16.png
My code:
import java.util.HashSet;
public class Solution {
public void gameOfLife(int[][] board) {
if (board == null || board.length == 0 || board[0].length == 0)
return;
boolean[][] next = new boolean[board.length][board[0].length]; // false means dead and true means live
/** traverse board to ensure whether life should be deal or live */
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
simulate(i, j, board, next);
}
}
/** update states for board depending on the nex[][] */
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (next[i][j])
board[i][j] = 1;
else
board[i][j] = 0;
}
}
}
/** simulate the next generation */
private void simulate(int i, int j, int[][] board, boolean[][] next) {
int liveNum = getLiveNumbers(i, j, board);
if (board[i][j] == 1) { // if alive
if (liveNum < 2 || liveNum > 3)
next[i][j] = false;
else
next[i][j] = true;
}
else { // if dead
if (liveNum == 3)
next[i][j] = true;
}
}
/** get the number of live animals around */
private int getLiveNumbers(int i, int j, int[][] board) {
int liveNum = 0;
/** left side */
if (j - 1 >= 0) {
if (i - 1 >= 0) { // up
if (board[i - 1][j - 1] == 1)
liveNum++;
}
if (board[i][j - 1] == 1)
liveNum++;
if (i + 1 < board.length) { // down
if (board[i + 1][j - 1] == 1)
liveNum++;
}
}
/** middle side */
if (i - 1 >= 0) { // up
if (board[i - 1][j] == 1)
liveNum++;
}
if (i + 1 < board.length) { // down
if (board[i + 1][j] == 1)
liveNum++;
}
/** right side */
if (j + 1 < board[0].length) {
if (i - 1 >= 0) { // up
if (board[i - 1][j + 1] == 1)
liveNum++;
}
if (board[i][j + 1] == 1)
liveNum++;
if (i + 1 < board.length) { // down
if (board[i + 1][j + 1] == 1)
liveNum++;
}
}
return liveNum;
}
public static void main(String[] args) {
Solution test = new Solution();
int[][] board = new int[1][2];
board[0][0] = 1;
board[0][1] = 1;
test.gameOfLife(board);
}
}
终于他妈过了测试。
这道题目和CS61B其中一次大作业很像。但是，这道题目简化了一些。
比如，(0, 0) 的邻居，就没有8个了。但是其实可以跳转到另外一端的。所以一开始我写的是一个更复杂的版本。在这个版本下，可以实现所谓的，无限大区域。因为他是球形的，无边界的。然后通过HashSet避免重复统计。
That Code:
import java.util.HashSet;
public class Solution {
public void gameOfLife(int[][] board) {
if (board == null || board.length == 0 || board[0].length == 0)
return;
boolean[][] next = new boolean[board.length][board[0].length]; // false means dead and true means live
/** traverse board to ensure whether life should be deal or live */
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
simulate(i, j, board, next);
}
}
/** update states for board depending on the nex[][] */
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (next[i][j])
board[i][j] = 1;
else
board[i][j] = 0;
}
}
}
/** simulate the next generation */
private void simulate(int i, int j, int[][] board, boolean[][] next) {
int liveNum = getLiveNumbers(i, j, board);
if (board[i][j] == 1) { // if alive
if (liveNum < 2 || liveNum > 3)
next[i][j] = false;
else
next[i][j] = true;
}
else { // if dead
if (liveNum == 3)
next[i][j] = true;
}
}
/** get the number of live animals around */
private int getLiveNumbers(int i, int j, int[][] board) {
int liveNum = 0;
HashSet<Integer> tracker = new HashSet<Integer>();
/** left */
int colLeft = (j - 1 >= 0) ? (j - 1) : (board[0].length - 1);
int colRight = (j + 1 <= board[0].length - 1) ? (j + 1) : (0);
int rowUp = (i - 1 >= 0) ? (i - 1) : (board.length - 1);
int rowDown = (i + 1 <= board.length - 1) ? (i + 1) : (0);
tracker.add(i * board[0].length + j); // add itself to avoid repeating
/** update left side */
if (!tracker.contains(rowUp * board[0].length + colLeft) && board[rowUp][colLeft] == 1) {
liveNum++;
tracker.add(rowUp * board[0].length + colLeft);
}
if (!tracker.contains(i * board[0].length + colLeft) && board[i][colLeft] == 1) {
liveNum++;
tracker.add(i * board[0].length + colLeft);
}
if (!tracker.contains(rowDown * board[0].length + colLeft) && board[rowDown][colLeft] == 1) {
liveNum++;
tracker.add(rowDown * board[0].length + colLeft);
}
/** update middle side */
if (!tracker.contains(rowUp * board[0].length + j) && board[rowUp][j] == 1) {
liveNum++;
tracker.add(rowUp * board[0].length + j);
}
if (!tracker.contains(rowDown * board[0].length + j) && board[rowDown][j] == 1) {
liveNum++;
tracker.add(rowDown * board[0].length + j);
}
/** update right side */
if (!tracker.contains(rowUp * board[0].length + colRight) && board[rowUp][colRight] == 1) {
liveNum++;
tracker.add(rowUp * board[0].length + colRight);
}
if (!tracker.contains(i * board[0].length + colRight) && board[i][colRight] == 1) {
liveNum++;
tracker.add(i * board[0].length + colRight);
}
if (!tracker.contains(rowDown * board[0].length + colRight) && board[rowDown][colRight] == 1) {
liveNum++;
tracker.add(rowDown * board[0].length + colRight);
}
return liveNum;
}
public static void main(String[] args) {
Solution test = new Solution();
int[][] board = new int[1][2];
board[0][0] = 1;
board[0][1] = 1;
test.gameOfLife(board);
}
}
这道题木没什么难的，就是有些烦，题目表述也不是很明确。
Anyway, Good luck, Richardo!
My code:
public class Solution {
private int[][] directions = new int[][]{{1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};
public void gameOfLife(int[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
board[i][j] *= 10;
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
simulate(board, i, j);
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
board[i][j] %= 10;
}
}
}
private void simulate(int[][] board, int i, int j) {
int live = 0;
int dead = 0;
for (int row = 0; row < directions.length; row++) {
int tempI = i + directions[row][0];
int tempJ = j + directions[row][1];
if (tempI >= 0 && tempI < board.length && tempJ >= 0 && tempJ < board[0].length) {
if (board[tempI][tempJ] / 10 == 1) {
live++;
}
else {
dead++;
}
}
}
if (board[i][j] / 10 == 1) {
if (live < 2) {
board[i][j] += 0;
}
else if (live < 4) {
board[i][j] += 1;
}
else {
board[i][j] += 0;
}
}
else {
if (live == 3) {
board[i][j] += 1;
}
else {
board[i][j] += 0;
}
}
}
}
这道题目之前一直在想如何in place
同学提醒，可以用int表示更多的信息。
一开始，所有board[i][j] * 10
所以，原状态全部保存在十位，
最新状态全部保存在个位。
然后就没问题了。
这次八个方向采用了 8*2的array
方便多了。。
Anyway, Good luck, Richardo! -- 09/05/2016
