class035 数据结构设计高频题【算法】

package class035;
// setAll功能的哈希表
// 测试链接 : https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;
public class Code01_SetAllHashMap {
  public static HashMap<Integer, int[]> map = new HashMap<>();
  public static int setAllValue;
  public static int setAllTime;
  public static int cnt;
  public static void put(int k, int v) {
    if (map.containsKey(k)) {
      int[] value = map.get(k);
      value[0] = v;
      value[1] = cnt++;
    } else {
      map.put(k, new int[] { v, cnt++ });
    }
  }
  public static void setAll(int v) {
    setAllValue = v;
    setAllTime = cnt++;
  }
  public static int get(int k) {
    if (!map.containsKey(k)) {
      return -1;
    }
    int[] value = map.get(k);
    if (value[1] > setAllTime) {
      return value[0];
    } else {
      return setAllValue;
    }
  }
  public static int n, op, a, b;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      map.clear();
      setAllValue = 0;
      setAllTime = -1;
      cnt = 0;
      n = (int) in.nval;
      for (int i = 0; i < n; i++) {
        in.nextToken();
        op = (int) in.nval;
        if (op == 1) {
          in.nextToken();
          a = (int) in.nval;
          in.nextToken();
          b = (int) in.nval;
          put(a, b);
        } else if (op == 2) {
          in.nextToken();
          a = (int) in.nval;
          out.println(get(a));
        } else {
          in.nextToken();
          a = (int) in.nval;
          setAll(a);
        }
      }
    }
    out.flush();
    out.close();
    br.close();
  }
}

package class035;
import java.util.HashMap;
// 实现LRU结构
public class Code02_LRU {
  // 测试链接 : https://leetcode.cn/problems/lru-cache/
  class LRUCache {
    class DoubleNode {
      public int key;
      public int val;
      public DoubleNode last;
      public DoubleNode next;
      public DoubleNode(int k, int v) {
        key = k;
        val = v;
      }
    }
    class DoubleList {
      private DoubleNode head;
      private DoubleNode tail;
      public DoubleList() {
        head = null;
        tail = null;
      }
      public void addNode(DoubleNode newNode) {
        if (newNode == null) {
          return;
        }
        if (head == null) {
          head = newNode;
          tail = newNode;
        } else {
          tail.next = newNode;
          newNode.last = tail;
          tail = newNode;
        }
      }
      public void moveNodeToTail(DoubleNode node) {
        if (tail == node) {
          return;
        }
        if (head == node) {
          head = node.next;
          head.last = null;
        } else {
          node.last.next = node.next;
          node.next.last = node.last;
        }
        node.last = tail;
        node.next = null;
        tail.next = node;
        tail = node;
      }
      public DoubleNode removeHead() {
        if (head == null) {
          return null;
        }
        DoubleNode ans = head;
        if (head == tail) {
          head = null;
          tail = null;
        } else {
          head = ans.next;
          ans.next = null;
          head.last = null;
        }
        return ans;
      }
    }
    private HashMap<Integer, DoubleNode> keyNodeMap;
    private DoubleList nodeList;
    private final int capacity;
    public LRUCache(int cap) {
      keyNodeMap = new HashMap<>();
      nodeList = new DoubleList();
      capacity = cap;
    }
    public int get(int key) {
      if (keyNodeMap.containsKey(key)) {
        DoubleNode ans = keyNodeMap.get(key);
        nodeList.moveNodeToTail(ans);
        return ans.val;
      }
      return -1;
    }
    public void put(int key, int value) {
      if (keyNodeMap.containsKey(key)) {
        DoubleNode node = keyNodeMap.get(key);
        node.val = value;
        nodeList.moveNodeToTail(node);
      } else {
        if (keyNodeMap.size() == capacity) {
          keyNodeMap.remove(nodeList.removeHead().key);
        }
        DoubleNode newNode = new DoubleNode(key, value);
        keyNodeMap.put(key, newNode);
        nodeList.addNode(newNode);
      }
    }
  }
}

package class035;
import java.util.ArrayList;
import java.util.HashMap;
// 插入、删除和获取随机元素O(1)时间的结构
public class Code03_InsertDeleteRandom {
  // 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/
  class RandomizedSet {
    public HashMap<Integer, Integer> map;
    public ArrayList<Integer> arr;
    public RandomizedSet() {
      map = new HashMap<>();
      arr = new ArrayList<>();
    }
    public boolean insert(int val) {
      if (map.containsKey(val)) {
        return false;
      }
      map.put(val, arr.size());
      arr.add(val);
      return true;
    }
    public boolean remove(int val) {
      if (!map.containsKey(val)) {
        return false;
      }
      int valIndex = map.get(val);
      int endValue = arr.get(arr.size() - 1);
      map.put(endValue, valIndex);
      arr.set(valIndex, endValue);
      map.remove(val);
      arr.remove(arr.size() - 1);
      return true;
    }
    public int getRandom() {
      return arr.get((int) (Math.random() * arr.size()));
    }
  }
}

package class035;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
// 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构
public class Code04_InsertDeleteRandomDuplicatesAllowed {
  // 测试链接 :
  // https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
  class RandomizedCollection {
    public HashMap<Integer, HashSet<Integer>> map;
    public ArrayList<Integer> arr;
    public RandomizedCollection() {
      map = new HashMap<>();
      arr = new ArrayList<>();
    }
    public boolean insert(int val) {
      arr.add(val);
      HashSet<Integer> set = map.getOrDefault(val, new HashSet<Integer>());
      set.add(arr.size() - 1);
      map.put(val, set);
      return set.size() == 1;
    }
    public boolean remove(int val) {
      if (!map.containsKey(val)) {
        return false;
      }
      HashSet<Integer> valSet = map.get(val);
      int valAnyIndex = valSet.iterator().next();
      int endValue = arr.get(arr.size() - 1);
      if (val == endValue) {
        valSet.remove(arr.size() - 1);
      } else {
        HashSet<Integer> endValueSet = map.get(endValue);
        endValueSet.add(valAnyIndex);
        arr.set(valAnyIndex, endValue);
        endValueSet.remove(arr.size() - 1);
        valSet.remove(valAnyIndex);
      }
      arr.remove(arr.size() - 1);
      if (valSet.isEmpty()) {
        map.remove(val);
      }
      return true;
    }
    public int getRandom() {
      return arr.get((int) (Math.random() * arr.size()));
    }
  }
}

package class035;
import java.util.PriorityQueue;
// 快速获得数据流的中位数的结构
public class Code05_MedianFinder {
  // 测试链接 : https://leetcode.cn/problems/find-median-from-data-stream/
  class MedianFinder {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;
    public MedianFinder() {
      maxHeap = new PriorityQueue<>((a, b) -> b - a);
      minHeap = new PriorityQueue<>((a, b) -> a - b);
    }
    public void addNum(int num) {
      if (maxHeap.isEmpty() || maxHeap.peek() >= num) {
        maxHeap.add(num);
      } else {
        minHeap.add(num);
      }
      balance();
    }
    public double findMedian() {
      if (maxHeap.size() == minHeap.size()) {
        return (double) (maxHeap.peek() + minHeap.peek()) / 2;
      } else {
        return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
      }
    }
    private void balance() {
      if (Math.abs(maxHeap.size() - minHeap.size()) == 2) {
        if (maxHeap.size() > minHeap.size()) {
          minHeap.add(maxHeap.poll());
        } else {
          maxHeap.add(minHeap.poll());
        }
      }
    }
  }
}

package class035;
import java.util.ArrayList;
import java.util.HashMap;
// 最大频率栈
public class Code06_MaximumFrequencyStack {
  // 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/
  class FreqStack {
    // 出现的最大次数
    private int topTimes;
    // 每层节点
    private HashMap<Integer, ArrayList<Integer>> cntValues = new HashMap<>();
    // 每一个数出现了几次
    private HashMap<Integer, Integer> valueTimes = new HashMap<>();
    public void push(int val) {
      valueTimes.put(val, valueTimes.getOrDefault(val, 0) + 1);
      int curTopTimes = valueTimes.get(val);
      if (!cntValues.containsKey(curTopTimes)) {
        cntValues.put(curTopTimes, new ArrayList<>());
      }
      ArrayList<Integer> curTimeValues = cntValues.get(curTopTimes);
      curTimeValues.add(val);
      topTimes = Math.max(topTimes, curTopTimes);
    }
    public int pop() {
      ArrayList<Integer> topTimeValues = cntValues.get(topTimes);
      int ans = topTimeValues.remove(topTimeValues.size() - 1);
      if (topTimeValues.size() == 0) {
        cntValues.remove(topTimes--);
      }
      int times = valueTimes.get(ans);
      if (times == 1) {
        valueTimes.remove(ans);
      } else {
        valueTimes.put(ans, times - 1);
      }
      return ans;
    }
  }
}

package class035;
import java.util.HashMap;
import java.util.HashSet;
// 全O(1)的数据结构
public class Code07_AllO1 {
  // 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/
  class AllOne {
    class Bucket {
      public HashSet<String> set;
      public int cnt;
      public Bucket last;
      public Bucket next;
      public Bucket(String s, int c) {
        set = new HashSet<>();
        set.add(s);
        cnt = c;
      }
    }
    private void insert(Bucket cur, Bucket pos) {
      cur.next.last = pos;
      pos.next = cur.next;
      cur.next = pos;
      pos.last = cur;
    }
    private void remove(Bucket cur) {
      cur.last.next = cur.next;
      cur.next.last = cur.last;
    }
    Bucket head;
    Bucket tail;
    HashMap<String, Bucket> map;
    public AllOne() {
      head = new Bucket("", 0);
      tail = new Bucket("", Integer.MAX_VALUE);
      head.next = tail;
      tail.last = head;
      map = new HashMap<>();
    }
    public void inc(String key) {
      if (!map.containsKey(key)) {
        if (head.next.cnt == 1) {
          map.put(key, head.next);
          head.next.set.add(key);
        } else {
          Bucket newBucket = new Bucket(key, 1);
          map.put(key, newBucket);
          insert(head, newBucket);
        }
      } else {
        Bucket bucket = map.get(key);
        if (bucket.next.cnt == bucket.cnt + 1) {
          map.put(key, bucket.next);
          bucket.next.set.add(key);
        } else {
          Bucket newBucket = new Bucket(key, bucket.cnt + 1);
          map.put(key, newBucket);
          insert(bucket, newBucket);
        }
        bucket.set.remove(key);
        if (bucket.set.isEmpty()) {
          remove(bucket);
        }
      }
    }
    public void dec(String key) {
      Bucket bucket = map.get(key);
      if (bucket.cnt == 1) {
        map.remove(key);
      } else {
        if (bucket.last.cnt == bucket.cnt - 1) {
          map.put(key, bucket.last);
          bucket.last.set.add(key);
        } else {
          Bucket newBucket = new Bucket(key, bucket.cnt - 1);
          map.put(key, newBucket);
          insert(bucket.last, newBucket);
        }
      }
      bucket.set.remove(key);
      if (bucket.set.isEmpty()) {
        remove(bucket);
      }
    }
    public String getMaxKey() {
      return tail.last.set.iterator().next();
    }
    public String getMinKey() {
      return head.next.set.iterator().next();
    }
  }
}