本文属“一天一道编程题”系列博客开头，作为每天一次的打卡式练习，日积月累，目的在于锻炼自己的编程能力，希望大家监督~

题目描述

根据*文章：“生命游戏，也可简单称为生命，是由英国数学家John Horton Conway于1970年发明的细胞自动机。”
给定一块有m*n个小格子的板，每个格子初始状态为live(1)或dead(0)，且于它的8个邻居(水平、竖直、斜线)使用如下4条规则进行交互：
1 任一live格子的live邻居数小于2将会死亡，因为人口不足；
2 任一live格子的live邻居数为2或3将会存活至下一代；
3 任一live格子的live邻居数大于3将会死亡，因为人口过剩；
4 任一dead格子的live邻居数正好为3时将会变为live，因为可以繁殖。

编写函数计算每个格子的状态来给出板的下一状态，依据以上规则，注意出生与死亡同时发生。

用例

输入：
0 1 0
0 0 1
1 1 1
0 0 0
输出：
0 0 0
1 0 1
0 1 1
0 1 0

跟进

1 能否在内部解决(即空间复杂度为1)？记住板需要同时更新：即不能先更新一个格子，然后用这个格子的状态去更新下个格子。
2 本问题中使用2维数列。但理论上，板是无限的，这会使得活跃区域超过数列的边界。改如何解决这个问题？

解决

class Solution {
    public void gameOfLife(int[][] board) {
    	if(board == null || board.length == 0) return; 
        for(int i=0; i<board.length; i++) {
        	for(int j=0; j<board[0].length; j++) {
        		int lives = findLivesBin(board, i, j);
        		if(board[i][j] == 0 && lives == 3) {
        			board[i][j] = 2;
        		}
        		if(board[i][j] == 1 && lives >= 2 && lives <= 3) {
        			board[i][j] = 3;
        		}        		
	
        	}	
        }    	
        for(int i=0; i<board.length; i++) {
        	for(int j=0; j<board[0].length; j++) {
        		board[i][j] >>= 1;// get 2
        	}
        }        
    }
    public int findLivesBin(int[][] board, int m, int n) {
    	int lives = 0;
    	for(int i=Math.max(0, m-1); i<=Math.min(board.length-1, m+1); i++) {
    		for(int j=Math.max(0, n-1); j<=Math.min(board[0].length-1, n+1); j++) { 
    			lives += board[i][j] &1;// get 1
    		}
    	}
        lives -= board[m][n] & 1;// get 3
    	return lives;
    }    
    
}

个人收获

0. 暴力枚举很容易想到，但空间复杂度为O(mn)不符合题目要求，使用十转二的方式能够得到多余位数来表达状态，节省空间
1. 当十进制转换为二进制时1个数位能表示2个状态
2. 获取第一位状态和1相与，获取第二位状态则右移1位
3. 求附近live邻居数时，首先要能想到通用的求法(有3类格子：角、边、非边角)，以及最后要减去自身的重复

题目来源：Leetcode 289