建一个团购网站,宁波网站排名优化报价,随州北京网站建设,江阴早晨网站建设题目 题目链接#xff1a; https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84
思路 双向链表map最新的数据放头结点#xff0c;尾节点放最老的数据#xff0c;没次移除尾巴节点本地考察链表的新增#xff0c;删除#xff0c;移动节点参考答案Java
im…题目 题目链接 https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84
思路 双向链表map最新的数据放头结点尾节点放最老的数据没次移除尾巴节点本地考察链表的新增删除移动节点参考答案Java
import java.util.*;public class Solution {MapInteger, Node cache new HashMap();Node start, end;int cap 0;public Solution(int capacity) {// write code herecap capacity;}public int get(int key) {//key对应节点移动到头部成为头节点if (!cache.containsKey(key)) return -1;Node cur cache.get(key);int v cur.data;Node next cur.next;Node prev cur.prev;if (next ! null prev ! null) { //cur 要变成头结点next.prev prev;prev.next next;if (next.next null) { //这里似乎可以不要end next;}cur.next start;start.prev cur;start cur;} else if (next ! null) { //说明cur是头结点不管了} else if (prev ! null) { //自己是尾结点prev.next null; //自己的prev要成为尾巴prev.next设置为nullcur.next start;start.prev cur;start cur;end prev; //尾巴修改为自己的前一个节点}return v;}public void set(int key, int value) {if (cache.containsKey(key)) {cache.get(key).data value;cache.put(key, cache.get(key));get(key); //使用一次移动到头部} else {Node node new Node(key, value);if (cap 1) { //容量为1时特殊处理start end node;cache.clear();cache.put(key, node);return;}int size cache.size();if (start null) {start node;end node;cache.put(key, node);} else if (size cap) { //不需要移除尾节点直接修改头部node.next start;start.prev node;start node;cache.put(key, node);} else {
// System.out.println();
// System.out.println(key value);
// System.out.println();Node last end;Node lastprev last.prev;end lastprev; //设置新的尾节点cache.remove(last.key);end.next null;last null;node.next start;start.prev node;start node; //设置新的头结点cache.put(key, node);}//show(start);}}static class Node {int key;int data;Node prev;Node next;public Node(int k, int d) {key k;data d;}}public void show(Node root) { //帮助打印的本答案可以不需要System.out.println();Node t root;SetInteger s new HashSet();while (t ! null) {System.out.print(t.key t.data );t t.next;//if(s.contains(t.data)) break;}System.out.println();}}/*** Your Solution object will be instantiated and called as such:* Solution solution new Solution(capacity);* int output solution.get(key);* solution.set(key,value);*/本答案在lintcode 上相同题目没有通过全部测试用例 https://www.lintcode.com/problem/134/ 后期找到原因后再修改本答案
