Task 2 - Processing Book

Cs, Go!

||最后更新: 2025-9-23|
 

Task 2.1 — The Book Structure

1️⃣
匿名同学 笔记（稍有难度，建议先画图手动推演再写代码）
题目理解

📌 简介

  • ProcessingBook 类似哈希表。
  • 键（key）：Transaction 对象（已签名）
  • 值（value）：交易金额
  • 每笔交易必须唯一存储，不能重复设定不同金额。

🧠 结构核心思想

🔢 签名（signature）说明

  • 签名是字符串，由小写字母（a–z）和数字（0–9）组成。
  • 每个字符有 36 种可能 → 账本有 36 个页面（pages）
  • 页面索引顺序：a, b, ..., z, 0, 1, ..., 9

✅ 插入规则

  • 使用签名第 i 位字符决定要插入的页。
  • 若该页为空 → 存入金额
  • 若该页已被占用：
    • 若为另一个 Transaction → 冲突：
      • 创建子账本（ProcessingBook）
      • 将冲突交易和新交易都转移进去
      • 在子账本中使用下一位字符继续处理（递归）
    • 若为子账本 → 递归调用 __setitem__

❌ 禁止行为

  • 若同一签名的交易已经存过一个值，不能设定不同的值。
  • 若值相同，可重复设置，不报错。
  • 读取不存在的交易 → 抛出 KeyError

🧩 你需要实现的方法

✅ __setitem__(transaction, amount)

  • 根据签名字符递归插入交易。
  • 若已存在但金额不同，记录错误。

✅ __getitem__(transaction)

  • 根据签名字符递归查找。
  • 若找不到 → 抛出 KeyError

✅ get_error_count()

  • 返回错误设置次数（即试图更新已有交易为不同金额的次数）。

⚠️ 约定和注意事项

  • 所有交易对象都有有效签名（你不需要手动签名）。
  • 所有交易签名长度一致。
  • 金额都是正整数。
  • 不允许假设签名长度最大值（和 Task 1 要分开考虑）。
  • 只能在 ProcessingBook 中存储一次交易金额。

🔁 冲突处理机制图解说明

场景
处理方式
两个签名首字符相同
在该页创建新 ProcessingBook
子账本中再次冲突
再次创建新 ProcessingBook
一直到字符不同为止
成功分配到不同页
题解思路

1. 核心目标

  • 将 Transaction 对象存储在递归哈希结构中。
  • 根据 交易签名 (signature) 的每个字符逐层分配到 pages（类似字典树 / trie 的思想）。
  • 支持插入 (__setitem__) 和查找 (__getitem__)，并在发生冲突时递归建立子表。
  • 检测错误：如果同一个签名对应的 amount 不一致，则记录在 _error_count 中。

2. 数据结构设计

  • ProcessingBook
    • pages：长度固定的 ArrayR，大小为 36（a–z, 0–9）。
    • _error_count：记录错误次数。
  • Somename（嵌套类）
    • someothername：一个长度为 2 的数组，存储 Transaction 和 amount。
    • sub_book：递归子表，发生冲突时创建。
    • contain_sub_book()：判断是否存在子表。

3. 插入逻辑 (__setitem__)

  1. 定位字符位置
      • 根据 transaction.signature[index] 找到对应的下标位置。
  1. 情况 A：该位置为空
      • 直接存放新的 Somename(transaction, amount)。
  1. 情况 B：该位置已有内容
      • 如果已有 子表 → 进入子表递归插入。
      • 如果没有子表：
        • 签名相同但金额不同 → 计入 _error_count。
        • 签名不同 → 创建子表，存放已有交易和新交易。
  1. 递归进行，直到找到合适位置。

4. 查找逻辑 (__getitem__)

  1. 从签名第一个字符开始查找 pages 对应位置。
  1. 如果存在子表 → 递归进入下一层。
  1. 如果是 Somename 且签名完全匹配 → 返回对应的金额。
  1. 如果不存在或不匹配 → 抛出 KeyError。
难点：1. 子表处理 2. 数据结构连贯性
2️⃣
Jason 笔记
查看思路
  • 账本类似哈希表，有 36 个「页面」（a–z, 0–9）。
  • 每个 Transaction 的 signature 决定它存放在哪一页：
    • 第 1 个字符 → 顶层页面。
    • 如果冲突（已有不同交易占位） → 创建子 ProcessingBook，在里面用第 2 个字符作为索引。
    • 再冲突 → 继续递归到第 3 个字符 … 直到分开。
  • 不能直接更新交易金额：
    • 如果同一签名再插入相同金额 → 安全忽略。
    • 如果金额不同 → 错误，记录一次 error。

核心思路

  • 用递归结构解决冲突：每一层账本只看签名的一个字符。
  • 插入时逐层进入，直到找到空位或必须新建子账本。
  • 查找时逐层进入，直到找到交易或确定不存在。
  • 维护一个全局 errors 计数器，每次试图「修改金额」时自增。

伪代码

  1. 插入 __setitem__
      • 输入：交易对象，金额 amount。
      • 找到签名第 depth 个字符，计算页索引。
      • 如果该页是空：放进去 (交易对象, amount)。
      • 如果该页已有一个 (交易对象2, amount2)：
        • 如果 交易对象2.signature == tx.signature：
          • 如果金额相同 → 忽略。
          • 如果金额不同 → errors += 1，不更新。
        • 否则：创建子 ProcessingBook，递归存储 交易对象2 和 交易对象。
      • 如果该页已有一个子 ProcessingBook：递归插入。
  1. 查找 __getitem__
      • 输入：交易对象 tx。
      • 找到签名第 depth 个字符，计算页索引。
      • 如果该页是空 → KeyError。
      • 如果是 (交易对象2, amount2) 且签名匹配 → 返回 amount2。
      • 如果是 ProcessingBook → 递归继续。
      • 否则 KeyError。
  1. 错误计数 (get_error_count)
      • 返回 self.errors。

Task 2.2 — Deleting

1️⃣
匿名同学笔记（稍有难度，建议先画图手动推演再写代码）
题目理解

📌 题目目标：

我们需要为 ProcessingBook 类实现一个删除功能 __delitem__，它可以：
  1. 从嵌套的哈希结构中删除一个指定的交易（Transaction）；
  1. 如果删除某个交易后，它所在的子书（sub book）中只剩下一个交易：
      • 那么该子书应当折叠回上一层，这个剩下的交易直接上浮，放回其父级页面中；
  1. 删除一个不存在的交易时，应抛出 KeyError；
  1. 整体逻辑为对 Task 2.1（添加时多层嵌套）的一种“反向处理”。

🔍 结构说明：

  • ProcessingBook 的 pages 是一个 ArrayR，其中的每个位置可以包含：
    • 一个 TransactionWrapper，其中是具体交易；
    • 或者一个嵌套的 sub_book（下一层 ProcessingBook）；
  • 因此，删除操作也要沿着 Transaction.signature 的字符路径，逐层进入正确的子书，直到找到目标交易；
  • 删除之后，若某一层子书只剩一个交易（其余为 None），就要将这个交易上浮，折叠掉该子书
解题思路

🧠 实现思路概述：

  1. 从顶层出发，递归向下查找目标交易的位置：
      • 根据交易的 signature 逐字符定位；
      • 每一层的字符决定进入哪个 page；
      • 若 page 中是子书，则继续进入下一层；
      • 若 page 中是交易，检查是否为目标交易。
  1. 在进入每一层之前，判断是否存在可折叠的情况：
      • 使用辅助函数判断：当前页面中是否除了目标位置以外还有其他内容（交易或子书）；
      • 如果没有，说明当前层结构已无必要存在，可标记为 need_collaps = True；
      • 同时记录当前层数，用于后续 collapse 操作。
  1. 找到目标交易后，执行删除操作：
      • 若不需要折叠，则直接将交易设为 None；
      • 若需要折叠，则将整个 page 设为 None，并调用 collaps 函数向上折叠结构。
  1. 折叠操作 collaps 的作用：
      • 定位到需要折叠的那一层的 ProcessingBook 对象；
      • 将其子书中唯一剩下的内容复制回当前页面中；
      • 相当于将嵌套层级减少一级，使结构更加紧凑。
  1. 异常处理：
      • 如果在任何层找不到目标交易，或路径上存在空位，应抛出 KeyError
2️⃣
Jason 笔记
查看思路
题目要求
  • 需要支持 del book[transaction] 删除交易。
  • 删除后要检查：
    • 如果子 ProcessingBook 变空 → 删除该子簿，父页设为 None。
    • 如果子 ProcessingBook 只剩 1 个交易 → 折叠，把这个唯一的交易移回父级。
  • 如果交易不存在 → 抛 KeyError。
  • 删除时要维护全局 __length 计数器，保证 __len__ O(1)。

核心思路

  • 删除和插入的逻辑正好相反：
    • 插入时：冲突 → 建子簿。
    • 删除时：冲突解除 → 折叠子簿。
  • 在每次删除时：
    • 如果删除成功，__length -= 1。
    • 如果删除导致子簿结构发生变化，要更新父级的页面指向。

伪代码

  1. 删除 __delitem__
      • 输入：交易对象 tx。
      • 找到签名第 depth 个字符 → 页索引。
      • 如果该页为空 → KeyError。
      • 如果该页是 (交易对象2, amount2)：
        • 如果签名相同 → 删除，父页设为 None，__length -= 1。
        • 否则 → KeyError。
      • 如果该页是子 ProcessingBook：
        • 递归删除。
        • 删除后检查子簿：
          • 如果子簿空 → 父页设为 None。
          • 如果子簿只剩 1 个交易 → 折叠，把唯一交易移回父级页。
  1. 折叠逻辑
      • 遍历子簿的 pages，找到唯一非空元素，直接提升到父级。

Task 2.3 — Iterating

2️⃣
Jason 笔记 🅰️ 版 → 依靠数据结构 #推荐
查看思路
题目要求
  • 需要支持 len(book) 返回账本中所有交易数量。
  • 需要支持 for tx, amt in book: 遍历所有交易。
  • 遍历时的顺序必须按照 LEGAL_CHARACTERS 的顺序（a–z → 0–9）。
  • 遍历结果是一个个二元组 (transaction, amount)。
  • 假设遍历过程中不会有新增/删除操作。

核心思路

  • __len__ 实现
    • 必须是 O(1)，不能在调用时去递归数。
    • 在插入时成功添加新交易 → __length += 1。
    • 在删除时成功删除交易 → __length -= 1。
    • 所以 __len__ 只需返回 self.__length。
  • 迭代器实现
    • __iter__：初始化一个栈或游标，返回迭代器对象。
    • __next__：使用深度优先遍历 (DFS) 的方式：
        1. 取出当前 (book, page_index)。
        1. 如果是 None → 跳过。
        1. 如果是 (transaction, amount) → 返回该二元组。
        1. 如果是子 ProcessingBook → 把它和索引放入栈，递归进入。
    • 每次只处理一个元素，所以 __next__ 是 O(1)。
    • 直到栈空，抛 StopIteration。

伪代码

迭代初始化 __iter__
  • 创建一个栈（或等价结构），保存「当前账本 + 页索引」。
  • 初始时，将 (self, 0) 压入栈。
  • 返回账本对象自身作为迭代器。
迭代步骤 __next__
  • 当栈非空：
    • 弹出栈顶 (当前账本, 当前索引)。
    • 如果索引超出 36 → 跳过。
    • 否则，把 (当前账本, 索引+1) 压回栈。
    • 查看该页：
      • 空 → 跳过。
      • 若为单个交易：返回 (交易, 金额)。
      • 若为子账本：把 (子账本, 0) 压入栈，继续循环。
  • 当栈为空：抛出 StopIteration。
2️⃣
Jason 笔记 🅱️ 版 → 依靠递归
查看思路
题目要求
  • 需要支持 len(book) 返回账本中所有交易数量。
  • 需要支持 for tx, amt in book: 遍历所有交易。
  • 遍历时的顺序必须按照 LEGAL_CHARACTERS 的顺序（a–z → 0–9）。
  • 遍历结果是一个个二元组 (transaction, amount)。
  • 假设遍历过程中不会有新增/删除操作。

核心思路

  1. 索引跟踪：用一个索引变量 track_index，从 0 遍历到 35，对应合法字符顺序。
  1. 递归展开：当某一页是子账本时，不一次性取出所有元素，而是把子账本转成迭代器，逐步交给它去产出元素。
  1. 状态保存：用一个变量 last_element 来记录当前是否正在遍历某个子账本：
      • 如果 last_element 还没结束 → 优先继续从里面取元素。
      • 如果子账本遍历结束 → 重置 last_element = None，然后继续向下扫描父账本的下一页。
  1. 终止条件：当索引扫描到最后（≥36）且没有子账本 → 抛出 StopIteration。

伪代码

迭代初始化（__iter__）
  • 设置一个索引变量 track_index = 0。
  • 设置一个变量 last_element = None，表示当前是否正在遍历子账本。
  • 返回当前对象作为迭代器。
迭代步骤（__next__）
  1. 检查是否在遍历子账本
      • 如果 last_element 是一个迭代器：
        • 尝试从中获取下一个元素。
        • 如果成功 → 返回这个元素。
        • 如果子账本遍历结束 → 把 last_element 设为 None，并让索引 +1。
  1. 循环检查当前账本的页面
      • 当 track_index 小于 36（合法字符总数）：
        • 取出当前页面。
        • 如果页面是一个 单个交易：
          • 索引 +1。
          • 返回该交易。
        • 如果页面是一个 子账本：
          • 把 last_element 设置为该子账本的迭代器。
          • 从子账本迭代器获取一个元素并返回。
        • 如果页面为空：
          • 索引 +1，继续循环。
  1. 结束条件
      • 如果所有页面都遍历完 (track_index >= 36) → 抛出 StopIteration。
 
Loading...