第 184 场周赛

Posted on | In , | |
Words count in article: 415 | Reading time ≈ 2

1408. 数组中的字符串匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    static bool cmp(string a, string b) {
        return a.size() < b.size();
    }
    vector<string> stringMatching(vector<string>& words) {
        sort(words.begin(), words.end(), cmp);
        unordered_map<string, int> mp;
        vector<string> ret;
        for(auto word: words) {
            for(int i=0; i<word.size(); i++) {
                for(int j=1; j<=word.size()-i; j++) {
                    if(mp[word.substr(i, j)]) {ret.push_back(word.substr(i, j)); mp[word.substr(i, j)] = 0;}   
                }
            }
            mp[word]++;
        }
        return ret;
    }
};

1409. 查询带键的排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    //10e3可以暴力解决 
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> ans;
        vector<int> dm(m, 0);
        for (int i = 1; i <= m; i++) dm[i-1]=i;
        for (int i = 0; i < queries.size(); i++) {
            for (int j = 0; j < m; j++) {
                if (dm[j] == queries[i]) {
                    ans.push_back(j);
                    for (int k = j; k >= 1; k--) {
                        dm[k] = dm[k-1];
                    }
                    dm[0]=queries[i];
                    break;
                }
            }
        }
        return ans;
    }
};

1410. HTML 实体解析器

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
class Solution {
public:
    string entityParser(string text) {
        map<string,string> mp;
        mp["&quot;"] = "\"";
        mp["&apos;"] = "'";
        mp["&amp;"] = "&";
        mp["&gt;"] = ">";
        mp["&lt;"] = "<";
        mp["&frasl;"] = "/";
        string str;
        int k = 0;
        for(int i=0;i<text.length();i++){
            if(text[i]!='&')
                str += text[i];
            else{
                //cout << i << endl;
                int j = i;    
                string tt = "";
                while(j<text.length()){
                    if(text[i]==';')break;
                    tt += text[i];
                    i++;
                    j++;
                }
                tt += ";";
                //cout << tt << endl;
                if(mp.find(tt)!=mp.end()) str += mp[tt];
                else str += tt;
                i = j;
                
            }
        }
        return str;
    }
};

1411. 给 N x 3 网格图涂色的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numOfWays(int n) {
        long long aba = 6;
        long long abc = 6;
        int mod = 1000000007;
        while(--n > 0) {
            long long aba2 = (aba*3 + abc*2) % mod;
            long long abc2 = (aba*2 + abc*2) % mod;
            aba = aba2;
            abc = abc2;
        }
        return (int)((aba+abc) % mod);
    }
};
Donate? comment?