头像

yandy


访客:4690

离线:2天前



yandy
9天前

8.29

一面:
面试官是客户端的,前面问的都是一些常规c++语法问题,手撕shared_ptr,
之后撕题,链表右移k位(循环移动);

二面:
输入URL之后的过程;
DNS解析的过程,为什么要用UDP;
系统调用和库函数的区别
用户态和内核态的区别,为什么要区分,用户态到内核态切换的底层;
口述思路 多线程顺序打印1234…
Mysql索引,事务的ACID
Redis的数据结构,单线程为什么快。
撕题 之字形打印二叉树

9.11三面

http和https的区别;
数字签名,对称加密和非对称加密;
内存分区,堆栈之间是什么。
Mmap的底层
三次握手协商哪些内容

撕题leetcode跳跃游戏2

撕题 sql 一个表,id,name,gender,level

求不同level下不同各gender的个数。

(前天HR说三面已过,无HR面,求一波意向书,等得好苦啊)



活动打卡代码 AcWing 786. 第k个数

yandy
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e5+10;
int n,k;
int q[N];

int quick_sort(int l,int r,int cnt)
{
    if(l>=r)return q[l];

    int i=l-1,j=r+1,x=q[l];
    while(i<j)
    {
        while(q[++i]<x);
        while(q[--j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    int sl=j-l+1;
    if(cnt<=sl)return quick_sort(l,j,cnt);

    return quick_sort(j+1,r,cnt-sl);
}

int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>q[i];
    cout<<quick_sort(0,n-1,k);
    return 0;

}


活动打卡代码 AcWing 165. 小猫爬山

yandy
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=20;

int n,m;
int w[N],sum[N];
int res=N;

void dfs(int u,int k)
{
    if(k>=res)return;
    if(u==n)
    {
        res=k;
        return;
    }

    for(int i=0;i<k;i++)
    {
        if(w[u]+sum[i]<=m)
        {
            sum[i]+=w[u];
            dfs(u+1,k);
            sum[i]-=w[u];
        }
    }
        sum[k]=w[u];
        dfs(u+1,k+1);
        sum[k]=0;

}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>w[i];
    sort(w,w+n);
    reverse(w,w+n);
    dfs(0,0);
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1117. 单词接龙

yandy
3个月前
#include<iostream>
#include<cstring>

using namespace std;

const int N=25;

int n;
string s[N];
char st;
int g[N][N];
int used[N];
int res;

void dfs(string d,int last)
{
    res=max((int)d.size(),res);
    used[last]++;
    for(int i=0;i<n;i++)
    {
        if(g[last][i]&&used[i]<2)
        {
            dfs(d+s[i].substr(g[last][i]),i);
        }
    }
    used[last]--;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    cin>>st;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            string a=s[i],b=s[j];
            for(int k=1;k<min(a.size(),b.size());k++)
            {
                if(a.substr(a.size()-k,k)==b.substr(0,k))
                {
                    g[i][j]=k;
                    break;
                }
            }
        }
    for(int i=0;i<n;i++)
        if(s[i][0]==st)
            dfs(s[i],i);

    cout<<res<<endl;       
    return 0;

}


活动打卡代码 AcWing 1116. 马走日

yandy
3个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=10;

int n,m;
bool st[N][N];
int res;

int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1};

void dfs(int x,int y,int u)
{
    if(u==n*m)
    {
        res++;
        return ;
    }

    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=n||b<0||b>=m)continue;
        if(st[a][b])continue;
        st[a][b]=true;
        dfs(a,b,u+1);
        st[a][b]=false;
    }
}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        memset(st,0,sizeof st);
        res=0;
        cin>>n>>m>>x>>y;
        st[x][y]=true;
        dfs(x,y,1);
        cout<<res<<endl;
    }
    return 0;

}


活动打卡代码 AcWing 1113. 红与黑

yandy
3个月前
#include<iostream>
#include<cstring>

using namespace std;

const int N=25;

int n,m;
char g[N][N];
bool st[N][N];
int res;

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

void dfs(int x,int y)
{
    st[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=n||b<0||b>=m)continue;
        if(g[a][b]=='#'||st[a][b])continue;
        st[a][b]=true;
        res++;
        dfs(a,b);
    }
}

int main()
{
    while(cin>>m>>n,n||m)
    {
        for(int i=0;i<n;i++)cin>>g[i];
        memset(st,0,sizeof st);
        res=1;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j]=='@')
                    dfs(i,j);

        cout<<res<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1112. 迷宫

yandy
3个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=110;

int n;
char g[N][N];
bool st[N][N];
int xa,ya,xb,yb;

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

bool dfs(int x,int y)
{
    if(g[x][y]=='#')return false;
    if(x==xb&&y==yb)return true;
    st[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=n||b<0||b>=n)continue;
        if(st[a][b]||g[a][b]=='#')continue;
        if(dfs(a,b))return true;
    }

    return false;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(st,0,sizeof st);
        for(int i=0;i<n;i++)cin>>g[i];
        cin>>xa>>ya>>xb>>yb;
        if(dfs(xa,ya))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return  0;

}


活动打卡代码 AcWing 190. 字串变换

yandy
3个月前
#include<iostream>
#include<cstring>
#include<queue>
#include<unordered_map>

using namespace std;

string A,B;
string a[6],b[6];
int n;



int work(queue<string>&q,unordered_map<string,int>& da,unordered_map<string,int>& db,string a[],string b[])
{
    for(int x=0,s=q.size();x<s;x++)
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<t.size();i++)
        {
            for(int j=0;j<n;j++)
            {
                if(t.substr(i,a[j].size())==a[j])
                {
                    string k=t.substr(0,i)+b[j]+t.substr(i+a[j].size());
                    if(da.count(k))continue;
                    if(db.count(k))return da[t]+1+db[k];

                    da[k]=da[t]+1;
                    q.push(k);
                }
            }
        }
    }
    return 11;
}
int bfs()
{
    queue<string>qa,qb;
    unordered_map<string,int>da,db;
    qa.push(A),qb.push(B);
    da[A]=0,db[B]=0;
    while(qa.size()&&qb.size())
    {
        int t;
        if(qa.size()<=qb.size())
        {
            t=work(qa,da,db,a,b);
        }
        else 
        {
            t=work(qb,db,da,b,a);
        }
        if(t<=10)return t;
    }
    return 11;
}

int main()
{


    cin>>A>>B;
    while(cin>>a[n]>>b[n])n++;

    int step=bfs();
    if(step>10)cout<<"NO ANSWER!";
    else cout<<step<<endl;

    return 0;

}


活动打卡代码 AcWing 175. 电路维修

yandy
3个月前
#include<iostream>
#include<cstring>
#include<deque>
#include<algorithm>

using namespace std;

const int N=510;

int n,m;
char g[N][N];
int d[N][N];
bool st[N][N];

void bfs()
{
    deque<pair<int,int>>q;
    memset(d,0x3f,sizeof d);
    memset(st,0,sizeof st);
    char cs[]="\\/\\/";
    int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};
    int ix[]={-1,-1,0,0},iy[]={-1,0,0,-1};

    q.push_back({0,0});
    d[0][0]=0;

    while(q.size())
    {
        auto t=q.front();
        q.pop_front();

        int x=t.first,y=t.second;
        if(st[x][y])continue;
        st[x][y]=true;

        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>n||b<0||b>m)continue;
            int ga=x+ix[i],gb=y+iy[i];
            int w=(g[ga][gb]!=cs[i]);
            int dis=d[x][y]+w;
            if(d[a][b]>dis)
            {
                d[a][b]=dis;
                if(!w)q.push_front({a,b});
                else q.push_back({a,b});
            }

        }
    }
}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)cin>>g[i];

        if(n+m&1)cout<<"NO SOLUTION"<<endl;
        else{
                bfs();
                cout<<d[n][m]<<endl;
            }
    }
    return 0;

}


活动打卡代码 AcWing 1107. 魔板

yandy
3个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>

using namespace std;
typedef pair<int,int>pII;

string st,ed;
char g[2][4];
unordered_map<string,int> d;
unordered_map<string,pair<char,string>>pre;

void set(string s)
{
    for(int i=0;i<4;i++)
        g[0][i]=s[i];

    for(int i=3,j=4;i>=0;i--,j++)
        g[1][i]=s[j];
}

string get()
{
    string res;
    for(int i=0;i<4;i++)
        res+=g[0][i];
    for(int i=3;i>=0;i--)
        res+=g[1][i];

    return res;
}

string move0(string t)
{
    set(t);

    for(int i=0;i<4;i++)
        swap(g[0][i],g[1][i]);

    return get();
}

string move1(string t)
{
    set(t);
    char v1=g[0][3],v2=g[1][3];
    for(int i=0;i<2;i++)
        for(int j=3;j>0;j--)
            g[i][j]=g[i][j-1];
    g[0][0]=v1,g[1][0]=v2;

    return get();
}

string move2(string t)
{
    set(t);

    char c=g[0][1];
    g[0][1]=g[1][1];
    g[1][1]=g[1][2];
    g[1][2]=g[0][2];
    g[0][2]=c;

    return get();
}


void bfs()
{
    queue<string>q;
    q.push(st);
    d[st]=0;

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t==ed)return;
        string m[3];
        m[0]=move0(t);
        m[1]=move1(t);
        m[2]=move2(t);
        for(int i=0;i<3;i++)
        {
            string k=m[i];
            if(d.count(k))continue;

            d[k]=d[t]+1;
            q.push(k);
            pre[k]={char(i+'A'),t};
        }
    }
}
int main()
{
    for(int i=0;i<8;i++)
    {
        int x;
        cin>>x;
        ed+=char(x+'0');
    }
    st="12345678";

    bfs();
    cout<<d[ed]<<endl;
    string res;
    if(d[ed])
    {
        while(ed!=st)
        {
            res+=pre[ed].first;
            ed=pre[ed].second;
        }
        reverse(res.begin(),res.end());
        cout<<res<<endl;
    }
    return 0;
}