算法笔记-结构设计

主要涉及一些基础数据集的手写，如LRU，LFU，跳表，堆等

必备知识

在刷题过程中不要一看到题目就开始写，应该通过题目进行推测题目考查的点是哪个？通过那些数据结构可以解决？可以使用哪些算法？

相关题目

设计跳表（hard）

class Skiplist {
        /**
         * 最大层数
         */
        private static int DEFAULT_MAX_LEVEL = 32;
        /**
         * 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
         */
        private static double DEFAULT_P_FACTOR = 0.25;

        Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点

        int currentLevel = 1; //表示当前nodes的实际层数，它从1开始


        public Skiplist() {
        }

        public boolean search(int target) {
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, target);
                if (searchNode.next[i]!=null && searchNode.next[i].value == target){
                    return true;
                }
            }
            return false;
        }

        /**
         *
         * @param num
         */
        public void add(int num) {
            int level = randomLevel();
            Node updateNode = head;
            Node newNode = new Node(num,level);
            // 计算出当前num 索引的实际层数，从该层开始添加索引
            for (int i = currentLevel-1; i>=0; i--) {
                //找到本层最近离num最近的list
                updateNode = findClosest(updateNode,i,num);
                if (i<level){
                    if (updateNode.next[i]==null){
                        updateNode.next[i] = newNode;
                    }else{
                        Node temp = updateNode.next[i];
                        updateNode.next[i] = newNode;
                        newNode.next[i] = temp;
                    }
                }
            }
            if (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
                for (int i = currentLevel; i < level; i++) {
                    head.next[i] = newNode;
                }
                currentLevel = level;
            }

        }

        public boolean erase(int num) {
            boolean flag = false;
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, num);
                if (searchNode.next[i]!=null && searchNode.next[i].value == num){
                    //找到该层中该节点
                    searchNode.next[i] = searchNode.next[i].next[i];
                    flag = true;
                    continue;
                }
            }
            return flag;
        }

        /**
         * 找到level层 value 大于node 的节点
         * @param node
         * @param levelIndex
         * @param value
         * @return
         */
        private Node findClosest(Node node,int levelIndex,int value){
            while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
                node = node.next[levelIndex];
            }
            return node;
        }


        /**
         * 随机一个层数
         */
        private static int randomLevel(){
            int level = 1;
            while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
                level ++ ;
            }
            return level;
        }


        class Node{
            Integer value;
            Node[] next;

            public Node(Integer value,int size) {
                this.value = value;
                this.next = new Node[size];
            }

            @Override
            public String toString() {
                return String.valueOf(value);
            }
        }

    }

381. O(1) 时间插入、删除和获取随机元素 - 允许重复（hard)

class RandomizedCollection {
    //哈希表(O(1)操作)+数组(随机)
    //哈希表key为插入的数，val为其数在list中的下标集合(因为插入的元素可重复)
    //每次删除val，通过获取map中的val一个下标，与list最后一个元素交换，即可达到O(1)效果
    Map<Integer,Set<Integer>> map;
    List<Integer> list;
    public RandomizedCollection() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }
    //添加:加入list末尾和map以及map中的下标
    public boolean insert(int val) {
        list.add(val);
        Set<Integer> set = map.getOrDefault(val, new HashSet<Integer>());
        set.add(list.size() - 1);
        map.put(val, set);
        return set.size() == 1;
    }
    //删除
    public boolean remove(int val) {
        //判断是否存在
        if(!map.containsKey(val))return false;
        //set只能通过迭代器获取(获取val在list中的下标)
        Iterator<Integer> iterator = map.get(val).iterator();
        int i = iterator.next();
        //当前列表中最后一个元素
        int lastNum = list.get(list.size() - 1);
        //i和最后一个数交换位置
        list.set(i, lastNum);
        //map存储的下标也要删除干净，移除val在map中的下标
        map.get(val).remove(i);
        //移除lastNum在map中的下标
        map.get(lastNum).remove(list.size() - 1);
        //如果i不是最后一个元素(lastNum和val不是同一个元素)，则需要更新lastNum交换后的下标
        if (i < list.size() - 1) {
            map.get(lastNum).add(i);
        }
        //如果在此次list中有只有一个val元素，移除掉就没有了，所以需要清理map
        if (map.get(val).size() == 0) {
            map.remove(val);
        }
        //删除list最后一个元素（其实就是val)
        list.remove(list.size() - 1);
        return true;
    }
    //随机获取
    public int getRandom() {
        return list.get((int) (Math.random() * list.size()));
    }
}

380. O(1) 时间插入、删除和获取随机元素（mid）

class RandomizedSet {
    //可变数组+哈希表
    private List<Integer> list;
    private Map<Integer,Integer> index;
    public RandomizedSet() {
        list = new ArrayList<>();
        index = new HashMap<>();
    }
    public boolean insert(int val) {
        if (index.containsKey(val))return false;
        list.add(val);
        index.put(val,list.size()-1);
        return true;
    }
    //每次remove一个数与交换最后一个元素，然后移除最后一个元素
    public boolean remove(int val) {
        if (!index.containsKey(val))return false;
        int removeIndex = index.get(val);
        int last = list.get(list.size() - 1);
        list.set(removeIndex,last);
        index.put(last,removeIndex);
        list.remove(list.size()-1);
        index.remove(val);
        return true;
    }
    public int getRandom() {
        return list.get((int) (Math.random()*list.size()));
    }
}

相关资料