Weekly Contest 164

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

1266. Minimum Time Visiting All Points

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int maxn = 0;
        for(int i=0; i<points.size()-1; i++){
            int maxx = abs(points[i][0]-points[i+1][0]);
            int maxy = abs(points[i][1]-points[i+1][1]);
            maxn += maxx > maxy ? maxx : maxy;
        }
        return maxn;
    }
};

1267. Count Servers that Communicate

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
class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int ret = 0;
        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[0].size(); j++){
                if(grid[i][j] == 1){
                    int flag = 0;
                    // cout << i << " " << j << endl;
                    for(int x=0; x<grid[0].size(); x++){
                        if(grid[i][x] == 1 && x != j){
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 1){
                        ret ++;
                        continue;
                    }
                    for(int x=0; x<grid.size(); x++){
                        if(grid[x][j] == 1 && x != i){
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 1){
                        ret ++;
                        continue;
                    }
                }
            }
        }
        return ret;
    }
};

1268. Search Suggestions System

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& p, string src) {
        int m = src.size(), n = p.size();
        sort(p.begin(), p.end());
        vector<vector<string>> ret;
        vector<int> cnt;
        for(string t : p){
            int i = 0;
            for(i = 0; i < src.size() && i < t.size() && src[i] == t[i]; i++);
            cnt.push_back(i);
        }
        for(int i=0; i<m; i++){
            vector<string> v;
            for(int j=0; j<n; j++){
                if(cnt[j] > i && v.size() < 3){
                    v.push_back(p[j]);
                }
            }
            ret.push_back(v);
        }
        return ret;
    }
};

1269. Number of Ways to Stay in the Same Place After Some Steps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define ll long long int

class Solution {
public:
    ll dp[501][501];
    ll MOD = 1e9 + 7;
    
    ll f(int steps, int i, int len){
        if(i >= len || i < 0) return 0;
        if(steps == 0) return (i == 0);
        if(dp[steps][i] != -1) return dp[steps][i];
        ll op1 = f(steps-1, i+1, len) % MOD;
        ll op2 = f(steps-1, i-1, len) % MOD;
        ll op3 = f(steps-1, i, len) % MOD;
        return dp[steps][i] = (op1 + op2 + op3) % MOD;
    }
    
    int numWays(int steps, int arrLen) {
        memset(dp, -1, sizeof(dp));
        if(arrLen > steps) arrLen = steps;
        return (int)(f(steps, 0, arrLen) % MOD);
    }
};
Donate? comment?