秋招日记

小结

日记

7月15日

算法

试图搞定今天的每日一题721. 账户合并，但并没有研究明白怎么做，看一眼提示才发现是并查集，算法课上学的忘干净了。

并查集：一种树形的数据结构，用于处理一些不交集的集合的合并及查询问题。并查集支持两种操作：

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一个子集。
• Union：将两个子集合并成同一个集合。

在这道题中，我们可以使用并查集来维护每个邮箱属于哪个账户。对于每个账户，我们将该账户的第一个邮箱作为“代表”邮箱，然后遍历该账户的所有邮箱，将其与代表邮箱进行合并。

代码好长，学不明白。收录一个并查集的板子（只带路径压缩）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class UnionFind {
public:
    vector<int> p;

    UnionFind(int n) {
        p.resize(n);
        for (int i = 0; i < n; i++){
            p[i] = i;
        }
    }

    void unite(int idx_1, int idx_2) {
        p[find(idx_2)] = find(idx_1);
    }

    int find(int idx) {
        return p[idx] == idx ? idx : p[idx] = find(p[idx]);
    }
};

做了两道贪心（也算是一维动态规划）的题目，55. 跳跃游戏和45. 跳跃游戏 II，第一道题是判断能否到达最后一个位置，第二道题是求到达最后一个位置的最小步数。第二道题本来的思路就是定义一个dp[i]表示从第i个位置到达最后一个位置的最小步数，使用memo数组进行记忆化搜索，但是超时了，看了一下题解，发现可以使用贪心算法，每次选择能跳的最远的位置，这样就能保证最小步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int end = 0, far = 0;
        int jumps = 0;

        for (int i = 0; i < n - 1; i++) {
            // 更新“可以”到达的最远距离
            far = max(i + nums[i], far);
            // 走到end标记位置时更新
            if (i == end) {
                jumps++;
                // 下一个跳转的end标记就是far的位置
                end = far;
            }
        }

        return jumps;
    }
};

八股

今天八股看网络，小林Coding网络部分的基础篇。

在网络分层的问题中，有一点以前没有注意过，就是“应用层工作在操作系统中的用户态，传输层及以下则工作在内核态”。

语言

摸鱼

今天先看了一点推荐系统的内容，包括这个仓库solidglue/Recommender_System，第一部分是王树森的推荐系统公开课wangshusen/RecommenderSystem，但是还没仔细看。

顺便发现了一个仓库gorse，Go 实现的一个推荐系统，分布式架构（区分了Worker、Master、API Server），支持基于协同过滤的推荐算法，看起来适合学习。

关于 Dify，尝试将 Notion 导入到知识库中时，发现除了Embedding模型，还需要一个Reranker模型进行召回的综合排序（包括关键词召回和向量召回），关于Reranker模型目前常用的应该是cohere和Jina。

7月14日

算法

今天不求别的，只求把股票买卖研究明白。

这问题真那么难吗？
真难，写不明白。

感觉好像明白了一点，看看明天还能不能品出来吧。模板放在这里。

太占地方，删掉了。

八股

今天没看。

语言

研究了一下 Go（Gin）的参数绑定，自动参数绑定使用反射还是比较多，也可以利用Go的元编程特性，自动生成参数绑定的代码，但是这样会导致代码可读性下降。大概搜到这几篇文章看看：

Gin 本身ShoundBind算是有 Go 策略模式的实现，择日细学。

摸鱼

Bravo 还没开始，学了一点Next.js和PWA，SSR 组件还是很难直接上手，需要系统学一遍Next。

Template

算法

八股

语言

摸鱼