有代西滴

Posted on | Edited on | In | | Views:
Symbols count in article: 10k | Reading time ≈ 11 mins.

迎难而上，祝我好运。

Anagram (49)

  • 给一个数组，将所有“由相同字母组合而成的字符串”group起来返回。
  • group就要找共同点，这里就是各字母出现的个数，可以排序一下作为key，维护一个Map映射到对应的index，存到的List进去。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    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。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    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。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    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，其中包含时间信息，求这些请求的平均时间。比如

    1
    2
    3
    4
    5
    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即得。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    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();
    }