Weekly Contest 155

Posted on | In , | |
Words count in article: 1.2k | Reading time ≈ 7

Minimum Absolute Difference

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

  • a, b are from arr
  • a < b
  • b - a equals to the minimum absolute difference of any two elements in arr
1
2
Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]
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<int>> minimumAbsDifference(vector<int>& arr) {
		vector<vector<int>> ret;
		int min = INT_MAX;
		sort(arr.begin(), arr.end());
        for(int i=0; i<arr.size()-1; i++)
        {
            if(abs(arr[i]-arr[i+1]) < min)
                min = abs(arr[i]-arr[i+1]);
        }
        for(int i=0; i<arr.size()-1; i++)
        {
            if(abs(arr[i]-arr[i+1]) == min)
            {
                vector<int> cur;
                cur.push_back(arr[i]);
                cur.push_back(arr[i+1]);
                ret.push_back(cur);
            }
        }
		return ret;        
    }
};

Ugly Number III

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or 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
31
32
33
34
35
36
37
class Solution {
public:
    long long ab, ac, bc, abc;
    long long gcd(long long a, long long b)
    {
        if(b == 0) return a;
        else
            return gcd(b, a%b);
    }
    long long lcd(long long a, long long b)
    {
        return a*b/gcd(a,b);
    }
    long long rongchi(long long N, long long a, long long b, long long c)
    {
        return N/a + N/b + N/c - N/ab - N/ac - N/bc + N/abc;
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        ab = lcd(a, b);
        ac = lcd(a, c);
        bc = lcd(b, c);
        abc = lcd(ab, c);
        
        int left = 1;
        int right = 2000000001;
        
        while(left < right)
        {
            long long mid = left + (right - left)/2;
            long long num = rongchi(mid, a, b, c);
            if(num < n) left = mid+1;
            else if(num >= n) right = mid;
        }
        return left;
        
    }
};

Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

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
class Solution {
public:
    map<int, vector<int>> mm;
    vector<int> have;
    
    void dfs(int index, vector<int>& indexset)
    {
        if(have[index]) return;
        indexset.push_back(index);
        have[index] = 1;
        for(auto m: mm[index])
        {
            dfs(m, indexset);
        }
    }
    
    
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        for(auto& p: pairs)
        {
            mm[p[0]].push_back(p[1]);
            mm[p[1]].push_back(p[0]);
        }
        
        have.resize(s.length(), 0);
        
        
        for(int i=0; i<s.length(); i++)
        {
            if(have[i]) continue;
            
            string tmp;
            vector<int> indexset;
            
            dfs(i, indexset);
            
            sort(indexset.begin(), indexset.end());
            
            for(auto aa: indexset)
            {
                tmp.push_back(s[aa]);
            }
            
            sort(tmp.begin(), tmp.end());
            
            for(int j=0; j<tmp.size(); j++)
            {
                s[indexset[j]] = tmp[j];
            }
        }
        return s;
    }
};

1203. Sort Items by Groups Respecting Dependencies

拓扑排序

There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it’s equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.

Return a sorted list of the items such that:

  • The items that belong to the same group are next to each other in the sorted list.
  • There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).

Return any solution if there is more than one solution and return an empty list if there is no solution.

  • 第一步，构造小组的依赖关系和组内项目的依赖关系。
  • 第二步，判断小组间是否有冲突，没冲突计算出小组的拓扑排序。
  • 第三步：判断每个小组内项目是否有冲突，没冲突计算出小组内项目的拓扑排序。
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class Solution {
    map<int, set<int>> group2item; //组织架构，没有小组的项目会分配一个唯一的小组
    
    map<int, int> groupInNum;       //每个小组的入度
    map<int, set<int>> groupDir;   //小组的依赖图
    map<int, int> itemInNum;       //组内每个成员的入度
    map<int, set<int>> itemDir;    //组内的依赖图

    
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        int minGroup = m;
        
        for(int i=0;i<group.size();i++){
            if(group[i] == -1){
                group[i] = minGroup++;
            }
            group2item[group[i]].insert(i);
        }
        for(int to = 0; to < beforeItems.size(); to++){
            int toGroup = group[to];
            for(auto from: beforeItems[to]){
                int fromGroup = group[from];
                
                if(toGroup == fromGroup){
                    itemDir[from].insert(to);
                    itemInNum[to]++; //入度加一
                }else{
                    if(groupDir[fromGroup].count(toGroup) == 0){
                        groupDir[fromGroup].insert(toGroup);
                        groupInNum[toGroup]++; //入度加一
                    }
                }
            }
        }
        
        //第一步检查小组间是否有冲突
        queue<int> que;
        vector<int> groupAns;
        for(int to = 0; to < minGroup; to++){
            if(groupInNum[to] == 0){
                que.push(to);
                groupAns.push_back(to);
            }
        }
        
        while(!que.empty()){
            int from = que.front();
            que.pop();
            for(auto to: groupDir[from]){
                groupInNum[to]--;
                if(groupInNum[to] == 0){
                    que.push(to);
                    groupAns.push_back(to);
                }
            }
        }
        if(groupAns.size() != minGroup){
            return {};
        }
        
        //第二部检查小组内的项目是否有冲突
        vector<int> ans;
        
        
        for(auto id: groupAns){
            auto& items = group2item[id];
            
            int num = 0;
            for(auto to: items){
                if(itemInNum[to] == 0){
                    que.push(to);
                    ans.push_back(to);
                    num++;
                }
            }
            
            while(!que.empty()){
                int from = que.front();
                que.pop();
                for(auto to: itemDir[from]){
                    itemInNum[to]--;
                    if(itemInNum[to] == 0){
                        que.push(to);
                        ans.push_back(to);
                        num++;
                    }
                }
            }
            
            if(num != items.size()){
                return {};
            } 
        }
        return ans;
        
    }
};
Donate? comment?