LRU缓存结构，简单总结起来就是本次的读写数据记录会被设为最新，并将其移动到链表的头部，当写操作发现缓存区已达到最大存储阈值，就将处在链表尾部，也即是被认为是最近最少被使用的数据删除掉，将新数据存入表头。
要自己设计一个LRU缓存，关键点是，写可以保证最新的记录直接就在表头，读并不会写入新元素，如何将本次读的记录变为最新记录呢？脑筋急转弯时间。
是的，那就是读的时候也写入一遍，就是把该元素从当前保存的位置先删除，然后呢，再添加一遍，这样该元素就顺利移动到了表头，成为了最新的记录。
直接上码，
class MainActivity : AppCompatActivity() {
override fun onCreate(savedInstanceState: Bundle?) {
super.onCreate(savedInstanceState)
setContentView(R.layout.activity_main)
Log.e("data", LRU(arrayOf(intArrayOf(1, 1, 6), intArrayOf(1, 2, 2), intArrayOf(1, 3, 6), intArrayOf(2, 1), intArrayOf(1, 4, 6), intArrayOf(2, 2)), 3).contentToString())
}
//LRU结构
var map: MutableMap? =null
var size: Int =0
var list = ArrayList()//要输出的结果的集合
companion object{
val READ =2//读取缓存操作
val WRITE =1//写入缓存操作
}
//operators为输入的测试用例
fun LRU(operators: Array, k: Int): IntArray {
size = k
for (it in operators) {//循环处理每一个用例
when (it[0]) {
WRITE -> {
set(it[1], it[2])
}
READ -> {
var array = it
map?.let {
get(array[1])
}
}
}
}
return list.toIntArray()//返回结果集合
}
fun set(key: Int, value: Int) {
if (map ==null) {
map =mutableMapOf(key to value)
}else {
if (map?.size ==size) {//达到阈值就删除表尾元素
for (key in map!!.keys) {
map?.remove(key)
break
}
}
map?.put(key, value)//将新元素存到表头
}
}
fun get(key: Int): Int? {
var a =if ((map?.containsKey(key)) ==true) {
//先删除，在添加，这个操作成功把当前元素移动到了表头的位置，成了最新的记录
var value = (map?.get(key)) ?:0
map?.remove(key)
map?.put(key, value)
map?.get(key)
}else {
-1
}
print(a)
list.add(a ?: -1)
return a
}
}
