题目描述
原题目是用牢房来打比喻，有时候这种题目总是读半天都不知道啥意思，所以直接大白话理解下
一个8位数组：[0, 1, 0, 1, 1, 0, 0, 1]，数组的值只有0和1两种取值，现在需要对数组做变换，每轮变换需要遵守如下规则：
如果第i-1位和第i+1位相等，则第i位置为1，否则置为0
首尾两位没有相邻的2个位，所以一直为0
来源：https://leetcode-cn.com/problems/prison-cells-after-n-days/
求第N轮后数组是多少？
还是很难懂吧...做一轮实操
[0, 1, 0, 1, 1, 0, 0, 1]做一轮变换后取值为：
[0, 1, 1, 0, 0, 0, 0, 0]
第1位置1是因为第0位==第2位
第2位置1是因为第1位==第3位
第3位置0是因为第2位和第4位不相等，所以置0
思路
最开始的思路是直接一遍一遍的遍历不就完了，这有啥难得，代码写好后一运行，跑的挺好的以为就这样结束了，结果一看人家的测试用例，N=1000000000，跑到电脑爆炸
思路：一共8位数组，每位取值为0或1，那么总共就256中取值可能，所以当变换遍历到一定遍数后一定会遇到和原数组一模一样的数组，也就是说存在轮回，假设第K遍和原数组一样，R=N%(K-1)，那么第R遍的结果就是第N遍的结果，直接返回第R遍的结果即可
工具：list，用lis将每一遍变换的结果存下来，当遇到和list中存的结果一样时，则判断接下来将进入重复的循环变换中
实现
fun prisonAfterNDays(cells: IntArray, N: Int): IntArray {
val result = cells.copyOf()//用来保存上一次变换后的结果
val resultCache = ArrayList<String>()
for (i in 1..N) {
cells.forEachIndexed { d, v ->
if (d == 0 || d == result.size - 1) {//如果是首位和尾位，则直接置0
cells[d] = 0
} else {
//如果前一位和后一位异或后的结果为1，说明前后两位不一样，那么本位需要置0，否则置1
cells[d] = if (result[d - 1] xor result[d + 1] == 1) 0 else 1
}
}
//因为这里始终是有2个数组对象，不能存list，所以我将数组用字符“|”连起来存入list中，用于保存变换结果，这里判断出list中已存在相同的计算结果，则直接计算出余数，再利用余数从list里取结果即可
if (resultCache.contains(cells.joinToString(separator = "|"))) {
//减1是为了让下标从0开始
var index = N % (i - 1) - 1
//如果是 -1，代表N和i-1余数为0，即数据就是list的最后一个
index = if (index == -1) resultCache.size - 1 else index
//取出数据，再转换成数组即可
return resultCache[index].split("|").map(String::toInt).toIntArray()
}
resultCache.add(cells.joinToString(separator = "|"))
System.arraycopy(cells, 0, result, 0, result.size)
}
return result
}
网友评论