数据结构 - 设计数据结构 - 《数据结构与算法》

146. LRU 缓存机制">双向链表 + hashMap146. LRU 缓存机制
284. 顶端迭代器">利用缓存cache思想实现精妙的284. 顶端迭代器
58. 把数组排成最小的数 ">定义特殊的排序规则58. 把数组排成最小的数
341. 扁平化嵌套列表迭代器">递归/非递归341. 扁平化嵌套列表迭代器
任务调度器">分类讨论任务调度器

双向链表 + hashMap146. LRU 缓存机制

使用双链表，每次使用了一个节点，就把这个节点放到链表的头部。如果超出空间，就删除链表的尾节点

建立一个哈希表，存放key ，value ：存放数据链表节点

每次put ：

如果有值，插入hashMap中，并把链表对应值的节点删除，插入到链表的头部
如果没值，插入hashMap中，插入到链表的头部
如果满了，删除尾部节点，通过节点得到key，从hashMap中删除key映射

get：

通过key到hashMap中取节点，把链表对应值的节点删除，插入到链表的头部，返回节点值

class LRUCache {
    class Node{
        int value, key;
        Node next, prev;
        Node(int key, int value){this.key = key; this.value = value; next = null; prev = null;}
    }
    int capacity;
    Node L, R;
    HashMap<Integer, Node> hash = new HashMap<Integer, Node>();
    public void remove(Node p){
        p.prev.next = p.next;
        p.next.prev = p.prev;
    }
    public void addFirst(Node p){
        L.next.prev = p;
        p.next = L.next;
        L.next = p;
        p.prev = L;
    }
    public LRUCache(int capacity) {
        L = new Node(-1, -1);
        R = new Node(-1, -1);
        L.next = R; R.prev = L;
        this.capacity = capacity;
    }
    public int get(int key) {
        if (!hash.containsKey(key)) return -1;
        Node tmp = hash.get(key);  
        remove(tmp);
        addFirst(tmp);
        //System.out.println("get: "+ L.next.key + " " +  R.prev.prev.key+ " " + R.prev.key);
        return tmp.value;
    }
    public void put(int key, int value) {
        if (hash.containsKey(key)){
            Node tmp = hash.get(key);
            tmp.value = value;
            remove(tmp);
            addFirst(tmp);
        }else{
            if (hash.size() >= capacity){
                //注意这里!!!! 一定是要有一个引用指向R.prev， 否则删除R.prev之后，下次再用R.prev就是R.prev.prev了！！！
                Node deleteNode = R.prev;
                remove(deleteNode);
                hash.remove(deleteNode.key);
            }
            Node nodeNew = new Node(key, value);
            addFirst(nodeNew);
            hash.put(key, nodeNew);
           // System.out.println("put"+ key + ": "+ L.next.key + " " + R.prev.prev.key+ " " +  R.prev.key);
        }
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

使用LinkedHashMap

class LRUCache extends LinkedHashMap<Integer, Integer>{
    int limit;
    public LRUCache(int capacity) {
        super(capacity,0.75f,true);
        this.limit = capacity;
    }
    public int get(int key) {
        if (super.containsKey(key))
            return super.get(key);
        return -1;
    }
    public void put(int key, int value) {
        super.put(key, value);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){
        return this.size() > limit;
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

利用缓存cache思想实现精妙的284. 顶端迭代器

注意：这里的PeekingIterator和Java中的iterator定义不一样

java: iterator.next() 移动，返回下一值

PeekingIterator.next() 移动，返回当前值

因此造成hasnext结果也会不一样

针对这些不同，我们建立一个缓存空间cache 和 has_next 判断cache后面有没有元素

PeekingIterator.next()就代表先看这个cache，再调用iterator.next()向后移动（把后一个元素放到cache中）

PeekingIterator.hasnext()：判断cache后面有没有元素，直接return has_next

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iterator;
    Integer cache;
    boolean has_next;
    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        this.iterator = iterator;
        if (has_next = iterator.hasNext()) cache = iterator.next();
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return cache;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer tmp = cache;
        if (has_next = iterator.hasNext()) cache = iterator.next();
        return tmp;
    }

    @Override
    public boolean hasNext() {
        return has_next;
    }
}

定义特殊的排序规则58. 把数组排成最小的数

定义一个排序规则：a < b 当且仅当 “ab” < “ba”

"ab" < "ba" 可以使用字符串哈希来比较相对大小。

使用反证法可以证明该规则的正确性。

将传入的数组进行对应的排序规则排序。

定义res字符串保存最小的数。

最后转换成数字。

class Solution {
    public String printMinNumber(int[] nums) {

        //装箱
        List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
        Collections.sort(list, new Comparator<Integer>(){
            public int compare(Integer a1, Integer b1){
                String a = a1 + "" + b1, b = b1 + "" + a1;
                return a.compareTo(b);
            }
        } );

        String res = "";
        for (int i = 0; i < list.size(); i ++){
            res += String.valueOf(list.get(i));
        }
        return res;
    }
}

递归/非递归341. 扁平化嵌套列表迭代器

递归：使用深搜把列表中的所有数顺序加入到一个list中，再顺序地进行遍历。

非递归：使用栈动态地把深搜顺序模拟起来。（递归在os地存储也是栈实现的）

分类讨论任务调度器

如果注释无法理解:可以结合题解来看参考

class Solution {
    public int leastInterval(char[] tasks, int n) {
/**
把出现次数最多的字母记为A,最多次数记为maxCount
如果出现了k个字母种类,BCD...
    当n>k&&字母maxCount相同: 最短时间需要(maxCount-1)*(n+1)+k(此时每一个字母和上一个字母的间距=n) 
        AB _ _ _ _ _ _ 
        AB _ _ _ _ _ _ 
        AB _ _ _ _ _ _ 
        AB _ _ _ _ _ _ 
        AB
    当n>k&&只有num个maxCount相同: 最短时间需要(maxCount-1)*(n+1)+k 
        可能会存在空位
        反向从最后一列向前排字母,(此时每一个字母和上一个同类字母的间距>=n),其他种类字母都可以放入空位中
        AB _ _ _ E D C 
        AB _ _ _ E D C 
        AB _ _ _ _ E C 
        AB _ _ _ _ E D 
        AB
    当n<k, 如果空位能放下，答案：(maxCount-1)*(n+1)+k；
        放不下，扩展列成k，此时CPU冷却只有n,因此填充列后，如果多余列有空位是可以除去的。 答案：task.size 
        最终为了保证能够满足这两种情况：MAX(tasks.size(),(maxCount-1)*(n+1)+k)
        AB C D E F G H I J
        AB C D E F G _ I J 
        AB C D E F G _ I J
        AB C D E _ _ _ I J
        AB

总结: 统计出现次数最多的次数maxCount的字母个数cnt,有mc行,把这些字母摆完,看剩余字母k-k'需要多少空位,如果不足,就扩展列.
让空位尽可能被任务占据
*/
        int maxc = 0, cnt = 0, m = tasks.length;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i ++){
            char c = tasks[i];
            map.put(c, map.getOrDefault(c, 0) + 1);
            maxc = Math.max(maxc, map.get(c));
        }
        for (Character key:map.keySet()){
            if (map.get(key) == maxc) cnt++;
        }
        return Math.max(m, (maxc - 1) * (n + 1) + cnt);
    }
}

设计数据结构

双向链表 + hashMap146. LRU 缓存机制

利用缓存cache思想实现精妙的284. 顶端迭代器

定义特殊的排序规则58. 把数组排成最小的数

递归/非递归341. 扁平化嵌套列表迭代器

分类讨论 任务调度器

分类讨论任务调度器