腾讯笔试 4.18 差一点AK 各题的做法和代码

注意我是投后台开发的，所以题目不一定和其他岗位相同

先提前声明：我是条ACM铜狗，这次能差点AK很大程度上也是因为这一点。

先上做法，下一楼再上代码
T1 求最小字典序的链表 AC
暴力穷举每条链表
T2 发公告 AC
维护结构体 node 记录每个人的时间间隔、id、下一次能接收的时间。
然后自定义比较器的优先队列。优先选择下一次能接收的时间小的，其次选择编号小的。
T3 俱乐部扣积分 AC
自定义比较器，扣分越大越靠前，扣分相同时截至时间小的靠前。然后用这个比较器 sort 一遍。
sort 完后挨个尝试安放项目，如果时间点 i 已经安过项目了，那下次就往 i 之前的没被安放的时间点放。
T4 能换位的字符串比较 AC
对两个字符串分别做一种特殊的递归操作，然后比较是否相同即可。
递归操作的伪代码：

void part(char* s, int len)
{
        // 如果长度为奇数，不能再分，直接返回
    if(len&1) return;
    // 如果长度为偶数，递归分离
    char *b = s+len/2;
    part(s, len/2);
    part(b, len/2);
        // 如果后半部分比前半部分字典序更小，那就交换这俩字符串
    if(cmp(s,b,len/2)>0)
        strswap(s,b,len/2);
}

T5 打地鼠 过90%
暴力DP。
没AC的原因是最后五分钟的时候我才发现题目里还有一句：这轮从a到b，下轮就不能从b到a了。

好了，剩下的时间就是祈祷我不会因为双非本科的学历被刷掉简历了。

各题代码：

T1 AC

 struct ListNode {
    int val;    
    struct ListNode *next;
};


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param S ListNode类 val表示权值，next指向下一个元素
     * @return ListNode类
     */
    int len;
    ListNode* head;
    int cmp(ListNode* pta, ListNode* ptb){
        ListNode* a = pta;
        ListNode* b = ptb;
        int cnt = len;
        while(cnt--){
            if(a->val!=b->val) return a->val-b->val;
            a=a->next;
            b=b->next;
            if(a==nullptr) a=head;
            if(b==nullptr) b=head;
        }
        return 0;
    }

    void getlen(ListNode* a){
        len=0;
        ListNode* x = a;
        while(x!=nullptr){
            x=x->next;
            len++;
        }
    }

    ListNode* solve(ListNode* S) {
        head = S;
        ListNode* ret = S;
        getlen(S);
        ListNode* p = ret->next;
        for(int i=1;i<len;i++, p=p->next){
            if(cmp(ret, p)>0)
                ret=p;
        }
        p = ret;
        while(len--){
            if(p->next == nullptr && len>0){
                p->next=head;
            }
            else 
            if(len==0){
                p->next = nullptr;
            }
            p=p->next;
        }
        //p->next=nullptr;
        return ret;
    }
};

T2 AC

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int t;
    int id;
    int stamp;
    bool operator<(const node& other) const {
        if(other.stamp!=stamp) return other.stamp<stamp;
        else return other.id<id;
    }
};

int main()
{
    ios::sync_with_stdio(0);
    priority_queue<node> q;
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        q.push(node{t,i,t});
    }
    while(k--){
        node x = q.top();
        q.pop();
        cout<<x.id<<"\n";
        //cout<<x.id<<" "<<x.t<<"\n";
        q.push(node{x.t,x.id,x.stamp+x.t});
    }
    return 0;
}

T3 AC

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1000+5;

struct node{
    int t;
    int val;
}a[MAXN];

bool vis[MAXN];

int cmp(const node& a,const node& b){
    if(a.val!=b.val) return a.val>b.val;
    else return a.t<b.t;
}

bool putit(int id){
    while(id>=1 && vis[id]){
        id--;
    }
    vis[id]=true;
    return id!=0;
}

void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].t;
    for(int i=1;i<=n;i++) cin>>a[i].val;
    for(int i=1;i<=n;i++) vis[i]=false;
    sort(a+1,a+n+1,cmp);
    int ans =0 ;
    for(int i=1;i<=n;i++){
        if(!putit(a[i].t)){
            //cout<<a[i].val;
            //for(int i=1;i<=n;i++)    cout<<vis[i];
            //cout<<"\n";
            ans+=a[i].val;
        }
    }
    cout<<ans<<"\n";
    // for(int i=1;i<=n;i++){
    //     cout<<a[i].t<<" "<<a[i].val<<"\n";
    // }
}

int main(){
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T4 AC

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
char sa[MAXN],sb[MAXN];

int cmp(char* a, char* b, int len){
    for(int i=0;i<len;i++){
        if(a[i]<b[i]) return -1;
        else if(a[i]>b[i]) return 1;
    }
    return 0;
}

void strswap(char* a, char* b, int len){
    for(int i=0;i<len;i++){
        swap(a[i],b[i]);
    }
}

void part(char* s, int len){
    // odd
    if(len&1) return;
    // even
    char *b = s+len/2;
    part(s, len/2);
    part(b, len/2);
    if(cmp(s,b,len/2)>0)
        strswap(s,b,len/2);
}

bool solve(){
    cin>>sa>>sb;
    int len = strlen(sa);
    if(cmp(sa,sb,len)==0){
        return true;
    }
    if(len&1){
        return false;
    }
    part(sa, len);
    part(sb, len);
    //cout<<"af a :"<<sa<<"\n";
    //cout<<"af b :"<<sb<<"\n";
    return cmp(sa,sb,len)==0;
}

int main(){
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--){
        cout<<(solve()?"YES\n":"NO\n");
    }
    return 0;
}

T5 过90%

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
int d[MAXN][MAXN];
int f[MAXN][MAXN];
int g[MAXN][MAXN];

int main(){
    int n,m,T;
    cin>>n>>m>>T;
    memset(d,0x3f3f3f3f,sizeof(d));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>d[i][j];
        }
    }
    for(int i=0;i<=MAXN;i++){
        for(int j=0;j<=MAXN;j++){
            f[i][j]=g[i][j]=-0x3f3f3f3f;
        }
    }
    int t=1;
    f[1][1]=0;
    for(;t<=T;t++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                g[i][j]=max(max(f[i-1][j],f[i][j-1]),max(f[i+1][j],f[i][j+1]));
                if(t%d[i][j]==0){
                    g[i][j]++;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                f[i][j]=g[i][j];
            }
        }
    }


    if(f[n][m]>0)    cout<<f[n][m];
    else cout<<0;

    return 0;
}