Collection（容器選擇）

# LC 791. Custom Sort String
# ...
s_map = Counter(s)
res = ""
for o in order:
    if o in s_map:
        res += (o * s_map[o])
        del s_map[o]
for s in s_map:
    res += (s * s_map[s])
# ...

import collections
s = ['a','b','c','c']
c= collections.Counter(s)
print (c)
print (c.keys())
print (c.values())

# 451 Sort Characters By Frequency
import collections
s = ['a','b','c','c']
count = collections.Counter(s).most_common()
for item, freq in count:
    print (item, freq)   
#c 2
#a 1
#b 1

import collections
s = ['a','b','c','c']
count = collections.defaultdict(int)
for i in s:
    count[i] += 1 

print (count)
print (dict(count))

import collections
s=[('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
count = collections.defaultdict(list)
for k, v in s:
    count[k].append(v)

print (count)
print (count.keys())
print (count.values())
print(count.items())

# LC # 554 rick Wall
import collections
_counter = collections.Counter()

_counter  # -> Counter()

_counter.update([1])

_counter  # -> Counter({1: 1})

_counter.update([1])

_counter  # -> Counter({1: 2})

_counter.update([2])

_counter  # -> Counter({1: 2, 2: 1})

# LC 146 LRU Cache
# OrderedDict = hash map + doubly linked list (Java: LinkedHashMap)
# https://docs.python.org/3/library/collections.html#collections.OrderedDict
#
# popitem(last=True)        pop the newest (last=True, LIFO) or oldest (last=False, FIFO) pair
# move_to_end(key, last=True)  move key to the end (or the front with last=False); KeyError if absent
#
# A plain dict also keeps insertion order (Python 3.7+). OrderedDict is still the LRU tool:
# move_to_end and popitem(last=False) are O(1), and a plain dict has neither.

#----------------------------
# example 0
#----------------------------
from collections import OrderedDict
d = OrderedDict()
for k in "abcde":
    d[k] = k.upper()

for k, v in d.items():
    print(k, v)
# -> a A
#    b B
#    c C
#    d D
#    e E

#----------------------------
# example 1
#----------------------------
d = OrderedDict.fromkeys('abcde')

d  # -> OrderedDict({'a': None, 'b': None, 'c': None, 'd': None, 'e': None})

d.move_to_end('b')

"".join(d)  # -> 'acdeb'

d.move_to_end('b', last=False)

"".join(d)  # -> 'bacde'

#----------------------------
# example 2
#----------------------------
class LastUpdatedOrderedDict(OrderedDict):
    'Store items in the order the keys were last added'

    def __setitem__(self, key, value):
        super().__setitem__(key, value)
        self.move_to_end(key)

#----------------------------
# example 3
#----------------------------
from time import time

class TimeBoundedLRU:
    "LRU Cache that invalidates and refreshes old entries."

    def __init__(self, func, maxsize=128, maxage=30):
        self.cache = OrderedDict()      # { args : (timestamp, result)}
        self.func = func
        self.maxsize = maxsize
        self.maxage = maxage

    def __call__(self, *args):
        if args in self.cache:
            self.cache.move_to_end(args)
            timestamp, result = self.cache[args]
            if time() - timestamp <= self.maxage:
                return result
        result = self.func(*args)
        self.cache[args] = time(), result
        if len(self.cache) > self.maxsize:
            self.cache.popitem(last=False)   # evict the least recently used
        return result

# LC 791. Custom Sort String
# V0
# IDEA : COUNTER
from collections import Counter
class Solution(object):
    def customSortString(self, order, s):
        s_map = Counter(s)
        res = ""
        for o in order:
            if o in s_map:
                res += (o * s_map[o])
                del s_map[o]
        for s in s_map:
            res += s * s_map[s]
        return res

// java
// IDEA: Java counterparts of Counter / defaultdict / most_common / OrderedDict / bisect
import java.util.*;

public class CollectionOps {

    // 1) COUNT  == Counter(s)
    // time = O(N), space = O(K)   (K = distinct keys)
    public static Map<Character, Integer> count(String s) {
        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : s.toCharArray()) {
            cnt.merge(c, 1, Integer::sum);   // or cnt.put(c, cnt.getOrDefault(c, 0) + 1)
        }
        return cnt;
    }

    // 2) GROUP  == defaultdict(list)
    // time = O(N), space = O(N)
    public static Map<String, List<Integer>> group(String[] keys, int[] vals) {
        Map<String, List<Integer>> m = new HashMap<>();
        for (int i = 0; i < keys.length; i++) {
            m.computeIfAbsent(keys[i], k -> new ArrayList<>()).add(vals[i]);
        }
        return m;
    }

    // 3) MOST COMMON  == Counter(...).most_common(k)      // LC 692 Top K Frequent Words
    // time = O(N + K log K), space = O(K)
    public static List<String> topK(String[] words, int k) {
        Map<String, Integer> cnt = new HashMap<>();
        for (String w : words) cnt.merge(w, 1, Integer::sum);
        // min-heap of size k: LOWEST freq at the top; tie -> lexicographically LARGER pops first
        PriorityQueue<String> pq = new PriorityQueue<>(
            (a, b) -> cnt.get(a).equals(cnt.get(b)) ? b.compareTo(a) : Integer.compare(cnt.get(a), cnt.get(b)));
        for (String w : cnt.keySet()) {
            pq.offer(w);
            if (pq.size() > k) pq.poll();   // evict the worst -> heap never exceeds k
        }
        LinkedList<String> res = new LinkedList<>();
        while (!pq.isEmpty()) res.addFirst(pq.poll());   // heap pops worst-first -> push front
        return res;
    }

    // 4) ORDERED DICT  == OrderedDict                      // LC 146 LRU Cache
    // time = O(1) per get/put, space = O(capacity)
    static class LRUCache extends LinkedHashMap<Integer, Integer> {
        private final int cap;
        LRUCache(int cap) {
            super(cap, 0.75f, true);   // accessOrder = true -> get() moves the key to the end
            this.cap = cap;
        }
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > cap;       // auto-evict the least recently used
        }
    }

    // 5) FLOOR / CEILING  == bisect on a sorted list       // LC 699 / LC 218
    // time = O(log N) per query, space = O(N)
    public static String floorCeil(TreeMap<Integer, Integer> tm, int q) {
        return tm.floorKey(q) + " / " + tm.ceilingKey(q);   // greatest <= q / smallest >= q
    }
}

# python
# IDEA: the same 5 ops in Python (this is what the Java above mirrors)
import bisect, heapq
from collections import Counter, defaultdict, OrderedDict

# 1) COUNT
# time = O(N), space = O(K)
Counter("abcc")                       # Counter({'c': 2, 'a': 1, 'b': 1})

# 2) GROUP
# time = O(N), space = O(N)
g = defaultdict(list)
for k, v in [('yellow', 1), ('blue', 2), ('yellow', 3)]:
    g[k].append(v)                    # {'yellow': [1, 3], 'blue': [2]}

# 3) MOST COMMON : freq DESC, then lexicographically ASC     # LC 692
# time = O(N + K log K), space = O(K)
def top_k(words, k):
    cnt = Counter(words)
    return heapq.nsmallest(k, cnt.keys(), key=lambda w: (-cnt[w], w))

# 4) ORDERED DICT : LRU ops                                   # LC 146
# time = O(1) per op, space = O(capacity)
d = OrderedDict()
d[1] = 1; d[2] = 2
d.move_to_end(1)                      # "touch" key 1 -> most recent
d[3] = 3
d.popitem(last=False)                 # evict LEAST recent (key 2) -> keys are [1, 3]

# 5) FLOOR / CEILING on a sorted list (Python has no TreeMap) # LC 699 / LC 218
# time = O(log N) query, O(N) insert  (use sortedcontainers.SortedList for O(log N) insert)
keys, q = [10, 20, 30], 25
i = bisect.bisect_right(keys, q)
floor_ = keys[i - 1] if i else None            # 20
ceil_ = keys[i] if i < len(keys) else None     # 30