Task 1 user

1.1 - User Password

1️⃣
#简单理解
查看思路

确认数据结构

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

对现有数据结构进行对比

  • ✅ 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 → ，Array sorted list 的搜索复杂度为
所以 Array set 胜出
🖊️
通过挨个比对，得到的结果：Array set 的结构可以轻松的满足我们对数据结构的需求，且有更好的时间复杂度。

代码部分

  1. 导入我们需要使用的数据类型
  1. 在 __init__ 中创建出 ArraySet
  1. 逻辑判断 伪代码

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️⃣
Jason 版 #简单理解
查看思路
💭
时间复杂度要求 ，结合题目 思路是 使用for循环 从后往前遍历每个像素进行操作。
数据结构因为容量固定，且是3D数组所以使用array_set。
代码思路
  1. 获取图片的基本信息height 以及width
  1. 创建一个容量为height 的ArraySet
  1. 通过嵌套循环，反向遍历tiptop
  1. 处理像素点后添加新的一行
伪代码
 
2️⃣
匿名版 #巧妙解题
查看思路

🧠 思路分析

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

⌛ 时间复杂度分析

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

1.3 - User Previews

1️⃣
#简单理解
查看思路
💭
本题难点在于如何正确规划处推荐的文章数量，这里我将题目的要求换一个方法表达出来。
推荐文章的数量 应该是一下任意一个要求的一个最少值
  • 最大预览数 #每次增加1题目要求的最高限制
  • 现有文章数量 #无法推送超过现有的数量的文章
  • 上次文章的坐标(index) #推送文章不因该增加任何旧文章

数据结构

我们的发布文章采用 LinkedList数据结构，有点在于我们可以进行头添加，以及无长度限制。类似于python list 里的 insert(0, “新的post”)
这样做的好处是最新的照片永远在第0位，以及每当我们发布了一个新的照片，旧照片的位子就会往后位移一位。而我们值需要往后数N位就好了，而N则是我们的推荐文章数量（满足上述要求，且最小为1）。
伪代码
 

1.4 - Generating Feeds (1054 Only)

1️⃣
(代码部分未完！！)
查看思路

题意要求：

任务背景

之前所有的方法仅关注用户自己发的 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， 就储存一次结果。但是实际上不是这样的。想想是为什么？

代码部分：

⚠️
未完！未完！
缺少条件判断，大致思路基本正确。
请酌情参考。
📆 预计完成时间：Tue 5 Aug
 
目录