游戏专题 2016-08-09

[wolfogre]

292 Nim Game

289 Game of Life

[wolfogre]

// AC 292 Nim Game
public class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

[dayang]

/**
 * [AC] LeetCode 292 Nim Game
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function(n) {
    return n % 4 !== 0;
};

[SnackMen]

/*
*[AC] LeetCode 292 Nim Game
*/
public class Solution {
    public boolean canWinNim(int n) {
        return n%4!=0;
    }
}

[wolfogre]

// [AC] 289 Game of Life
public class Solution {
    class Point{
        public int v, row, col;
        public Point(int v, int row, int col){
            this.v = v;
            this.row = row;
            this.col = col;
        }
    }

    public void gameOfLife(int[][] board) {
        ArrayList<Point> changes = new ArrayList<>();
        for(int i = 0; i < board.length; ++i)
            for(int j = 0; j < board[0].length; ++j){
                int lives = getLiveCount(i, j, board);

                if(board[i][j] == 1){
                    if(lives < 2)
                        changes.add(new Point(0, i, j));
                    else
                        if(lives > 3)
                           changes.add(new Point(0, i, j)); 

                } else 
                    if(lives == 3)
                       changes.add(new Point(1, i, j));  
            }
        for(Point p : changes)
            board[p.row][p.col] = p.v;
    }

    private int getLiveCount(int row, int col, int[][] board){
        return ((row > 0) ? board[row - 1][col] : 0)
                    + ((row > 0 && col > 0) ? board[row - 1][col - 1] : 0)
                    + ((row > 0 && col < board[0].length - 1) ? board[row - 1][col + 1] : 0)
                    + ((col > 0) ? board[row][col - 1] : 0)
                    + ((col < board[0].length - 1) ? board[row][col + 1] : 0)
                    + ((row < board.length - 1 && col > 0) ? board[row + 1][col - 1] : 0)
                    + ((row < board.length - 1 && col < board[0].length - 1) ? board[row + 1][col + 1] : 0)
                    + ((row < board.length - 1) ? board[row + 1][col] : 0);
    }
}

[dayang]

/**
 * [AC] LeetCode 289 Game of Life
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function(board) {
    var temp = [], m = board.length, n = board[0].length;
    var i,j,k,x,y,num;
    var dir = [[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1]];
    for(i = 0; i < m; i++){
        temp.push([]);
        for(j = 0; j < n; j++){
            temp[i].push(board[i][j]);
        }
    }

    for(i = 0; i < m; i++){
        for(j = 0; j < n; j++){
            num = 0;
            for(k = 0; k < 8; k++){
                x = i + dir[k][0];
                y = j + dir[k][1];
                if(x < 0 || x >= m || y <0 || y >= n)
                    continue;
                if(temp[x][y] === 1){
                    num ++;
                }
            }
            if(num < 2){
                board[i][j] = 0;
            }else if(num === 3){
                board[i][j] = 1;
            }else if(num > 3){
                board[i][j] = 0;
            }
        }
    }
};

[zhaokuohaha]

292 - C# - 保证每次拿完剩下的石头都是4的倍数

public class Solution {
    public bool CanWinNim(int n) {
        return n%4 != 0;
    }
}

提速

public class Solution {
    public bool CanWinNim(int n) {
        return (n & 3) != 0;
    }
}

[SnackMen]

/*
*[AC] LeetCode 289 Game of Life
*/
public class Solution {
    public void gameOfLife(int[][] board) {
        int rowLength = board.length;
        int cellLength = board[0].length;
        for(int i=0;i<rowLength;i++){
            for(int j=0;j<cellLength;j++){
                int live=0;
                if(i>0){
                    live+=board[i-1][j]==1 || board[i-1][j]==2 ? 1:0;
                }
                if(i<rowLength-1){
                    live+=board[i+1][j]==1 || boadr[i+1][j]==2 ? 1:0;
                }
                if(j>0){
                    live+=board[i][j-1]==1 || board[i][j-1]==2 ? 1:0;
                }
                if(j<cellLength-1){
                    live+=board[i][j+1]==1 || board[i][j+1]==2 ? 1:0;
                }
                if(i>0 && j>0){
                    live+=board[i-1][j-1]==1 || board[i-1][j-1]==2 ? 1:0;
                }
                if(i<rowLength-1 && j<cellLength-1){
                    live+=board[i+1][j+1]==1 || board[i+1][j+1]==2 ? 1:0;
                }
                if(i>0 && j<cellLength-1){
                    live+=board[i-1][j+1]==1 || board[i-1][j+1]==2 ? 1:0;
                }
                if(i<rowLength-1 && j>0){
                    live+=board[i+1][j-1]==1 || board[i+1][j-1]==2 ? 1:0;
                }

                if(board[i][j]==0 && live==3){
                    board[i][j]=3;
                }else if(board[i][j]==1 && (live<2 || live>3)){
                    board[i][j]=2;
                }
            }
        }
        for(int i=0;i<rowLength;i++){
            for(int j=0;j<cellLength;j++){
                board[i][j]=board[i][j]%2;
            }
        }
    }
}

[zhaokuohaha]

289 - C# - 遍历标记该点是否需要更改

感觉直接标记更新后的状态(无论是否更改) 代码写起来简单一些

public class Solution {
    public void GameOfLife(int[,] board) {
        int height = board.GetLength(0);
        int width = board.GetLength(1);
        bool[,] che= new bool[height,width];
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(Change(board,i,j,width,height)){
                   che[i,j] = true; 
                }
            }
        }
        for(int i=0; i<board.GetLength(0); i++){
            for(int j=0; j<board.GetLength(1); j++){
                if(che[i,j]){
                   board[i,j] = 1 - board[i,j];
                }
            }
        }
    }

    private bool IsIn(int x, int y, int height, int width){
        return x>=0 && x < height && y >= 0 && y < width;
    }

    private bool Change(int[,] board, int i, int j,int width, int height){
        int count = 0;
        for(int x = -1; x <=1; x++){
            for(int y=-1; y<=1; y++){
                if(!(x==0&&y==0) && IsIn(i+x,y+j,height,width) && board[i+x,j+y]==1)
                {
                    count ++;
                }
            }
        }
        if((board[i,j] == 1 && (count < 2 || count > 3)) || (board[i,j] == 0 && count == 3)){
            return true;
        }
        return false;
    }
}