|
2 | 2 |
|
3 | 3 | publicclass_289 { |
4 | 4 | publicstaticclassSolution1 { |
| 5 | +/** |
| 6 | + * Time: O(m*n) |
| 7 | + * Space: O(m*n) |
| 8 | + */ |
5 | 9 | publicvoidgameOfLife(int[][]board) { |
6 | 10 | intheight =board.length; |
7 | 11 | intwidth =board[0].length; |
@@ -40,4 +44,73 @@ public void gameOfLife(int[][] board) { |
40 | 44 | } |
41 | 45 | } |
42 | 46 | } |
| 47 | + |
| 48 | +publicstaticclassSolution2 { |
| 49 | +/** |
| 50 | + * Time: O(m*n) |
| 51 | + * Space: O(1) |
| 52 | + * <p> |
| 53 | + * we use different numbers to represent its previous state so that we can change in place without losing track of its previous state |
| 54 | + * we define: |
| 55 | + * live to dead is 1 -> -1 |
| 56 | + * dead to live is 0 -> 2 |
| 57 | + * live to live is 1 -> 1 |
| 58 | + * <p> |
| 59 | + * Credit: Solution 2 from https://leetcode.com/problems/game-of-life/solution/ |
| 60 | + */ |
| 61 | +publicvoidgameOfLife(int[][]board) { |
| 62 | +// Neighbors array to find 8 neighboring cells for a given cell |
| 63 | +int[]neighbors = {0,1, -1}; |
| 64 | + |
| 65 | +introws =board.length; |
| 66 | +intcols =board[0].length; |
| 67 | + |
| 68 | +// Iterate through board cell by cell. |
| 69 | +for (introw =0;row <rows;row++) { |
| 70 | +for (intcol =0;col <cols;col++) { |
| 71 | + |
| 72 | +// For each cell count the number of live neighbors. |
| 73 | +intliveNeighbors =0; |
| 74 | + |
| 75 | +for (inti =0;i <3;i++) { |
| 76 | +for (intj =0;j <3;j++) { |
| 77 | + |
| 78 | +if (!(neighbors[i] ==0 &&neighbors[j] ==0)) { |
| 79 | +intr = (row +neighbors[i]); |
| 80 | +intc = (col +neighbors[j]); |
| 81 | + |
| 82 | +// Check the validity of the neighboring cell. |
| 83 | +// and whether it was originally a live cell. |
| 84 | +if ((r <rows &&r >=0) && (c <cols &&c >=0) && (Math.abs(board[r][c]) ==1)) { |
| 85 | +liveNeighbors +=1; |
| 86 | + } |
| 87 | + } |
| 88 | + } |
| 89 | + } |
| 90 | + |
| 91 | +// Rule 1 or Rule 3 |
| 92 | +if ((board[row][col] ==1) && (liveNeighbors <2 ||liveNeighbors >3)) { |
| 93 | +// -1 signifies the cell is now dead but originally was live. |
| 94 | +board[row][col] = -1; |
| 95 | + } |
| 96 | +// Rule 4 |
| 97 | +if (board[row][col] ==0 &&liveNeighbors ==3) { |
| 98 | +// 2 signifies the cell is now live but was originally dead. |
| 99 | +board[row][col] =2; |
| 100 | + } |
| 101 | + } |
| 102 | + } |
| 103 | + |
| 104 | +// Get the final representation for the newly updated board. |
| 105 | +for (introw =0;row <rows;row++) { |
| 106 | +for (intcol =0;col <cols;col++) { |
| 107 | +if (board[row][col] >0) { |
| 108 | +board[row][col] =1; |
| 109 | + }else { |
| 110 | +board[row][col] =0; |
| 111 | + } |
| 112 | + } |
| 113 | + } |
| 114 | + } |
| 115 | + } |
43 | 116 | } |