Weekly Contest 171

Posted on | In , | |
Words count in article: 699 | Reading time ≈ 4

1317. Convert Integer to the Sum of Two No-Zero Integers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool check(int n){
        while(n){
            if(n % 10 == 0) return false;
            n /= 10; 
        }
        return true;
    }
    vector<int> getNoZeroIntegers(int n) {
        for(int i=1; i<n; i++){
            if(check(i) && check(n-i))
                return {i, n-i};
        }
        return {0,0};
    }
};

1318. Minimum Flips to Make a OR b Equal to c

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
class Solution {
public:
    string tostr(int a){
        string ret = "";
        while(a){
            ret += a % 2 == 0? '0' : '1';
            a /= 2;
        }
        return ret;
    }
    int minFlips(int ia, int ib, int ic) {
        string a = tostr(ia);
        string b = tostr(ib);
        string c = tostr(ic);
        int count = 0;
        int maxlen = max(a.size(), max(b.size(), c.size()));
        while(a.size() != maxlen) a+='0';
        while(b.size() != maxlen) b+='0';
        while(c.size() != maxlen) c+='0';
        for(int i=0; i<maxlen; i++){
            if(c[i] == '0'){
                count += (a[i]=='1' ? 1: 0);
                count += (b[i]=='1' ? 1: 0);
            }else{
                if(a[i] == '0' && b[i] == '0') count++;
            }
        }
        return count;
    }
};

1319. Number of Operations to Make Network Connected

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:
    vector<int> parent;
    int num;
    int find(int x){
        while(x != parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    void Union(int x, int y){
        int px = find(x);
        int py = find(y);
        num--;
        parent[px] = py;
    }
    int makeConnected(int n, vector<vector<int>>& connections) {
        parent.resize(n);
        num = n;
        for(int i=0; i<n; i++) parent[i] = i;
        int count = 0;
        for(auto& con: connections){
            int a = con[0], b = con[1];
            if(find(a) == find(b)) count++;
            else Union(a, b);
        }
        int ret = num-1;
        if(ret <= count) return ret;
        else return -1;
    }
};

1320. Minimum Distance to Type a Word Using Two Fingers

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
class Solution {
public:
    int M[26][2] = {
        {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, 
        {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, 
        {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, 
        {3, 0}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {3, 5}, 
        {4, 0}, {4, 1}
    };
    int dist(int i, int j) {
        return abs(M[i][0] - M[j][0]) + abs(M[i][1] - M[j][1]);
    }
    const int INF = 1e8;
    int minimumDistance(string word) {
        int N = word.size();
        if (N < 2) return 0;
        vector<vector<vector<int> > > dp(N + 1, vector<vector<int> >(26, vector<int>(26, INF)));
        int step = 0;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                dp[0][i][j] = 0;
            }
        }
        for (int i = 1; i <= N; ++i) {
            int curr = word[i - 1] - 'A';
            for (int j = 0; j < 26; ++j) {
                for (int k = 0; k < 26; ++k) {
                    dp[i][curr][j] = min(dp[i][curr][j], dp[i - 1][k][j] + dist(curr, k));
                    dp[i][curr][j] = min(dp[i][curr][j], dp[i - 1][curr][k] + dist(k, j));
                    
                    dp[i][j][curr] = min(dp[i][j][curr], dp[i - 1][j][k] + dist(curr, k));
                    dp[i][j][curr] = min(dp[i][j][curr], dp[i - 1][k][curr] + dist(k, j));
                }
            }
        }
        int res = INF;
        int ind = word[N - 1] - 'A';
        for (int i = 0; i < 26; ++i) {
            res = min(res, dp[N][ind][i]);
            res = min(res, dp[N][i][ind]);
        }
        return res;
    }
};
Donate? comment?