手写JSON序列化：字符串转义、递归容器与循环

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练只接受str/list/dict，dict键必须str；容器插入顺序保留，输出紧凑JSON。
• 有限嵌套、Unicode码点为合法文本；未定义的数值/null类型不擅自扩展，递归深度需限制。

解题路线

1. string用双引号包裹，转义quote/backslash和控制字符；// / / 短转义，其余<0x20用四位\u。不能直接str(dict)，那是Python语法不是JSON。
2. list递归值逗号拼接，dict逐键转义+冒号+递归值。active身份集只记录当前递归路径，检测环；共享但非循环子对象允许重复编码。
3. 以标准JSON解析器roundtrip验证，并对同输入与标准序列化输出比较。生产优先成熟库，手写练习必须覆盖空值容器、引号、反斜杠、控制字符和深层引用。

手动走一遍

{"a":["x","y"]}编码结构保持，字符串内换行输出\n而非真实控制换行。x=[];x.append(x)不存在有限树形JSON，拒绝；[shared,shared]无环可重复输出。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def serialize(value):
    active=set()
    def string(text):
        result=['"']
        short={'"':'\\"','\\':'\\\\','\b':'\\b','\f':'\\f','\n':'\\n','\r':'\\r','\t':'\\t'}
        for char in text:
            if char in short:result.append(short[char])
            elif ord(char)<32:result.append('\\u%04x'%ord(char))
            else:result.append(char)
        result.append('"');return ''.join(result)
    def encode(obj):
        if type(obj) is str:return string(obj)
        if type(obj) not in (list,dict):raise ValueError("string/list/dict only")
        if id(obj) in active:raise ValueError("cycle")
        active.add(id(obj))
        try:
            if type(obj) is list:return '['+','.join(encode(x) for x in obj)+']'
            if any(type(k) is not str for k in obj):raise ValueError("string keys")
            return '{'+','.join(string(k)+':'+encode(v) for k,v in obj.items())+'}'
        finally:active.remove(id(obj))
    return encode(value)

复杂度

总输出L、深度h，分层字符串join可能反复复制使O(hL)保守时间，辅助O(h+L)；可写入流式buffer降低拷贝，仍有Ω(L)输出。

易错点与追问

容易失分的边界

• 只转义双引号而漏反斜杠会改变解析意义。
• 全局seen拒绝共享对象，会误当环。

继续深挖

• 若添加float，NaN/Infinity、−0与精度应怎样规定？
• 超过递归深度时如何改显式stack或限制输入？