今天百度oc，一下子心里的大石头落地

晚上九点多就上床躺下居然一下子睡着，十二点多醒来后呆在了笔记本前，不知道该干点什么

刷了一会B站，打了两盘大乱斗都觉得倍加的无聊

一下子奋斗的目标没有了，虽然还有其他的面试，但是应该是不会去了

从20年开始在AcWing上刷算法，到现在两三年了

去年一整年都在刷题、背书、做项目、改简历、投简历、笔试面试，被拒，再投，再被拒，无限循环

整个2022年从新年伊始就是寒气逼人，实习停招，hc爆减，最终秋招也是寒意刺骨，职场哀鸿遍野，求职更是上天无门下地无路

整个实验室最终也只有一个字节（转正ssp大佬），一个TP（双九学历厂+7）和一个华为（23年1月才给的offer,很信华爱华选华的同门，不过14）

无奈之下草草签了一个研究所，2月新年刚结束就去单位匆匆报道了

结果研究所的生活实在是过于一成不变，2周最大的收获就是日均5杯白开水+免费咖啡，顺带把单位附近的外卖摸清楚

里面没有业绩压力，没有项目，没有日报，没有周报，每月一度的串讲也流于形式

谁刚来的时候不是满腔热血，想做点东西学点本事出来，可是无奈在大环境之下，只能是拔剑四顾心茫然

我不想就这样一直待下去直到彻底废掉

于是2月底开始投简历，3月初正式辞职毁约重新准备春招

一开始非常的不理想，boss打了100个招呼只有三十来个简历发送，面试机会更是寥寥无几，前5个进入流程的几乎都是简历复筛挂或者一面挂，整个人也非常的blue

尤其是寄予厚望的阿里补录刚好结束（阿里今年只有24招聘了，23春招没有），蚂蚁简历复筛失败，华为春招停止，更是极受打击

还好三月中开始各厂的春招逐渐开启，面试慢慢多了起来，平均每周10个左右的面试让人忙碌起来就少有胡思乱想

最初的面试其实很差，因为刚刚结束噩梦般的22年秋招以及北京严格的疫情管控，整个人在1，2两个月是完全摆烂似的度过，基础的mysql和os八股都答得磕磕绊绊，项目经历也忘得七七八八（美团一面thrift匹配系统架构没答出来）

基本上属于上一周的面试剩一小半留到下一周，漏斗模型的开展

上周到这周五之前也拿到了几个小offer，但是都不很满意，一直在等几个大厂的反馈辗转反侧难以成眠，手机24小时开到最大音量完全不敢静音，拉屎撒尿甚至洗澡都不敢离开视线范围

有几次在面试中导致漏接电话且无法回拨（有些公司会有虚拟号或者座机联系）时会难受好几天

今天下午终于接到了百度oc的电话，其实上周四就终面完了一直在等，今天一天都是极度的忐忑，因为8天没有通知大概率就是排序没了（今年百度三面也有池子，还要排序），最终放下电话的10分钟后突然感觉到一阵强烈的饥饿感，原来我已经一天没吃饭了（下午四点多接到的电话，当时快绝望了，hr是6点下班）。感觉人又活了过来

回想求职的过程，面试官、hr对简历经历的质疑（专业知识、本科到研究生中间有gap、通信非科班等），个中辛酸不足为外人道也

写到这里我也不知道自己想总结出什么经验，或者感悟出什么道理，可能只是想单纯的记录一下自己的心路历程。

一轮轮的面试，一次次的拒绝，给你希望又让希望破灭的那种滋味真是无比的辛酸

我相信任何参加了23届秋招春招的同学都能明白我的意思，22届最后的繁华到23届快速的破灭，心理上的巨大落差是最需要去克服的

接下来我要做的就是把缺的补上，剩下的面试面完，既然选择了来卷这条路，就不能后悔，打碎牙齿和血吞硬着头皮也要走下去

AcWing上的填坑计划昨天已经设计好了，都是做了但是没做完、没做到位的东西，深入思考求甚解， 完善她们也完善自己

毕竟我也不想到了新公司绩效只有0.8啊hhh

相信看到我写到这里的同学，都对找工作有自己的看法和体会，无论是正在找还是准备找都是需要用到我经历的这些东西，有些已经有了，有些没有，在这个平台重在交流

对了在这里再开个新坑，签约完之后找个时间把面经总结一下发出来还愿，合力完善一个更好的社区

Wind up，诸君共勉

23.03.31 学习

匈牙利算法=ntr算法

待字闺中，据为己有；名花有主，求他放手

Y总の奇妙比喻，极其的形象
看题解：https://www.acwing.com/solution/content/179030/

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 1e5 + 10;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];  // 妹子的匹配对象下标
bool st[N];  // 妹子是否被当前男生看过

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {  // 每个男生点，遍历他看上的多叉妹子点
        int j = e[i];  // 妹子
        if (!st[j]) {  // 妹子之前没看过
            st[j] = true;  // 妹子看过了
            if (match[j] == 0 || find(match[j])) {  // 1.妹子没有匹配对象；2.妹子的匹配对象有其他备胎
                match[j] = u;  // 绿了那个海王兄弟，把妹子抢过来
                return true;  // 匹配成功
            }
        }
    }

    return false;  // 匹配失败
}

int main() {
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    while (m -- ) {  // 常规邻接表建图
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    int res = 0;
    for (int i = 1; i <= n1; i ++ ) {  // 遍历左边所有男生，找妹子
        memset(st, false, sizeof st);  // 对于每个男生来说，找妹子都必须当作新人全部看一遍
        if (find(i)) res ++ ;  // 找到合适的妹子，匹配成功对+1
    }

    cout << res << endl;

    return 0;
}

23.03.31 学习

海绵哥的题解太清晰了，直接省去所有注释，自己看题解就行了
https://www.acwing.com/solution/content/105874/

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int c) {
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!color[j]) {
            if (!dfs(j, 3 - c)) return false;
        } 
        else if (color[j] && color[j] != 3 - c) {
            return false;
        }
    }

    return true;
}

int main() {
    int n, m;
    cin >> n >> m;

    memset(h, -1, sizeof h);
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    bool flag = true;
    for (int i = 1; i <= n; i ++ ) {
        if (!color[i]) {
            flag = dfs(i, 1);
            if (!flag) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}

23.03.30

算法

1. 并查集复习
2. 23.03.30，链式前向星+图遍历的分享博客
3. 23.03.31，图论补完
4. 数论补完

Linux

1. 管道补完
2. thrift复习

Djngo

1. 整体复习，使用vscode重学整理一遍

Web

1. Vue学习
2. 填充网站

Springboot

1. 学习前端网站建设即可

Unity

待完成…

23.03.30 学习

留坑

链式前向星真是个好玩意，以前懵懵懂懂的终于图论题碰多了慢慢明白，就得一点点手动去模拟

目前的思路

• for()：遍历是用来决定该节点的分叉走向，当一个节点有多条出边时，多叉走路
• dfs()：是用来在图之间进行从上个点走到下个点的，单链式走路

整体很像全排列，dfs用于位数移动，for用于每一位的取值遍历
参考题解：https://www.acwing.com/blog/content/2416/
图解和详细的路径展示，看题解，在这里不再赘述

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b) {
    e[idx] = b;

    ne[idx] = h[a];
    h[a] = idx ++ ;

    // for (int i = h[a]; i != -1; i = ne[i]) {
    //     cout << i << ' ' << e[i] << ' ' << ne[i] << ' ' << idx << ' ' << h[a];
    //     cout << endl;
    // }
}

int cnt = 0;
void dfs(int u) {
    st[u] = true;
    //cout << u << endl;  // u就是图中的每一个点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        cout << u << "->" << j << endl;  // 这里可以使用二维vector以数组形式存错所有的边
        if (!st[j]) {
            cnt ++ ;  // cnt是递归了多少次，也就是idx在图中走了多少条边，应该是等于m的，证明所有点都遍历到了
            dfs(j);
        }
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int start;

    for (int i = 0; i < m; i ++ ) {
        int a, b, c;
        cin >> a >> b;
        add(a, b);
        if (i == 0) start = a;
    }

    dfs(1);
    //cout << cnt;

    return 0;
}

23.03.29 学习

Kruskal = quicksort + 并查集，并查集真忘了，也不想写重载运算符，就用cmp比较rule吧
复习一下并查集
6600/52000，一道题提交前进200，把图论补完恐怕进不去前6000，还是要补完数论ToT

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;
int p[N];

struct Edge {
    int a, b, w;
}edges[M];

static bool cmp(Edge& a, Edge& b) {
    return a.w < b.w;
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    sort(edges, edges + m, cmp);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int sum = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if (find(a) != find(b)) {
            p[find(a)] = find(b);
            cnt ++ ;
            sum += w;
        }
    }

    if (cnt != n - 1) return INF;
    else return sum;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    int res = kruskal();

    if (res == INF) cout << "impossible" << endl;
    else cout << res << endl;

    return 0;
}

23.03.29学习

确实和dijsktra算法很像，思路代码风格都是

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int res = 0;

    for (int i = 0; i < n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) 
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;
        st[t] = true;
        if (i) res += dist[t];

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f3f3f3f, sizeof g);
    while (m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);  // 去掉重边的无向图
    }

    int t = prim();

    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

这版提前初始化dist[1]=0，把起点的距离初始化，省去两个if(i)的判断

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;

    for (int i = 0; i < n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) 
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (dist[t] == INF) return INF;
        st[t] = true;
        res += dist[t];

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);  // 去掉重边的无向图
    }

    int t = prim();

    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

23.03.28 学习

算法基础课补完计划开始

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e5 + 10, M = N;
int n, m;
int h[N], e[M], ne[M], idx;
int d[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topsort() {
    queue<int> q;
    int top[N], cnt = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (d[i] == 0) {
            q.push(i);
            cnt ++ ;
            top[cnt] = i;
        }
    }
    // bfs,删除每个点的入度找拓扑序
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j] -- ;
            if (d[j] == 0) {
                q.push(j);
                cnt ++ ;
                top[cnt] = j;
            }
        }
    }
    // 判断
    if (cnt != n) cout << -1 << endl;
    else {
        for (int i = 1; i <= n; i ++ ) cout << top[i] << ' ';
        cout << endl;
    }
}

int main()
{

    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++ ;
    }

    topsort();

    return 0;
}

23.03.24 学习

纪念，力扣Hot100正式刷完，前前后后刷了一个多月，虽然慢但是也完事了，之前基本就刷的差不多了面试够用就没再着急刷，下一目标把算法基础课的数论部分刷完，COYG!!!

还是看wzc大佬的题解，思路非常好，而且和LeetCode84.最大的矩形 思路高度联通，把一维问题扩展到二维，或许不是最快的，但是思路很好想。

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size(), res = 0;
        vector<int> heights(m, 0);
        heights.push_back(-1);

        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < m; j ++ ) {
                if (matrix[i][j] == '0') heights[j] = 0;
                else heights[j] ++ ;
            }
            // for (auto x : heights) cout << x << ' ';
            // cout << endl;

            // 对于每一层的heights都计算一遍res，遍历完m层最大的res就出来了
            stack<int> stk;
            for (int i = 0; i <= m; i ++ ) {
                while (!stk.empty() && heights[i] < heights[stk.top()]) {
                    auto cur = stk.top();
                    stk.pop();

                    if (stk.empty()) res = max(res, heights[cur] * i);
                    else res = max(res, heights[cur] * (i - stk.top() - 1));
                }
                stk.push(i);
            }
        }

        return res;
    }
};

23.03.24 学习

这个题打断点多模拟一下吧，看大佬题解https://www.acwing.com/solution/content/140/

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size(), res = 0;
        heights.push_back(-1);
        stack<int> stk;

        for (int i = 0; i <= n; i ++ ) {
            while (!stk.empty() && heights[i] < heights[stk.top()]) {
                auto cur = stk.top();
                stk.pop();

                if (stk.empty()) res = max(res, heights[cur] * i);  // 左边没有比他低的柱子
                else res = max(res, heights[cur] * (i - stk.top() - 1)); 
            }
            stk.push(i);
        }

        return res;
    }
};