第 181 场周赛

Posted on | In , | |
Words count in article: 570 | Reading time ≈ 3

5364. 按既定顺序创建目标数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        int n = nums.size();
        vector<int> ret;
        vector<int> vis(n);
        int i = 0;
        while(ret.size() < n) {
            if(vis[i] == 1) continue;
            vis[i] = 1;
            vector<int> cur(ret.size()+1);
            for(int z=0; z<index[i]; z++) cur[z] = ret[z];
            cur[index[i]] = nums[i];
            for(int z=index[i]+1; z<cur.size(); z++) cur[z] = ret[z-1];
            i++;
            ret = cur;
            if(i == n) i = 0;
        }
        return ret;
    }
};

5178. 四因数

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
class Solution {
public:
    unordered_map<int, int> mp1;
    int get(int x) {
        if(mp1[x]) return mp1[x];
        int c = 0;
        int sum = 0;
        for(int i=1; i<=sqrt(x); i++) {
            if(x % i == 0) {c+=2; sum+=i; sum+=x/i;}
            if(c > 5) break;
        }
        double m = sqrt(x);
        if(m == (int)m) {c--; sum-=m;}
        if(c == 4) {
            mp1[x] = sum;
            return sum;
        }
        mp1[x] = 0;
        return 0;
    }
    int sumFourDivisors(vector<int>& nums) {
        int count = 0;
        for(int i=0; i<nums.size(); i++) {
            count += get(nums[i]);
        }
        return count;
    }
};

5367. 最长快乐前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string longestPrefix(string s) {
        int n = s.size();
        vector<int> kmp(n);
        kmp[0] = 0;
        for (int i = 1; i < n; ++i) {
            int j = kmp[i - 1];
            while (s[j] != s[i]) {
                if (!j) {
                    j = -1;
                    break;
                }
                j = kmp[j - 1];
            }
            kmp[i] = j + 1;
        }
        int len = kmp.back();
        return s.substr(0, len);
    }
};

5366. 检查网格中是否存在有效路径

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:
    bool vis[305][305];
    int m,n;
    int mp[305][305];
    bool left(int x,int y){
        return mp[x][y]==1||mp[x][y]==4||mp[x][y]==6;
    }
    bool right(int x,int y){
        return mp[x][y]==1||mp[x][y]==3||mp[x][y]==5;
    }
    bool up(int x,int y){
        return mp[x][y]==2||mp[x][y]==5||mp[x][y]==6;
    }
    bool down(int x,int y){
        return mp[x][y]==2||mp[x][y]==4||mp[x][y]==3;
    }
    void dfs(int x,int y){
        if(x<=0||x>m||y<=0||y>n) return;
        if(vis[x][y]) return;
        vis[x][y]=1;
        if(left(x,y)&&right(x,y+1)) dfs(x,y+1);
        if(right(x,y)&&left(x,y-1)) dfs(x,y-1);
        if(up(x,y)&&down(x-1,y)) dfs(x-1,y);
        if(down(x,y)&&up(x+1,y)) dfs(x+1,y);
    }
    bool hasValidPath(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++) 
                mp[i+1][j+1]=grid[i][j];
        dfs(1,1);
        return vis[m][n];
    }
};
Donate? comment?