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
In [87]: _counter = collections.Counter()

In [88]: _counter
Out[88]: Counter()

In [89]: _counter.update([1])

In [90]: _counter
Out[90]: Counter({1: 1})

In [91]: _counter.update([1])

In [92]: _counter
Out[92]: Counter({1: 2})

In [93]: _counter.update([2])

In [94]: _counter
Out[94]: Counter({1: 2, 2: 1})

# LC 146 LRU Cache

# There is a structure called ordered dictionary, it combines behind both hashmap and linked list. In Python this structure is called OrderedDict and in Java LinkedHashMap.

# https://docs.python.org/3/library/collections.html#collections.OrderedDict
# https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/367557/
# https://www.w3help.cc/a/202107/420653.html

"""

# OrderedDict = hashmap + linked list
# CAN make dict ordering (default dict is NOT ordering)
# Return an instance of a dict subclass that has methods specialized for rearranging dictionary order

* popitem(last=True)
    The popitem() method for ordered dictionaries returns and removes a (key, value) pair. The pairs are returned in LIFO order if last is true or FIFO order if false.

* move_to_end(key, last=True)
    Move an existing key to either end of an ordered dictionary. The item is moved to the right end if last is true (the default) or to the beginning if last is false. Raises KeyError if the key does not exist:

"""

#----------------------------
# example 0
#----------------------------

# default dict
In [34]: d = {}
    ...: d['a'] = 'A'
    ...: d['b'] = 'B'
    ...: d['c'] = 'C'
    ...: d['d'] = 'D'
    ...: d['e'] = 'E'
    ...:
    ...: for k, v in d.items():
    ...:     print (k, v)
    ...:
# NON ordering
a A
b B
c C
d D
e E

# OrderedDict
In [35]: from collections import OrderedDict
    ...: d = OrderedDict()
    ...: d['a'] = 'A'
    ...: d['b'] = 'B'
    ...: d['c'] = 'C'
    ...: d['d'] = 'D'
    ...: d['e'] = 'E'
    ...:
    ...: for k, v in d.items():
    ...:     print (k, v)
    ...:

# ordering !!!
a A
b B
c C
d D
e E


#----------------------------
# example 1
#----------------------------
In [28]:  d = OrderedDict.fromkeys('abcde')

In [29]: d
Out[29]: OrderedDict([('a', None), ('b', None), ('c', None), ('d', None), ('e', None)])

In [30]: d.move_to_end('b')

In [31]: "".join(d)
Out[31]: 'acdeb'

In [32]:

In [32]: d.move_to_end('b', last=False)

In [33]: "".join(d)
Out[33]: '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(0)
        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) : 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