力扣周赛251题解

Posted on | Post modified:

力扣周赛251题解

T1.字符串转化后的各位数字之和

字符串转化后的各位数字之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int getLucky(string s, int k) {
        vector<int> d;
        for(char c:s){
            int k=c-'a'+1;
            if(k>=10){
                d.push_back(k/10);
                d.push_back(k%10);
            }else{
                d.push_back(k);
            }
        }
        for(int tt=1;tt<=k;tt++){
            int ans=0;
            for(int v:d){
                ans+=v;
            }
            d.clear();
            while(ans){
                d.push_back(ans%10);
                ans/=10;
            }
            reverse(d.begin(),d.end());
        }
        int res=0;
        for(int v:d){
            res=res*10+v;
        }
        return res;
    }
};

T2. 子字符串突变后可能得到的最大整数

贪心，找到第一个能够变大的为止，以其为起点突变即可，直到遇到一个突变后会变小的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string maximumNumber(string num, vector<int>& change) {
        int n=(int)num.size();
        int id=-1;
        for(int i=0;i<n;i++){
            if(change[num[i]-'0']+'0'>num[i]){
                id=i;break;
            }
        }
        if(id==-1){
            return num;
        }
        for(int i=id;i<n;i++){
             if(change[num[i]-'0']+'0'>=num[i]){
                num[i]=change[num[i]-'0']+'0';
            }else{
                 break;
             }
        }
        return num;
    }
};

T3.最大兼容性评分和

实际上利用next-permutation函数可以通过本题…比赛的时候想复杂了，使用了状压dp。

令$dp[i][status]$表示前$i$个学生已经选择了$status$导师。

则状态转移方程为：

其中$cost(i,j)$表示学生$i$跟随导师$j$的兼容性评分，时间复杂度为$O(n\cdot m^2 \cdot 2^m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int dp[10][1<<8];
    int cal(vector<int> a,vector<int> b){
        int ans=0;
        int n=(int)a.size();
        for(int i=0;i<n;i++){
            if(a[i]==b[i]){
                ++ans;
            }
        }
        return ans;
    }
    int bitcount(int x){
        int ans=0;
        while(x){
            ans+=(x&1);
            x/=2;
        }
        return ans;
    }
    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        dp[0][0]=0;
        int m=(int)students.size();
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                for(int last=0;last<(1<<m);last++){
                    if((((last>>(j-1))&1)==0)&&bitcount(last)==i-1){
                        dp[i][last|(1<<(j-1))]=max( dp[i][last|(1<<(j-1))],dp[i-1][last]+cal(students[i-1],mentors[j-1]));
                    }
                }
            }
        }
        
        return dp[m][(1<<m)-1];
    }
};

T4.删除系统中的重复文件夹

卡常卡到爆炸…

考虑根据所有的文件路径复原出文件树，文件树的复原过程类似于字典树的构建过程。

接下来对于构造出来的文件树进行DFS，利用DFS求出以$node$为根节点的子树的所有文件的hash值。

最后只要当前子树的hash值出现过，则当前子树就要被删除。

最后再利用一次DFS遍历出答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
const int base = 233;
const int mod = 1e9+7;
typedef long long ll;
struct Node{
    string s;
    int id;
    ll hash_val;
    vector<Node*> sons;
    Node(string s,int id):s(s),id(id){}
};
class Solution {
public:
    map<pair<Node*,string>,Node*> nxt;
    unordered_map<string,int> id;
    unordered_map<ll,int> cnt;
    vector<vector<string> > ans;
    vector<string> tmp;
    void Insert(vector<string> vec,Node *node){
        for(string s:vec){
            bool find=0;
            Node *p = nxt[{node,s}];
            if(p){
                node=p;
            }else{
                Node *v = new Node(s,id[s]);
                node->sons.push_back(v);
                nxt[{node,s}]=v;
                node=v;                
            }

        }
    }
    ll Gethash(string s){
        ll ans=0;
        for(char c:s){
            ans=(ans*base%mod+(int)c)%mod;
        }
        return ans;
    }
    void DFS(Node* u){
        ll ans=0;
        for(auto v:u->sons){
            DFS(v);
            ll t=(v->hash_val*base%mod+Gethash(v->s))%mod;
            ans=(ans*base%mod+t)%mod;
        }
        cnt[ans]++;
        u->hash_val=ans;
    }
    void DFSS(Node* u){
        if(cnt[u->hash_val]>1&&u->hash_val){
            return ;
        }
        if(u->s!="/"){
            tmp.push_back(u->s);
            ans.push_back(tmp);
        }
        for(auto v:u->sons){
            DFSS(v);
        }
        if(tmp.size()) tmp.pop_back();
    }
    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
        Node *root = new Node("/",1);
        Node *p=root;
        for(auto v:paths){
            Insert(v,p);
        }
        DFS(root);
        DFSS(root);
        return ans;
    }
};