有代西滴

迎难而上，祝我好运。

Anagram (49)

• 给一个数组，将所有“由相同字母组合而成的字符串”group起来返回。
• group就要找共同点，这里就是各字母出现的个数，可以排序一下作为key，维护一个Map映射到对应的index，存到的List进去。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return ans;
        }
        
        Map<String, Integer> map = new HashMap<>();
        for (String str: strs) {
            char[] sChar = str.toCharArray();   // sort str
            Arrays.sort(sChar);             
            String newStr = new String(sChar);  // the key to get the index in ans
            if (map.containsKey(newStr)) {
                int index = map.get(newStr);
                ans.get(index).add(str);
            } else {
                map.put(newStr, ans.size());
                List<String> temp = new ArrayList<>();
                temp.add(str);
                ans.add(temp);
            }
        }
        
        return ans;
    }
}

Least Frequently Used 460

• 实现最近最频繁使用的有限容量缓存，到达容量上限时evict最不频繁使用的key，若频繁情况相同则evict掉最早插入的。
• 方法一：优先队列，自定义Cache类，其中包含freq和timestamp，自定义Comparator来维护顺序。cacheMap用于维护正常的键值对缓存，freqMap用于快速获得给定key的freq。

class LFUCache {
    // naive做法：通过自定义Cache维护一个优先队列，排序就是根据freq和timestamp来的，freq小在前、相等则时间戳小的在前
    // put：把键值对放入cacheMap，还要新建这个key的freq（第一次为1）并插入freqMap
    // get: 直接从cacheMap中拿
    // 在put和get过程中，若key是现有的，则需要更新freq，并存入pq
    // 当到达容量上限，直接从pq头部poll出来的key对应从map里删掉即可
    // pq的remove是O(N)的，所以总体是O(capacity)的
    class Cache {
        int key, freq, timestamp;
        public Cache(int key, int freq, int timestamp) {
            this.key = key;
            this.freq = freq;
            this.timestamp = timestamp;
        }
        @Override
        public boolean equals(Object obj) {
            return key == ((Cache)(obj)).key;
        }
        @Override
        public int hashCode() {
            return key;
        }
    }
    
    int capacity, globalTime;
    Map<Integer, Integer> cacheMap = null;
    Map<Integer, Integer> freqMap = null;
    PriorityQueue<Cache> pq = null;
    public LFUCache(int capacity) {
        this.capacity = capacity;
        globalTime = 0;
        cacheMap = new HashMap<>();
        freqMap = new HashMap<>();
        pq = new PriorityQueue<>((c1, c2) -> {
            return c1.freq == c2.freq? c1.timestamp - c2.timestamp: c1.freq - c2.freq;
        });
    }
    
    public int get(int key) {
        globalTime++;
        if (cacheMap.containsKey(key)) {
            update(key);
            return cacheMap.get(key);
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return ;
        }
        globalTime++;
        if (cacheMap.containsKey(key)) {
            update(key);
            cacheMap.put(key, value);
            return;
        }
        if (cacheMap.size() == capacity) {
            Cache evict = pq.poll();
            cacheMap.remove(evict.key);
            freqMap.remove(evict.key);
        }
        cacheMap.put(key, value);
        freqMap.put(key, 1);
        pq.add(new Cache(key, 1, globalTime));
    }
    
    public void update(int key) {
        int freq = freqMap.get(key);
        freqMap.put(key, freq + 1);
        Cache c = new Cache(key, freq + 1, globalTime);
        pq.remove(c);
        pq.add(c);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

• 方法二：使用LRU中的双向链表，可以使得remove也O(1)。自定义Node，每个位置的Node代表了某个freq值的所有key。

class LFUCache {
    // 自定义双向链表节点Node用于按照freq从大到小存放key
    // 通过key对应到Node（nodeMap），Node中存放该key的freq。
    // 若相同的freq对应多个key，则用一个Set存放，为了维持Recent特性，需要保证插入顺序，故用LinkedHashSet
    // get：从cacheMap中正常取数值，并从nodeMap中拿到这个节点，更新freq并插入到后续位置。
    // put：有可能是更新原有key的数值，更新cacheMap中value。
    // put：若是插入新的key，则先看看head是否维护的是freq为0，不是则新建head并插入到最前。
    // put完之后要统一更新freq.
    class Node {
        public int freq = 0;
        public Set<Integer> keySet = null;
        public Node prev = null, next = null;
        public Node(int freq) {
            this.freq = freq;
            keySet = new LinkedHashSet<>();
            prev = null;
            next = null;
        }
    }
    private Node head = null;
    private int capacity = 0;
    private Map<Integer, Integer> cacheMap = null;
    private Map<Integer, Node> nodeMap = null;
    public LFUCache(int capacity) {
        this.capacity = capacity;
        cacheMap = new HashMap<>();
        nodeMap = new HashMap<>();
    }
    
    public int get(int key) {
        if (cacheMap.containsKey(key)) {
            updateFreq(key);
            return cacheMap.get(key);
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (cacheMap.containsKey(key)) {
            cacheMap.put(key, value);
        } else {
            if (cacheMap.size() < capacity) {
                cacheMap.put(key, value);
            } else {
                deleteOldest();
                cacheMap.put(key, value);
            }
            addToHead(key);
        }
        updateFreq(key);
    }
    
    // 更新key的freq并加入相应的node中
    private void updateFreq(int key) {
        Node node = nodeMap.get(key);
        node.keySet.remove(key);  // 从当前freq的node中移除然后加入后续node
        
        if (node.next == null) {
            node.next = new Node(node.freq + 1);
            node.next.prev = node;
            node.next.keySet.add(key);    // 相同freq的key，维持插入顺序
        } else if (node.next.freq == node.freq + 1) {
            node.next.keySet.add(key);
        } else {
            Node newFreqNode = new Node(node.freq + 1);
            newFreqNode.keySet.add(key);
            newFreqNode.prev = node;
            newFreqNode.next = node.next;
            node.next.prev = newFreqNode;
            node.next = newFreqNode;
        }
        nodeMap.put(key, node.next);   // 更新后续node
        if (node.keySet.size() == 0) {
            deleteNode(node);
        }
    }
    
    // O(1)删除双向链表的节点
    private void deleteNode(Node node) {
        if (node.prev == null) {
            head = node.next;
        } else {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
    }
    
    // 新插入的key要新建freq=0的Node（或原本就有），并作为head
    private void addToHead(int key) {
        if (head == null) {
            head = new Node(0);
            head.keySet.add(key);
        } else if (head.freq > 0) {
            Node newHead = new Node(0);
            newHead.keySet.add(key);
            newHead.next = head;
            head.prev = newHead;
            head = newHead;
        } else {
            head.keySet.add(key);
        }
        nodeMap.put(key, head);
    }
    
    private void deleteOldest() {   // 双向链表头就是freq最小的key们
        if (head == null) {
            return;
        }
        Iterator it = head.keySet.iterator(); // keys中靠前的就是较早插入的
        Integer oldestKey = null;
        if (it.hasNext()) {
            oldestKey = (Integer)it.next();
            head.keySet.remove(oldestKey);
        }
        if (head.keySet.size() == 0) {
            deleteNode(head);
        }
        if (oldestKey != null) {
            cacheMap.remove(oldestKey);
            nodeMap.remove(oldestKey);
        }
    }
}

求平均时间

• 给一堆GET request，其中包含时间信息，求这些请求的平均时间。比如

GET /course/html5-game-development--cs255 200 [72.80 27.47 28.51] 86.231.22.202 2017-04-07T18:02:35+00:00 {"id": "html5-game-development--cs255"}
GET /public-api/v1/degrees/nd803 200 [83.31 32.66 25.50] 160.153.51.93 2017-04-07T18:02:35+00:00 {"format": "json", "key": "nd803"}
GET /course/android-development-for-beginners--ud837 200 [68.02 29.44 21.22] 205.102.123.51 2017-04-07T18:02:36+00:00 {"id": "android-development-for-beginners--ud837"}
GET /ai 302 [32.47 21.71 4.39] 209.151.195.193 2017-04-07T18:02:37+00:00 {"id": "ai"}
GET /course/artificial-intelligence-nanodegree--nd889 200 [52.65 41.78 4.50] 209.151.195.193 2017-04-07T18:02:37+00:00 {"id": "artificial-intelligence-nanodegree--nd889"}

• 它们都格式都是固定的，通过split提取出时间，然后从Date转换成long，求平均值，最后再new一个Date即得。

public static String getAvgTime(String[] requests) {
    if (requests == null || requests.length == 0) {
        return null;
    }
    long timeVal = 0;
    SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd'T'HH:mm:ss");
    format.setTimeZone(TimeZone.getTimeZone("UTC"));
    for (int i = 0; i < requests.length; i++) {
        String[] requestParts = requests[i].split(" ");
        long currVal = 0;
        try {
            currVal = format.parse(requestParts[7]).getTime();
        } catch (ParseException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        if (i > 0) {
            timeVal = (long)(timeVal / 2.0 + currVal / 2.0);
        } else {
            timeVal = currVal;
        }
    }
    Date avgTime = new Date(timeVal);
    return avgTime.toString();
}