动机
跟室友丁神聊完之后，感到了深深的peer pressure。又拾起了想去找个实习的想法。不管是找个AI4S的科研岗还是找个大厂做算法的业务岗，都是对自己经历和能力的一大步提升。
计划出去半年，发点论文也好，积累些工业界经验也好，总比在学校无所事事的好。想起高师兄说的，你要么早点毕业，要么出去交换或者找个实习，在学校就是浪费时间。当时觉得高师兄在装逼，现在想想高师兄真的太真诚了，装逼的只有当时傲慢的自己。
我得努力一点了，至少能让自己在毕业时多些选择。
行动计划
每天刷点leetcode，把算法基本功捡起来。开发的八股还有点印象，再学点大模型的八股，拥抱一下时代潮流。计划用四五个月的时间，让自己能有去参加面试的信心和能力。
- 每天至少做每日一题，写题解。
- 有多余时间就看看经典算法题和面试高频题目，从数据结构开始，链表，数组，树，图。再看算法，dp和backtrack，图算法，以及一些小tricks，很多都不用重新理解原理，所以这遍再学习要比研二看的更深一些，一些acm用的高阶算法，线段树之类的也要涉及到。
- 大模型八股。transformer，bert，llm，RLHF。
刷题赎罪
2025.6.18
- 每日一题
第一直觉就是模拟一下。先排序，然后贪心。
class Solution {
public:
vector<vector<int>> divideArray(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
for(int i = 0; i < n / 3; i++) {
int buf = i * 3;
if(nums[buf + 2] - nums[buf] > k) {
return {};
}
res.push_back({nums[buf], nums[buf + 1], nums[buf + 2]});
}
return res;
}
};- 链表
今天第一天给自己加餐。先看点链表的东西，做了反转链表相关的题目。
简单题，双指针。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};没啥说的，熟练背诵……
跟反转链表的思路一样，双指针。加点判断语句。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
for(int i = 0; i < left - 1; i++) {
pre = pre->next;
}
ListNode* r = pre;
for(int i = 0; i < right - left + 1; i++) {
r = r->next;
}
ListNode* l = pre->next;
ListNode* cur = r->next;
pre->next = nullptr;
r->next = nullptr;
reverseList(l);
pre->next = r;
l->next = cur;
return dummy->next;
}
};2025.6.19
- 每日一题
跟昨天的每日一题长得好像啊，但是昨天的是K个一组，确定了必须划分的组数，今天是最少的组数，先写个暴力试一下。
class Solution {
public:
int partitionArray(vector<int>& nums, int k) {
sort(nums.negin(), nums.end());
int n = nums.size();
int res = 0;
for(int i = 0; i < n; ) {
int j = i + 1;
while(j < n && nums[j] - nums[i] <= k) {
j++;
}
res++;
i = j;
}
return res;
}
}时间复杂度来自于排序算法的$O(n \log n)$，空间复杂度$O(1)$，感觉是没啥好优化的。
- 链表
每日一题太简单了，做个难点的K个一组反转链表。
不管别的，先再默写一遍反转链表。应该是反转链表系列的基本模块。
ListNode* reserveList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}然后想k个一组反转链表是啥意思。好像双指针的思路可以用上。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
// 截取链表
while(cur) {
ListNode* right = pre;
for(int i = 0; i < k; i++) {
right = right->next;
if(! right) {
return dummy->next;
}
}
ListNode* next = right->next;
right->next = nullptr;
// 反转链表
pre->next = reverse(cur);
}
}
};一直到这里都很顺利，但是突然发现也需要反转后的子链表的尾部节点指向next接回去。于是稍作修改。
class Solution {
public:
pair<ListNode*, ListNode*> reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return {pre, head}; // 返回反转后的头和尾
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
// 截取链表
while(cur) {
ListNode* right = pre;
for(int i = 0; i < k; i++) {
right = right->next;
if(! right) {
return dummy->next;
}
}
ListNode* next = right->next;
right->next = nullptr;
// 反转链表
pair<ListNode*, ListNode*> res = reverseList(cur);
pre->next = res.first;
res.second->next = next;
pre = res.second;
cur = next;
}
return dummy->next;
}
};时间复杂度就是遍历的$O(n)$，空间复杂度$O(1)$。
总的来说是一道不特别难的困难题。
八股
手撕
BPE算法
BPE(byte pair encoding)算法是一种编码方式。解决了在语言模型训练过程中的编码问题。
