Task 1 user

Cs, Go!

||最后更新: 2025-8-17|

1.1 - User Password

1️⃣
#简单理解 🛠️更新日期 2025年8月5日
查看思路

确认数据结构

💭
首先我们想到的是需要储存用户曾经使用过的密码，所以我们需其中一种数据结构。
而这个数据结构需要让我们可以
  • 添加新的元素
  • 遍历所有现有元素进行比对（用与检查密码是否已经存在）
  • 满足可以储存51个元素的需求

对现有数据结构进行对比

  • ✅ array_set - array set 满足需求
  • ✅ array_sorted_list - array sorted list 满足需求
  • ❌ array_stack - array stack 无法让我们简单的查询所有现有的元素
  • ❌ bit_vector_set - bit vector set 无法让我们简单的查询所有现有的元素
  • ❌ circular_queue - circular queue 无法让我们简单的查询所有现有的元素
  • ❌ linked_list - linked list 无法让我们简单的查询所有现有的元素
  • ❌ node - node（二元树）无法让我们简单的查询所有现有的元素
  • ❌ referential_array - referential array（指针数组）无法让我们简单的查询所有现有的元素

Array set 🆚 Array sorted list

搜索复杂度
Array set 的搜索复杂度在这情况为
Array sorted list 的搜索复杂度为 或者
String 的 comp 在本单元中 为 1
添加复杂度
Array set 的添加复杂度为
Array sorted list 的添加复杂度为 或者
结论
在worst case中，两者一样，
在best case中，后者略胜一筹
所以 Array sorted list 胜出

代码部分

  1. 导入我们需要使用的数据类型
  1. 在 __init__ 中创建出 SortedList
  1. 逻辑判断 伪代码
更新内容
2025年8月5日
更改了数据结构 Array set →Array Sorted List
  • Best case 的时间复杂度从 →
修改了Array Sorted List 的容量 50 → 51
  • 符合题目要求不再报错，感谢林同学！！
 

1.2 - Posting TipTops

任务概览

展开详情
  1. TipTop 数据结构 🗂️
    1. 第一维 ➡️ 表示行 (rows)
    2. 第二维 ➡️ 表示列 (columns)
    3. 第三维 ➡️ 单个像素数据，每个像素包含三个整数 (RGB)
  1. 发布前的修改 🎨
      • 如果像素的 第三个数（蓝色分量 blue component） > 200，则将其降低到 200
      • 对图像分别进行水平与垂直方向的翻转，以获得其关于中心的对称版本 (从后往前读）
  1. 时间复杂度要求 ⏱️
      • 方法的时间复杂度 ≤ O(P)，其中 P 为 TipTop 的像素数量
  1. 发布操作 🚀
      • 修改完成后，调用 remote_server 的 post_tiptop 函数发布
  1. 默认假设 📝
      • 调用 remote_server.post_tiptop 函数的时间复杂度为 O(1)
1️⃣
匿名版 #巧妙解题
查看思路

🧠 思路分析

  • 只遍历 一半的像素对（与其中心对称像素成对处理）
  • 对每一对像素：
    • 限制蓝色分量 ≤ 200
    • 交换两个像素位置
  • 时间复杂度应 ≤ O(P) (P = 像素总数)

⌛ 时间复杂度分析

  • 遍历次数：一半像素数 → O(P/2)
  • 常数操作：蓝色分量检查 + 交换像素 → O(1)
  • 总体复杂度：O(P/2) + O(1) ≈ O(P)
 
 

1.3 - User Previews

1️⃣
#简单理解 🛠️更新日期 2025年8月13日
查看思路
💭
由于我们不需要（而且不能）保存旧的Tiptop，所以我们可以不断去迭代我们的显示列表。
在函数被调用时候：如果 当前显示的数量小于最大限制则直接返回，否则返回 前最大限制 个文章。

数据结构

我们的发布文章采用 LinkedList数据结构，有点在于我们可以进行头添加，以及无长度限制。类似于python list 里的 insert(0, “新的post”)
这样做的好处是最新的照片永远在第0位，以及每当我们发布了一个新的照片，旧照片的位子就会往后位移一位。而我们值需要往后数N位就好了，而N则是我们的推荐文章数量（满足上述要求，且最小为1）。
💭
由于创建一个新列表，往列表里添加内容时间复杂度都是O(1)，删除现有的反而成本高，所以我们一律创建新的列表。
🖊️
来着Tim的精简概括 （用英语更加准确一点）
create A linked list put X amount of tiptops in A linked list from B linked list replace B linked list with A linked list return A linked list
伪代码
更新内容
2025年8月13日
增加了 Tim 的概括
2025年8月12日
修改了错别字 保存旧的
修复了为代码中的错误 ArraySet → LinkedList
2025年8月5日
修改了判断条件
  • Best case 的时间复杂度从 →
新增了迭代覆盖
  • 满足了ED 上老师指出的要求 - 不保存旧的Tiptop （ 题目写的是真太含蓄了）
      • notion image
 

1.4 - Generating Feeds (1054 Only)

⚠️
1.4 有些耗费时间，建议 1054 的同学（或者是 1008 想要尝试的同学）先把 1008 & 1054 共同部分写完～
1️⃣
匿名版 #有难度 🛠️更新日期 2025年8月13日
查看思路

题意要求：

任务背景

之前所有的方法仅关注用户自己发的 TipTops。
但我们还需要实现用户查看朋友动态的逻辑。
这个逻辑由 generate_feed 方法实现，
它将当前用户的朋友所发布的 TipTops 合并到一个时间线上。

输入

此方法接受一个参数：数组（array），数组的每个元素是一个链表（linked list）。
  • 每个链表包含某位朋友发布的 TipTops，按发布时间顺序排列。
  • 链表中每个元素是一个二元组 (timestamp, tiptop)：
    • timestamp 表示发布的时间（相对于程序启动后的秒数）
    • tiptop 表示 TipTop 的具体内容

输入示例

一个用户有 5 位朋友，其各自 TipTops 数据如下：
  • 一位朋友有 4 条 TipTop
  • 第二位朋友有 1 条
  • 第三位朋友有 3 条
  • 第四位朋友有 1 条
  • 第五位朋友没有发布过任何 TipTop
在这些时间戳中：
  • 最早的 TipTop 是第二位朋友的 T5
  • 最晚的 TipTop 是第三位朋友的 T6

目标

我们要为当前用户生成一个动态（feed）：
  • 使用一个链表表示
  • 按时间从最旧到最新排序（最小时间戳最先）
  • 限制动态中显示的 TipTops 数量（记为 X）

优先规则

  1. 确保所有朋友都有至少一条动态
      • 在动态生成过程中，优先确保每个有 TipTops 的朋友至少有一条内容出现在 feed 中。
      • 例外情况：如果某个朋友连续发布的 TipTops 时间间隔小于等于 3 秒，认为它们是关联内容（同一个故事）。
        • 这种情况下，即使已有一条 TipTop 被选中，该朋友仍然算作“还未贡献”，直到遇到一条时间间隔大于 3 秒的下一条。
  1. 所有朋友至少贡献一条后
      • 当所有有 TipTops 的朋友都在动态中出现至少一次后，
          • 不再考虑“优先让未贡献朋友入选”，而是直接根据时间戳顺序填充剩余的动态条目，直到达到 feed 容量上限 X。

动态容量

  • 初始容量 X = 1
  • 每次调用 generate_feed 后，X 翻倍
  • 如果没有足够的 TipTops 填充 feed，则只展示现有的 TipTops

算法步骤总结

  1. 初始化动态容量 X（初始为 1，每次调用后翻倍）
  1. 先保证每个朋友至少有一条 TipTop 出现在动态中
      • 如果一个朋友的多条 TipTop 时间差 ≤ 3 秒，视作同一故事，直到遇到时间差 > 3 秒的下一条，才算完成该朋友的贡献
  1. 在满足所有朋友“至少一次”贡献后，按时间顺序直接填充动态，直到达到容量上限 X
  1. 返回链表形式的动态

示例讲解

假设调用多次 generate_feed，仍使用上文输入（5 个朋友，TipTop 数量分别为 4、1、3、1、0）：

第一次调用

  • 动态容量 X = 1
  • 输出：T5（最早）
  • 容量翻倍 → X = 2

第二次调用

  • 动态容量 X = 2
  • 输出：T5 -> T1（T1 是下一个最早的）
  • 容量翻倍 → X = 4

第三次调用

  • 动态容量 X = 4
  • 输出：T5 -> T1 -> T2 -> T9
    • 已有朋友#1 的 TipTop (T1)，但 T2 与 T1 相差 ≤ 3 秒 → 仍未算作贡献完成 → 继续考虑该朋友
    • 由于 T2 仍然时间上最早，加入 T2
    • 接着选择朋友#4 的 T9（未贡献）
  • 容量翻倍 → X = 8

第四次调用

  • 动态容量 X = 8
  • 输出：T5 -> T1 -> T2 -> T9 -> T3 -> T6 -> T4 -> T7
    • 解释：
      • 先选朋友#1 的 T3（与 T2 相差 ≤ 3 秒，仍算同一故事）
      • 朋友#1 到此才算贡献完成（T4 已经时间差 > 3 秒）
      • 朋友#3 还没贡献 → 选 T6（相差 > 3 秒）
      • 所有有 TipTops 的朋友已贡献
      • 按时间顺序继续填充：T4 -> T7
  • 容量翻倍 → X = 16

假设条件

  • 每个链表内部的 TipTops 已按时间戳顺序排列（旧 → 新）
  • 不同用户的 TipTops 没有时间顺序关系（需合并排序）
  • 有些用户可能没有 TipTops（空链表）
  • 所有 TipTops 时间戳唯一（不会重复）
  • 可修改输入对象，或创建其副本处理

部分分说明

即使没有实现 3 秒规则，只要其余逻辑正确，也会给部分分数。

注意

❌  从例子来看，我们明智的决定是每 call 一次 method， 就储存一次结果，这样以后，对于同样的friends previews，调用相同方法时无需从头重新遍历。但是实际上不是这样的。想想是为什么？

代码部分：

⚠️
注意！
代码部分已完成～ 🎉 🎉 🎉
（时间复杂度可能会根据TA的提议进行优化）
 
Loading...