首页 > itarticle > leetcode-biweekly-contest-5

leetcode-biweekly-contest-5

admin 11月 12, 2020 0

Time: Jul 27th, 2019 @ 10:30 PM - 12:00 PM (GMT+8)

总体来说，Biweekly Contest 还是比 Weekly Contest 简单不少的。。。

1133.Largest Unique Number

打卡题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
class  {
public:
    int largestUniqueNumber(vector<int>& a) {
        sort(a.begin(), a.end());
        
        int ret = -1;
        for (int i = a.size() - 1; i >= 0 && ret == -1;) {
            int cnt = 0;
            int cur = a[i];
            while (i >= 0 && a[i] == cur) {
                cnt++; i--;
            }
            if (cnt == 1) {
                ret = a[i + 1]; 
            }
        }
        return ret;
    }
};

1134. Armstrong Number

打卡题*2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
class  {
public:
    bool isArmstrong(int N) {
        int k = to_string(N).size();
        int n = N;
        int s = 0;
        while (N) {
            int t = N % 10;
            s += int(pow(t, k));
            N /= 10;
        }
        return s == n;
    }
};

1135. Connecting Cities With Minimum Cost

最小生成树。

Kruskal + 并查集实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
class :
    def find(self, x, f):
        if f[x] == x:
            return x
        f[x] = self.find(f[x], f)
        return f[x]
    
    def minimumCost(self, n: int, c: List[List[int]]) -> int:
        c = sorted(c, key=lambda x: x[2])
        f = [x for x in range(n + 1)]
        
        cost = 0
        cnt = 0
        for x in c:
            if self.find(x[0], f) != self.find(x[1], f):
                f[self.find(x[0], f)] = self.find(x[1], f)
                cost += x[2]
                cnt += 1
                
        if cnt != n - 1:
            return -1
        
        return cost

1136. Parallel Courses

感觉有点Floodfill和BFS的感觉。

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
 
class  {
public:
    int minimumSemesters(int n, vector<vector<int>>& relations) {
        vector<int> cnt(n + 1, 0);
        vector<vector<int>> m(n + 1, vector<int>{});
        for (auto &x : relations) {
            cnt[x[1]]++;
            m[x[0]].push_back(x[1]);
        }
        
        vector<int> v;
        vector<bool> visited(n + 1, false);
        for (int i = 1; i <= n; ++i) {
            if (cnt[i] == 0) {
                v.push_back(i);
                visited[i] = true;
            }
        }
        for (auto &x: v) {
            for (auto &y : m[x]) {
                cnt[y]--;
            }
        }
        
        if (v.size() == 0) return -1;
        
        int ret = 0;
        while (v.size() != 0) {
            vector<int> new_v;
            
            for (auto &x: v) {
                for (auto &y : m[x]) {
                    if (!visited[y] && cnt[y] == 0) {
                        visited[y] = true;
                        new_v.push_back(y);
                    }
                }
            }
            v = new_v;
            
            for (auto &x: v) {
                for (auto &y : m[x]) {
                    cnt[y]--;
                }
            }
            ret++;
        }
        
        for (int i = 1; i <= n; ++i) {
            if (!visited[i])
                return -1;
        }
        
        return ret;
    }
};
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能