数据结构设计高频题

注: 本节以数据结构设计高频题为主，并不涉及太难的数据结构设计题目

题目1 : setAll功能的哈希表

测试链接 : https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967
思路
- 添加时间戳, map的v放置一个数组, 0下标为value,1 下标为对应的时间, 每次添加或修改时都要更新时间戳
- 添加两个变量: setAllValue setAllTima, setAll方法只需更新两个变量
- get时根据最晚的时间戳取值

代码

// key: Integer value: {v,timestamp}
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));// BufferedReaderStreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));// PrintWriterwhile (in.nextToken() != StreamTokenizer.TT_EOF) {// 清空map.clear();setAllValue = 0;setAllTime = -1;cnt = 0;n = (int) in.nval;for (int i = 0; i < n; i++) {// 用for输入n组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();
}

题目2 : 实现LRU结构

测试链接 : https://leetcode.cn/problems/lru-cache/
思路
- 使用哈希表和双向链表实现
- 哈希表中的键为Integer, 值为DoubleNode, 所有的值(DoubleNode)连在一起成为DoubleList,维持时序,标识早晚, head标识最早, tail标识最晚, 当哈希表达到capacity, 删除head标识的值, 并在DoubleList中也删除head
- 每一次LRU访问操作都要更新所对应结点的位置, 将其放置表尾, 标识最新操作

代码

// 实现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) {// 链表内部的nodeif (tail == node) {// 在尾巴上return;}if (head == node) {// 在头上(换头)head = node.next;// 头来到下一个节点head.last = null;// 头的last为空} 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<>();// hash表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);// 移除链表和hash表中最晚的节点}// 没满,直接加DoubleNode newNode = new DoubleNode(key, value);keyNodeMap.put(key, newNode);nodeList.addNode(newNode);}}}}

题目3 : 插入、删除和获取随机元素O(1)时间的结构

测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/
思路
- 使用arr操作,使用HashMap判断去重, map中k-v分别对应插入的数值 - 在数组中的下标, 以方便在arr中操作,达到O(1)
- 插入
  - 先判断是否含有
  - 先更新map,为了使用arr.size,要放置的下标是arr.size()
  - 更新动态数组
- 删除
  - 先判断是否不含
  - 在arr中查找最后一个值, 如果是最后一个值,直接删除
  - 如果不是最后一个值, 用最后一个值替代,然后删除最后一个值
- 获取随机元素
  - (int) (Math.random() * arr.size()) : [0,arr.size - 1]上整数等概率出现, 在arr中取值

代码

	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)) {// 含有valreturn false;// 不插入}// 不含val,插入map.put(val, arr.size());// 先更新map,为了使用arr.size,要放置的下标是arr.size()arr.add(val);// 更新动态数组return true;}public boolean remove(int val) {if (!map.containsKey(val)) {// 不含val,不进行删除操作return false;}// 进行删除操作int valIndex = map.get(val);// 在map中查找下标int endValue = arr.get(arr.size() - 1);// 在arr中查找最后一个值if(val == endValue){}else{map.put(endValue, valIndex);// 在map中用最后一个数值替换到原数值的下标上arr.set(valIndex, endValue);// 在set中用最后一个数值替换}map.remove(val);// 根据值删除,将map中原数值删除(还存在,map中有两个相等的val)arr.remove(arr.size() - 1)// 根据下标删除,将数组中最后一个用来代替的值删除;return true;}public int getRandom() {// 		[0,arr.size - 1]上整数等概率出现return arr.get((int) (Math.random() * arr.size()));// 随机取一个下标}

题目4 : 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构

测试链接 :https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
思路
- arr进行保存, HashMap<Integer, HashSet>, 分别对应保存的数值 - 该数值在数组中的所有下标
- 插入
  - 加到数组中
  - 找出该值对应的set,并在set中添加下标
  - 重新放置该set(原来可能有,可能没有)
  - 返回val是不是第一次进来(题目要求)
- 删除
  - 判断是否含有该值
  - 判断是不是要删除数组最后一个,如果是,直接删除
  - 不是删除最后一个, 最后一个值替换要删除的值, 在最后一个值的set中加入要删除值的下标, 在arr中要删除值的下标位置放置最后一个值, 要删除值的set中删除原下标, 最后一个值的set中删除最后最后一个位置(已经被移走)
  - 判断删完后的set是否为空, 如果为空, 直接将val从map中删除
- 随机值
  - (int) (Math.random() * arr.size()) : [0,arr.size - 1]上整数等概率出现, 在arr中取值, 自动调整权重,相同的数会放在数组上

代码

	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) {// 1. 加到数组中arr.add(val);// 2. 找出该值对应的set,并在set中添加下标HashSet<Integer> set = map.getOrDefault(val, new HashSet<Integer>());// 有: 拿value;没有: 拿default位set.add(arr.size() - 1);// 3. 重新放置该set(原来可能有,可能没有)map.put(val, set);// 4. 返回val是不是第一次进来return set.size() == 1;}public boolean remove(int val) {if (!map.containsKey(val)) {return false;}HashSet<Integer> valSet = map.get(val);// 该值对应的setint valAnyIndex = valSet.iterator().next();// 在set中任取一个int endValue = arr.get(arr.size() - 1);// 取最后一个值if (val == endValue) {// 要删的是最后一个valSet.remove(arr.size() - 1);// set中删除} else {// 要删的不是最后一个,用要删的替换最后一个HashSet<Integer> endValueSet = map.get(endValue);// 最后一个值对应的setendValueSet.add(valAnyIndex);// 在最后一个值的set中添加删除值的下标,因为该值移动到了删除值的位置arr.set(valAnyIndex, endValue);// 在arr中用最后一个值替代原值set中的任意一个endValueSet.remove(arr.size() - 1);// 最后一个值的set中移除arr中最后一个下标valSet.remove(valAnyIndex);// 该值对应的set中移除要移除的值}arr.remove(arr.size() - 1);// arr中删除if (valSet.isEmpty()) {// 如果set中是空的,即该值已经没有在arr中放置map.remove(val);}return true;}public int getRandom() {// 自动调整权重,相同的数会放在数组上return arr.get((int) (Math.random() * arr.size()));}}

题目5 : 快速获得数据流的中位数的结构

测试链接 : https://leetcode.cn/problems/find-median-from-data-stream/
思路
- addNum()
  - 使用 一个大根堆一个小根堆, 大根堆存放较小的那一半, 当两个堆中都没有值 或者 num<大根堆顶(最大值), 加入大根堆, 加入的过程保持两堆数量相差不超过1
  - 加入后堆可能不平衡, 要进行调整
- 调整
  - 当两堆相差超过一个, 进行调整, 将较多的堆的堆顶放入另一个堆
- findMedian()
  - 若两堆数量相等, 中位数为两堆堆顶和除以2
  - 若两堆数量不等, 中位数为较多的堆的堆顶

代码

	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) {// 当大根堆为空 或者 num<大根堆顶(最大值), 加入大根堆maxHeap.add(num);} else {minHeap.add(num);}balance();// 可能会不平衡, 进行调整}public double findMedian() {if (maxHeap.size() == minHeap.size()) {// 两堆存放的数量相等return (double) (maxHeap.peek() + minHeap.peek()) / 2;// 中间值是两堆堆顶的平均值// 使用peek, 因为是查看, 原来的数不能改变z} else {// 如果两堆存放的数量不相等, 中间值为存放数量较多堆的堆顶return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();}}private void balance() {// 进行调整if (Math.abs(maxHeap.size() - minHeap.size()) == 2) {// 如果两堆数量相差2, 进行调整if (maxHeap.size() > minHeap.size()) {// 较多的堆的堆顶放入另一个堆minHeap.add(maxHeap.poll());} else {maxHeap.add(minHeap.poll());}}}}

题目6 : 最大频率栈

测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/
思路
- 三个变量: topTimes 最大词频数; HashMap<Integer, ArrayList> 每个词频对应的数; HashMap<Integer, Integer> 每个数对应的词频
- push
  - 更新自己的词频
  - 查出自己的词频, 查出该词频对应的保存值的数组, 没有的话新建, 加入该数
  - 看看是否需要更新最大词频
- pop
  - 弹出词频对应的动态数组;里的最后一个值
  - 如果动态数组为空, 删除该值, 最大词频-1
  - 词频表中查询该值的词频, 判断是需要-1 还是需要删除

代码

	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) {// 更新自己的词频	更新为原词频数+1valueTimes.put(val, valueTimes.getOrDefault(val, 0) + 1);// 更新操作// 当前数的最大次int curTopTimes = valueTimes.get(val);// 如果没有这么高的链表if (!cntValues.containsKey(curTopTimes)) {cntValues.put(curTopTimes, new ArrayList<>());// 在map中加上该高度的动态数组}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--);// 1.把最高层的链表移除掉 2.最大词频-1}// 词频表int times = valueTimes.get(ans);// 如果移除前这个值的词频为1if (times == 1) {valueTimes.remove(ans);// 则移除后这个值就没了} else {valueTimes.put(ans, times - 1);// 否则, 这个数的词频表里要减少一次}return ans;}}

题目7 : 全O(1)的数据结构

测试链接 : https://leetcode.cn/problems/all-oone-data-structure/
思路
- 用一个双向链表(用于连接桶们), 一个map用于记录字符串以及对应的桶的地址, 桶链表要含有头和尾, 用于简化操作
- inc(新增)
  - 看看map里有没有该字符串的记录
    - 没有
      - 看看有没有词频为1的桶
        有: 放入
        没有: 新增
    - 有
      - 找桶,词频加一即原桶的下一个
        有词频加一的桶
        词频加一的桶接收, 改map
        
        没有
        新增
        改map
      - 将原桶记录中的字符串删除
        如果桶空了, 在链表中将桶移除
- dec(删除)
  - 删桶的时候一定有桶, 找出该桶
    - 若该桶的词频为1
      - map删除该key对应的桶的内存地址
    - 词频不为1
      - 往左移动
        左边有桶, 往左搬家
        左边没桶, 新增左桶,往左搬家
  - 原桶里字符串删除(移除了map中的字符串,但是该词频的桶还存在)
    - 如果桶空了, 把整个桶删掉

代码

	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后插入poscur.next.last = pos;pos.next = cur.next;cur.next = pos;pos.last = cur;}private void remove(Bucket cur) {// 删掉curcur.last.next = cur.next;cur.next.last = cur.last;}Bucket head;Bucket tail;HashMap<String, Bucket> map;public AllOne() {// 一整个双向链表:// head -> [bucket:词频逐渐增大] -> tailhead = 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)) {// 先看看map里有没有该字符串的记录if (head.next.cnt == 1) {// 看看有没有词频为1的桶map.put(key, head.next);// 有->放入head.next.set.add(key);} else {// 没有词频为1的桶Bucket newBucket = new Bucket(key, 1);// 新建词频为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);// 改mapbucket.next.set.add(key);// 词频加一的桶接收} else {// 原桶的下一个不是词频加一Bucket newBucket = new Bucket(key, bucket.cnt + 1);// 新建桶map.put(key, newBucket);// 加mapinsert(bucket, newBucket);// 链表链桶:在 老桶 的后面 加入新桶}bucket.set.remove(key);// 老桶删keyif (bucket.set.isEmpty()) {// 如果桶空了remove(bucket);// 把桶删掉}}}public void dec(String key) {Bucket bucket = map.get(key);// 删桶的时候一定有桶if (bucket.cnt == 1) {// 该桶的词频为1map.remove(key);// map删除该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);// 原桶里字符串删除(移除了map中的字符串,但是该词频的桶还存在)if (bucket.set.isEmpty()) {// 如果桶空了remove(bucket);// 把整个桶删掉}}public String getMaxKey() {return tail.last.set.iterator().next();}public String getMinKey() {return head.next.set.iterator().next();}}