64 lines
2.0 KiB
Python
64 lines
2.0 KiB
Python
import random
|
|
|
|
import pytest
|
|
|
|
from patterns import (LRUCache, edit_distance, longest_unique_substring, lower_bound, merge_intervals,
|
|
shortest_path, top_k_frequent, topo_order, two_sum)
|
|
|
|
|
|
def test_two_sum():
|
|
assert two_sum([3, 3], 6) == (0, 1)
|
|
assert two_sum([1, 2], 10) is None
|
|
|
|
|
|
@pytest.mark.parametrize("s,n", [("", 0), ("bbbb", 1), ("pwwkew", 3), ("abba", 2), ("你好你们好", 3)])
|
|
def test_longest_unique(s, n):
|
|
assert longest_unique_substring(s) == n
|
|
|
|
|
|
def test_lower_bound_matches_bisect():
|
|
import bisect
|
|
rng = random.Random(0)
|
|
for _ in range(200): # 与标准库对拍
|
|
arr = sorted(rng.randint(0, 20) for _ in range(rng.randint(0, 15)))
|
|
t = rng.randint(-1, 21)
|
|
assert lower_bound(arr, t) == bisect.bisect_left(arr, t)
|
|
|
|
|
|
def test_top_k():
|
|
assert top_k_frequent([], 3) == []
|
|
assert top_k_frequent(list("aaabbc"), 1) == ["a"]
|
|
|
|
|
|
def test_shortest_path_blocked():
|
|
assert shortest_path([[0, 1], [1, 0]], (0, 0), (1, 1)) == -1
|
|
assert shortest_path([[0]], (0, 0), (0, 0)) == 0
|
|
|
|
|
|
def test_topo_cycle_and_order():
|
|
assert topo_order({"a": ["b"], "b": ["a"]}) is None
|
|
order = topo_order({"app": ["db", "cache"], "cache": ["net"], "db": ["net"]})
|
|
assert order is not None
|
|
pos = {n: i for i, n in enumerate(order)}
|
|
assert pos["net"] < pos["db"] < pos["app"] and pos["net"] < pos["cache"] < pos["app"]
|
|
|
|
|
|
def test_edit_distance():
|
|
assert edit_distance("", "abc") == 3
|
|
assert edit_distance("退货申请", "退款申请") == 1
|
|
|
|
|
|
def test_lru():
|
|
c = LRUCache(2)
|
|
c.put("a", 1)
|
|
c.put("b", 2)
|
|
assert c.get("a") == 1 # a 变成最近使用
|
|
c.put("c", 3) # 淘汰 b
|
|
assert c.get("b") is None and c.get("a") == 1 and c.get("c") == 3
|
|
|
|
|
|
def test_merge_intervals():
|
|
assert merge_intervals([]) == []
|
|
assert merge_intervals([(1, 4), (4, 5)]) == [(1, 5)]
|
|
assert merge_intervals([(5, 6), (1, 2)]) == [(1, 2), (5, 6)]
|