Kotlin中如何判断IntArray元素未赋值实现类似Java的记忆化逻辑?
Kotlin实现记忆化缓存的三种常用方案
方案1:使用可空Int类型数组(最贴近原Java实现)
Kotlin支持可空类型,直接声明Array<Array<Int?>>即可和Java的Integer[][]实现完全一致的null判断逻辑,不需要修改原有业务流程。
class Solution { // 可空Int二维数组,未初始化元素默认是null private lateinit var memory: Array<Array<Int?>> fun leetcode(array: IntArray): Int { // 按需初始化缓存数组维度,示例中第二维固定为2,可根据实际需求调整 val n = array.size memory = Array(n) { arrayOfNulls<Int?>(2) } return maxOf(dfs(0, 0), dfs(0, 1)) } fun dfs(status1: Int, status2: Int): Int { if (status1 == Int.MAX_VALUE || status2 == Int.MAX_VALUE) { return 0 } // 用Elvis运算符简化null判断逻辑,和Java的if(null)分支完全等价 return memory[status1][status2] ?: run { val res = calculate() + maxOf(dfs(status1 + 1, status2), dfs(status1 + 1, status2 + 1)) memory[status1][status2] = res res } } fun calculate(): Int { // 原有业务逻辑 return 0 } }
方案2:使用哨兵值标记未初始化状态(性能最优)
如果业务场景中缓存结果不可能出现某个特殊值(比如绝大多数DP题的计算结果都是非负整数),可以用该特殊值作为未计算的标记,直接使用基础类型的IntArray实现,避免装箱开销,性能比可空数组更高。
class Solution { private lateinit var memory: Array<IntArray> // 选取业务不可能出现的值作为未初始化标记,这里用Int最小值做示例 private val UNCALCULATED = Int.MIN_VALUE fun leetcode(array: IntArray): Int { val n = array.size // 初始化时所有元素填充为哨兵值 memory = Array(n) { IntArray(2) { UNCALCULATED } } return maxOf(dfs(0, 0), dfs(0, 1)) } fun dfs(status1: Int, status2: Int): Int { if (status1 == Int.MAX_VALUE || status2 == Int.MAX_VALUE) { return 0 } if (memory[status1][status2] != UNCALCULATED) { return memory[status1][status2] } val res = calculate() + maxOf(dfs(status1 + 1, status2), dfs(status1 + 1, status2 + 1)) memory[status1][status2] = res return res } fun calculate(): Int = 0 }
方案3:使用HashMap做缓存(适合稀疏状态场景)
如果状态范围很大但实际用到的状态很少,用数组初始化会浪费大量空间,可以用HashMap存储已计算的状态,以两个状态组成的Pair作为key,不存在的key即代表未计算。
class Solution { // 无需提前确定数组大小,仅存储实际用到的状态 private val memory = HashMap<Pair<Int, Int>, Int>() fun leetcode(array: IntArray): Int { memory.clear() return maxOf(dfs(0, 0), dfs(0, 1)) } fun dfs(status1: Int, status2: Int): Int { if (status1 == Int.MAX_VALUE || status2 == Int.MAX_VALUE) { return 0 } // 用getOrPut直接实现不存在就计算的逻辑,代码更简洁 return memory.getOrPut(status1 to status2) { calculate() + maxOf(dfs(status1 + 1, status2), dfs(status1 + 1, status2 + 1)) } } fun calculate(): Int = 0 }
内容的提问来源于stack exchange,提问作者ltoibq93578
相关产品推荐
相关产品推荐

