#腾讯笔试10.26 ak代码#

#腾讯笔试#

五题难度分析，四道medium，一道hard

第一题

    ListNode* xorList(ListNode* a, ListNode* b) {
        stack<ListNode*>st;
        ListNode* ca=a;
        ListNode* cb=b;
        while(ca!=nullptr){
            st.push(ca);
            ca=ca->next;
        }
        ListNode* head=new ListNode(0);
        while(!st.empty()){
            ListNode* t=new ListNode(st.top()->val^cb->val);
            t->next=head->next;
            head->next=t;
            cb=cb->next;
            st.pop();
            if(cb==nullptr){
                while(!st.empty()){
                    ListNode* t=st.top();
                    t->next=head->next;
                    head->next=t;
                    st.pop();
                }
            }
        }
        if(cb!=nullptr){
            while (cb!=nullptr) {
                ListNode* t=new ListNode(cb->val);
                t->next=head->next;
                head->next=t;
                cb=cb->next;
            }
        }
        ListNode* h=head->next;
        while(h!=nullptr&&h->val==0){
            h=h->next;
        }
        if(h==nullptr) h=new ListNode(0);
        return h;
    }

第二题

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<stack>
#include<algorithm>
#include<bitset>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;
typedef pair<int,int> pi;

int count(int n){
    int res=0;
    while(n!=0){
        n=n&(n-1);
        res++;
    }
    return res;
}
int main(){
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    priority_queue<pi>q;
    long long res=0;
    for(int i=0;i<n;i++) {
        cin>>v[i];
        res+=(long long)v[i];
        q.push(pi(v[i]-count(v[i]),i));
    }
    while(k--){
        auto [a,i]=q.top();
        q.pop();
        int x=v[i]-a;
        res=res-a+(long long)x;
        q.push(pi(x,i));
    }
    cout<<res<<endl;
}

第三题

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<stack>
#include<algorithm>
#include<bitset>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;
int main(){
    int n;
    cin>>n;
    deque<int>q;
    int a;
    for(int i=0;i<n;i++){
        cin>>a;
        q.push_back(a);
    }
    vector<int>v(n);
    for(int i=1;i<=n;i++){
        if(i&1==1){
            v[i-1]=max(q.front(),q.back());
            if(q.front()>=q.back()){
                q.pop_front();
            }else q.pop_back();
        }else{
            v[i-1]=min(q.front(),q.back());
            if(q.front()<=q.back()){
                q.pop_front();
            }else q.pop_back();
        }
    }
    for(auto i:v) cout<<i<<" ";
    cout<<endl;
}

第四题

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<stack>
#include<algorithm>
#include<bitset>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;

long long f(long long n,long long y){
    if(n==1) return cal(y);
    long long x=1;
    while(x<n) x=x<<1;
    if(x==n) return x/2;
    return x/4+f(n-x/2,y);
}
bool cal(long long n){
    if(n==1) return 1;
    long long x=1;
    while(x<n) x=x<<1;
    return !cal(n-x/2);
}
int main(){
    long long l,r;
    cin>>l>>r;
    long long x=f(r,r)-f(l-1,l-1);
    cout<<x<<endl;
}

第五题

第五题多说一嘴哈，其实这个题可以分解为，将一个数组分为两部分，使得两部分的和的差值最小，保存怎么分的就行

#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<stack>
#include<algorithm>
#include<bitset>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;

vector<int>st;
int mx=0;
unordered_map<long,int>p;
int jud(vector<int>&a,int x,int i,vector<int>&v,int cur){
    if(i==a.size()){
        if(cur>mx){
            st=v;
            mx=cur;
        }
        return cur;
    }
    long ss=cur*101+i;
    int res=0;
    if(p.count(ss)) return p[ss];
    if(a[i]+cur>x){
        res=jud(a,x,i+1,v,cur);
    }else{
        v[i]=1;
        int l=jud(a,x,i+1,v,cur+a[i]);
        v[i]=0;
        int r=jud(a,x,i+1,v,cur);
        res=max(l,r);
    }
    p[ss]=res;
    return res;
}

int main(){
    int n,sum=0;
    cin>>n;
    vector<int>a(n);
    st.resize(n,0);
    for(int i=0;i<n;i++) {
        cin>>a[i];
        sum+=a[i];
    }
    int x=0,y=0;
    vector<int>v(n,0);
    x=jud(a,sum/2,0,v,0);
    y=x-sum;
    cout<<x<<" "<<y<<endl;
    for(int i=0;i<st.size();i++){
        if(st[i]==1){
            cout<<"Y";
        }else cout<<"X";
    }
    cout<<endl;
}