class AllOne {
public AllOne() {
}
public void inc(String key) {
}
public void dec(String key) {
}
public String getMaxKey() {
}
public String getMinKey() {
}
}
二、思路（自己）
这个题目我感觉并不难，就是设计一个数据结构和它的函数，但是其实有点难理解的是它的题意。比如输入代表什么意思，还有就是字符串key的计数是什么意思？这里我绕了好大的弯，getMaxKey返回任意一个计数最大的字符串？（挺打脸的，它要求时间复杂度为O(1)））我代码写完执行出错才发现原来我理解错意思了，其实它的计数指的是AllOne中该字符串的个数，我理解为该字符串的比较大小了。如下为我的错误代码：
class AllOne {
List list=new ArrayList<>();
public AllOne() {
}
public void inc(String key) {
list.add(key);
}
public void dec(String key) {
list.remove(key);
if(list.size()==0) list.clear();
}
public String getMaxKey() {
if(this.list.size()==0) return "";
String s="";
for (int i = 0; i 0){
s=list.get(i);
}
}
return s;
}
public String getMinKey() {
if(this.list.size()==0) return "";
String s=list.get(0);
for (int i = 0; i s2.length()) return 1;
if(s1.length()
比较有意思的是居然还通过了10个测试用例懂题目意思了其实就不难了，因为之前也做过类似的题目。但是，我犯了个小错误，弄得我一直提交之后解答出错。
class AllOne {
// List list=new ArrayList<>();
Map map=new HashMap<>();
public AllOne() {
}
public void inc(String key) {
if(this.map.containsKey(key))
this.map.put(key,this.map.get(key)+1);
else
this.map.put(key,1);
}
public void dec(String key) {
if(this.map.containsKey(key)){
this.map.put(key,this.map.get(key)-1);
if(this.map.get(key)==0) map.remove(key);
}
}
Comparator> com=new Comparator>() {
@Override
public int compare(Map.Entry o1, Map.Entry o2) {
return o1.getValue()-o2.getValue();
}
};
public String getMaxKey() {
if(this.map.size()==0) return "";
//又是按照map的值取key，之前做过
List> list=new ArrayList<>(this.map.entrySet());
Collections.sort(list,com);
return list.get(list.size()-1).getKey();
}
public String getMinKey() {
if(this.map.size()==0) return "";
List> list=new ArrayList<>(this.map.entrySet());
Collections.sort(list,com);
return list.get(0).getKey();
}
} 最后还是未通过，为什么呢，时间复杂度高了
我记得我之前做过类似的题，是用set去重好像，但是具体怎么用我还是忘记了。。。我去翻翻以前的笔记。。。找不见了，估计那时候还没开始写博客
三、题解（官方）
题目要求O(1)的时间复杂度我看了评论区宫水三叶的答案，真厉害，是自己写一个哈希表来实现时间复杂度定义节点类，用来存储字符串出现的次数以下为代码和注释，挺好理解的
class AllOne{
//定义节点类用来作为哈希表的数组部分
class Node{
int cnt;//字符串出现的次数
Set set=new HashSet<>();//次数为cnt的字符串
Node left,right;//链表前后元素
Node(int _cnt){
cnt=_cnt;
}
}
Node hh,tt;
//记录输入的节点，减少遍历来查找
Map map=new HashMap<>();
public AllOne(){
//初始化双链表
hh=new Node(-1000);tt=new Node(-1000);
hh.right=tt; tt.left=hh;
}
void clear(Node node){
if(node.set.size()==0){
//如果node中没有字符串了，那么就把它消掉
node.left.right=node.right;
node.right.left=node.left;
}
}
public void inc(String key){
//如果之前已经存储过现在输入的字符串
if(map.containsKey(key)){
//取出哈希表数组部分的节点
Node node=map.get(key);
//因为该字符串数量加一，所以不能待在哈希表这个数组部分
node.set.remove(key);
int cnt=node.cnt;
Node next=null;
if(node.right.cnt==cnt+1){
//如果数量加一后为后面那个数组部分的数量，则将其放到下一个节点的位置
next=node.right;
}else {
//没有对应数量的节点，且后面的那个节点一定大于加一，将节点插入到刚才所在节点后面
next=new Node(cnt+1);
next.right=node.right;
next.left=node;
node.right.left=next;
node.right=next;
}
next.set.add(key);
//记录加入节点和位置
map.put(key,next);
clear(node);
}else {//如果之前没有存储过这个字符串，那么该字符串数量为1
Node node=null;
if(hh.right.cnt==1){
node=hh.right;//之前存在数量为1的字符串
}else {//没有数量为1的字符串，插入
node=new Node(1);
node.right=hh.right;
node.left=hh;
hh.right.left=node;
hh.right=node;
}
node.set.add(key);//把字符串放入node中
map.put(key,node);
}
}
public void dec(String key){
Node node=map.get(key);//找出key对应的节点位置
node.set.remove(key);
int cnt=node.cnt;
if(cnt==1){
map.remove(key);
}else {
Node prev=null;
if(node.left.cnt==cnt-1){
prev=node.left;
}else {
prev=new Node(cnt-1);
prev.right=node;
prev.left=node.left;
node.left.right=prev;
node.left=prev;
}
prev.set.add(key);
map.put(key,prev);
}
clear(node);
}
public String getMaxKey(){
Node node=tt.left;
for(String str:node.set) return str;
return "";
}
public String getMinKey(){
Node node=hh.right;
for(String str:node.set) return str;
return "";
}
}
继续加油！
