2022-09-度小满一面二面

2022-09-03-度小满一面-25min

周六

删除重复节点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        ListNode* h=new ListNode(0), *nn, *p, *t;
        h->next=pHead;
        p=h;
        while(p->next){
            nn=p->next->next;
            if(!nn)
                break;
            if(p->next->val!=nn->val){
                p=p->next;
            }else{
                int sameVal=p->next->val;
                while(p->next&&p->next->val==sameVal){
                    t=p->next;
                    p->next=t->next;
                    delete t;
                }
                t=nullptr;
            }
        }
        return h->next;
    }
};

2022-09-06-度小满二面-55min

问了很多都说不会，最后来个hard也不会，暴力过了10%

左右括号匹配，字符串里有些问号，问号可以是左括号可以是右括号，
每个问号改为每个符号的成本都不一样，问最小成本使得括号配对合法

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

// To execute C++, please define "int main()"

// The TestCase is shown below
// Input : 1 2
// Output : 3
vector<int> l,r;
int minCost,n;
string s,ansStr;
void dfs(int i, int lc, int pi, int cost){
    if(i==n){
        if(lc==0){
            if(minCost>cost){
                ansStr=s;
                minCost=cost;
            }
        }
        return ;
    }
    else if(cost>minCost)
        return;
    while(i<n){
        if(s[i]=='(') lc++;
        else if(s[i]==')'){
            lc--;
            if(lc<0) return;
        }else break;
    }

    if(i==n){
        if(lc==0){
            if(minCost>cost){
                ansStr=s;
                minCost=cost;
            }
        }
        return ;
    }

    ++pi;
    //if(l[i]<r[i]){
        s[i]='(';
        dfs(i+1,lc+1,pi,l[pi]+cost);
    //}
    if(lc>0){
        s[i]=')';
        dfs(i+1,lc-1,pi,r[pi]+cost);
    }
    s[i]='?';
    return;
}

int main() {

    while(cin>>s){
        n=s.length();
        int q=0;
        for(auto& i:s){
            if(i=='?')
                q++;
        }
        l.resize(q,0);
        r.resize(q,0);
        for(int i=0;i<q;i++){
            cin>>l[i]>>r[i];
        }
        if(n%2==1)
        {
            cout<<-1<<endl;
            continue;
        }
        minCost=0x3fffffff;
        dfs(0,0,-1,0);
        cout<<minCost<<"\n"<<ansStr<<"\n";
        /*
        int lc=0, pi=-1;
        for(int i=0;i<n;i++){
            if(s[i]=='(')
                lc++;
            else if(s[i]==')')
                lc--;
            else{
                pi++;

            }
        }*/
    }

      return 0;
}

以为会挂的，后收到了3面（9月17号），过了，10月约hr面