面试经典150题——生命游戏

03-15 1445阅读 0评论

"Push yourself, because no one else is going to do it for you." - Unknown

$面试经典150题——生命游戏,面试经典150题——生命游戏,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第2张$

（图片来源网络，侵删）

1. 题目描述

2. 题目分析与解析

2.1 思路一——暴力求解

之所以先暴力求解，是因为我开始也没什么更好的思路，所以就先写一种解决方案，没准写着写着就来新的灵感了。暴力求解思路还是很简单的，就是尝试遍历面板的每个格子，判断其周围八个位置的状态（对于边角需要特殊处理），根据边角种存在的活细胞（也就是1的个数）判断该位置应该填什么。

但是需要注意一点，为了避免我们在原矩阵上更改值后导致影响后续的判断，所以我们肯定需要先复制一个原始矩阵。

代码思路：

初始化，复制一个原始矩阵
$面试经典150题——生命游戏,面试经典150题——生命游戏,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第5张$
（图片来源网络，侵删）
遍历复制矩阵的每一个元素，查看其周围八个位置的状态，统计1的个数
- 根据题目提到的判定规则：少于 2 个或者大于 3 个 1 就判定当前位置为 0
- 等于 2 个 1 那么当前位置不需要更改
- 如果等于 3 个 1 那么当前位置如果为 0 需要改为 1
- 对于边角位置需要额外处理防止越界

2.2 思路二——进阶（原地算法）

$面试经典150题——生命游戏,面试经典150题——生命游戏,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第7张$

（图片来源网络，侵删）

根据题目中的进阶提示，要求使用原地算法，也就是不能用一个额外的面板存储现有的值，并且还提示了所有格子被同时更新。因此我们再想一想怎么解决。

如果使用原地算法，最主要的问题就是对于前面内容的更新会影响后面的结果，因为你不知道原来前面的内容是什么样子。但是记住，原始状态只有两种，要么是0，要么是1。

而变化也只有四种

要么原来是0，后来变成1
要么原来是0，保持不变为0
要么原来是1，后来变成0
要么原来是1，后来不变为1

如下图：

因为我们担心原始信息被覆盖，因此我们是不是可以添加几个数字也就相当于几种状态，来存储这些被覆盖的信息？这样我们看见某一个数字就知道它之前是什么状态，就相当于在原始数据的基础上进行操作了！在这里我们假设：

用 0 和 1 还是表示原来是什么现在就是什么的情况，也就是对应上图中两种不变的情况
而用数字2表示 0 改变为 1
用数字3表示 1 改变为 0

作图表示如下：

对于这种原地算法，如果你需要用到之前的信息，但是可能之前的信息会被修改，就想办法把原始信息用一种方式存储起来。

因此我们在遍历面板的每一个元素时，我们就知道之前的位置原始数据是什么，这样就能正确计算结果，等到最后我们再根据每一种数字的情况将它归为正确的表示，比如最后我们处理完了所有数据，然后我们再遍历每个元素：
- 发现值为0或者1就不动
- 发现值为2就变为1
- 发现值为3就变为0
  
  这样就可以得到最终结果！
  
  代码思路：
  1. 遍历面板每一个元素，根据原始状态和需要改变为的值确定该位置的值
    - 对于面板每一个元素，遇见周围八个位置中有1和3就把它当作1
      - 对于面板每一个元素，遇见周围八个位置中有2和0就把它当作0
    - 处理完每个元素后再次遍历整个面板，将1与3替换回正确的值
  2.3 思路三——思路一的优化（位运算）
  
  现在我们看看还有没有什么优化空间，有时间提示信息不是白给的哦：
  
  题目提示我们board[i][j] 为 0 或 1，0和1，有没有想到什么？学计算机的0和1分别表示什么？在java中int是怎么存储的？
  
  再看看面板的大小？1