ランレングス圧縮
(String/run_length_encoding.py)

• View this file on GitHub
• Last update: 2021-01-28 20:42:36+09:00

使い方

encoding(s: Sequence[Any]) -> List[Tuple[Any, int]]
s 中の連続した同じ要素をまとめて (要素, 連続した回数) のタプルに変換した結果を返す。n = len(s) としたとき、計算量 $O(n)$

Verified with

• TestCase/unittest/run_length_encoding.unittest.test.py

Code

def encoding(s):
    n = len(s)
    begin, cnt = 0, 0
    ans = []
    if n == 0:
        return ans
    for end in range(n + 1):
        if end == n or s[begin] != s[end]:
            ans.append((s[begin], cnt))
            begin, cnt = end, 1
        else:
            cnt += 1
    return ans

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page