a**********0
发帖数: 422 | 1 自己的代码老通不过 不知道为什么
public class LRUCache {
int cap;
//hashmap is for Cache's storage
// arraylist is for item's recency
HashMap myHashMap = new HashMap();
// key-value
ArrayList myArrayList = new ArrayList();// key
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if(this.myHashMap.get(key) == null)
return -1;
this.myArrayList.remove(new Integer(key));
this.myArrayList.add(key);
return this.myHashMap.get(key).intValue();
}
public void set(int key, int value) {
if(this.myHashMap.size()< this.cap){
if(this.myHashMap.get(key) != null){
this.myHashMap.put(key,value);
this.myArrayList.remove(new Integer(key));
this.myArrayList.add(new Integer(key));
}else{
this.myHashMap.put(key,value);
this.myArrayList.add(new Integer(key));
}
}else{
if(this.myHashMap.get(key) != null){
this.myHashMap.put(key,value);
this.myArrayList.remove(new Integer(key));
this.myArrayList.add(new Integer(key));
}else{
this.myHashMap.remove(myArrayList.get(0));
this.myHashMap.put(key,value);
this.myArrayList.remove(0);
this.myArrayList.add(key);
}
}
}
} |
s******s
发帖数: 84 | 2 myArrayList.remove(new Integer(key)); 这个地方有问题吧，java 里面的remove（
index）是index/position 而不是key的吧 |
a**********0
发帖数: 422 | 3 建议你看看arraylist的文档
【在 s******s 的大作中提到】
: myArrayList.remove(new Integer(key)); 这个地方有问题吧，java 里面的remove（
: index）是index/position 而不是key的吧
|
c*********w
发帖数: 65 | 4 Use LinkedHashMap, check its javadoc. |
a**********0
发帖数: 422 | 5 网上有人用你说的数据结构做LRU 我没仔细看 类似的代码一大堆
我估计我的代码一点错误也没有 只是超时而已
【在 c*********w 的大作中提到】
: Use LinkedHashMap, check its javadoc.
|
l***i
发帖数: 1309 | 6 If you use linkedHashMap, there is nothing to do to get LRUCache. |
o***g
发帖数: 2784 | 7 虽然ArrayList也有remove(Object O)，但是int还有boxing unboxing，传一个Integer
，你确定是匹配remove(Object)而不匹配remove(int)？另外，实现的时候是用的==还
是equals，你知道么？
【在 a**********0 的大作中提到】
: 建议你看看arraylist的文档
|
a**********0
发帖数: 422 | 8 我的程序超时 超在哪里呢？
我觉得hashmap的操作基本都是constant的 不可能超时 但是我用arraylist记录
recency
估计超时在这里
【在 l***i 的大作中提到】
: If you use linkedHashMap, there is nothing to do to get LRUCache.
|
P******r
发帖数: 1342 | 9 arraylist 的remove比较花时间吧？ |
a**********0
发帖数: 422 | 10 我不知道这个题目要做什么 用java collections 非常容易解决 尽管不快
你有什么建议吗 难道只能linkedhashmap
因为这个保留recency的数据结构必须要求 1 可以删除 端点 2 可以删除object
hashmap不能 因为不支持删除端节点
list 可以删端节点 但是又不支持删object
arraylist可以 但是慢
艹
【在 P******r 的大作中提到】
: arraylist 的remove比较花时间吧？
|
|
|
e***l
发帖数: 710 | 11 arraylist remove需要o (n). 自己实现一个链表, o (1)删除, 就可以过了 |
a**********0
发帖数: 422 | 12 自己实现的list只能记录recency 也就是哪一个是最老的 ： 头节点
我需要这个list还要有根据内容 添加 删除 的功能
所以这不是一个option
【在 e***l 的大作中提到】
: arraylist remove需要o (n). 自己实现一个链表, o (1)删除, 就可以过了
|
h******h
发帖数: 6 | |
e***l
发帖数: 710 | 14 自己维护prev, next, 添加删除都是常数时间。这是最容易想到的解法。
【在 a**********0 的大作中提到】
: 自己实现的list只能记录recency 也就是哪一个是最老的 ： 头节点
: 我需要这个list还要有根据内容 添加 删除 的功能
: 所以这不是一个option
|
e***l
发帖数: 710 | 15 刚才又想了一下，不自己实现双链表，直接用一个list和两个hashmap也能做，能通过
OJ，而且更简洁。等会有时间贴代码 |
e***l
发帖数: 710 | 16 import java.util.ArrayList;
import java.util.HashMap;
// TODO: rename this class to "LURCahch" for Leetcode submission
public class LRUCache2 {
private ArrayList list; // list of keys
private HashMap valueMap; // key-value map
private HashMap countMap; // appearance of each keys
in the key list
private int maxSize;
public LRUCache2(int capacity) {
maxSize = capacity;
list = new ArrayList();
valueMap = new HashMap();
countMap = new HashMap();
}
public int get(int key) {
if (valueMap.containsKey(key)) {
removeEldest(); // remove eldest entry if necessary
} else {
return -1;
}
list.add(key);
countMap.put(key, countMap.containsKey(key) ? countMap.get(key) + 1
return valueMap.containsKey(key) ? valueMap.get(key) : -1;
}
// append new keys
public void set(int key, int value) {
list.add(key);
countMap.put(key, countMap.containsKey(key) ? countMap.get(key) + 1
valueMap.put(key, value);
}
public void removeEldest() {
while (valueMap.size() > maxSize) {
int key = list.remove(0);
int count = countMap.get(key);
if (count == 1) {
valueMap.remove(key); // the least used entry
}
countMap.put(key, count - 1);
}
}
} |
p*****2
发帖数: 21240 | 17
面试不是刷题。
【在 e***l 的大作中提到】
: 刚才又想了一下，不自己实现双链表，直接用一个list和两个hashmap也能做，能通过
: OJ，而且更简洁。等会有时间贴代码
|
l*****a
发帖数: 14598 | 18 大牛介绍一下
那些面试要求system design,建一个scalable web/distributed system
然后进去之后就是整天维护别人的code, 解点小bug
充其量在现有architecture上照葫芦画瓢的加点新功能
的厂子是咋回事？
【在 p*****2 的大作中提到】
:
: 面试不是刷题。
|
z****e
发帖数: 54598 | 19 好像你说对了
remove有两个方法
在overload的时候要区分
remove(object)和remove(int)方法
这个在1.5之后是经常出问题的一个地方
autoboxing其实做得不好
【在 s******s 的大作中提到】
: myArrayList.remove(new Integer(key)); 这个地方有问题吧，java 里面的remove（
: index）是index/position 而不是key的吧
|
