每日算法题—N天后的牢房

题目描述

原题目是用牢房来打比喻，有时候这种题目总是读半天都不知道啥意思，所以直接大白话理解下
一个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
    }