LeetCode周賽155

1200. Minimum Absolute Difference

最小絕對差，周遊找出最小差，插入vector即可。

class Solution {
public:
   vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
       sort(arr.begin(), arr.end());
       int minr = INT_MAX;
       vector<vector<int>> re;
       for (int i = 1; i < arr.size(); i++) {
           if (arr[i] - arr[i - 1] < minr) {
               re.clear();
               re.push_back({arr[i - 1], arr[i]});
               minr = arr[i] - arr[i - 1];
               
           } else if (arr[i] - arr[i - 1] == minr) {
               re.push_back({arr[i - 1], arr[i]});
               
           }
           
       }
       return re;
   }
};
           

1201. Ugly Number III

找醜數

利用容斥 + 二分。

容斥定義：如果被計數的事物有A、B、C三類，那麼，A類和B類和C類元素個數總和= A類元素個數+ B類元素個數+C類元素個數—既是A類又是B類的元素個數—既是A類又是C類的元素個數—既是B類又是C類的元素個數+既是A類又是B類而且是C類的元素個數。（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）。

是以我們可以求出整數n是第幾個醜數。即 f ( n ) = n / a + n / b + n / c − n / l c m ( a , b ) − n / l c m ( b , c ) − n / l c m ( a , c ) + n / l c m ( a , b , c ) f(n) = n / a + n / b + n / c - n / lcm(a, b) - n / lcm(b,c)- n / lcm(a, c) + n / lcm(a, b, c) f(n)=n/a+n/b+n/c−n/lcm(a,b)−n/lcm(b,c)−n/lcm(a,c)+n/lcm(a,b,c)lcm為最小公倍數。

class Solution {
public:
    int gcb(int a, int b) {
        return b == 0 ? a : gcb(b, a % b);
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        int l = 1, h = 2e9;
        long long ab = (long long)a * (long long)b / gcb(a, b);
        long long  ac = (long long)a * (long long)c / gcb(a, c);
        long long bc = (long long)b * (long long)c / gcb(b, c);
        long long abc = (long long)a * bc / gcb(a, bc);
        while (l < h) {
            int mid = l + (h - l) / 2;
            int cnt = mid / a + mid / b + mid / c - mid / ac - mid / ab - mid / bc +                mid / abc;
            if (cnt >= n)
                h = mid;
            else
                l = mid + 1;
        }
        return l;
    }
};
           

1202. Smallest String With Swaps

最小字典序字元串。

即解決動态連通性，使用并查集。例如[0, 1], [1, 2],則 0 ~ 2都可任意調換得到最小的字典序。

class Solution {
public:
int find_parent(vector<int>& ds, int i) {
  return ds[i] == -1 ? i : ds[i] = find_parent(ds, ds[i]);
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
	vector<int> uf(s.size(), -1);
	vector<vector<int>> sortIndex(s.size());
	for (int i = 0; i < pairs.size(); i++) {
		int px = find_parent(uf, pairs[i][0]);
		int py = find_parent(uf, pairs[i][1]);
		if (px != py)
			uf[py] = px;
	}
	for (int i = 0; i < s.size(); i++) {
		sortIndex[find_parent(uf,i)].push_back(i);
	}
	for (auto si : sortIndex) {
		if (!si.empty()) {
			string temp = "";
			for (int c : si) {
				temp += s[c];
			}
			sort(temp.begin(), temp.end());
			for (int i = 0; i < temp.size(); i++) {
				s[si[i]] = temp[i];
			}
		}
	}
	return s;
    }
};

           

1203. Sort Items by Groups Respecting Dependencies

拓撲排序

維護一個組内的拓撲排序，以及各組之間的拓撲排序。

class Solution {
public:

    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        map<int, set<int>> groupItem; // 物品對應組
        vector<vector<int>> groupm(n + 1); // 組之間有向圖
        vector<vector<int>> itemm(n + 1); //物品之間有向圖
        vector<int> groupIn(n + 1); //組入度
        vector<int> itemIn(n + 1); //物品入度
        int index = m;
        for (int i = 0; i < group.size(); i++) {
            
            if (group[i] == - 1)
                group[i] = index++;
            groupItem[group[i]].insert(i);
        }
        for (int i = 0; i < beforeItems.size(); i++) {
            int g = group[i];
            //判斷先決條件物品是否屬于同一組，不同組加邊
            for (int b : beforeItems[i]) {
                int g1 = group[b];
                if (g1 == g) {
                    itemm[b].push_back(i);
                    itemIn[i]++;
                }else {
                    if (find(groupm[g1].begin(), groupm[g1].end(), g) == groupm[g1].end()) {
                        groupm[g1].push_back(g);
                        groupIn[g]++;
                    }
                }
            }
        }
        queue<int> q;
        vector<int> groupAns;
        for (int i = 0; i < index; i++) {
            if (groupIn[i] == 0) {
                q.push(i);
                groupAns.push_back(i);
            }
        }
        while(!q.empty()) {
            int f = q.front();
            q.pop();
            for (int g : groupm[f]) {
                groupIn[g]--;
                if (groupIn[g] == 0) {
                    q.push(g);
                    groupAns.push_back(g);
                }
            }
        }
        if (groupAns.size() != index)
            return {};
        
        vector<int> ans;
        for (int g : groupAns) {
            auto &items = groupItem[g];
            int cnt = 0;
            for (int i : items) {
                if (itemIn[i] == 0) {
                    q.push(i);
                    ans.push_back(i);
                    cnt++;
                }
            }
        
        
            while (!q.empty()) {
                int f = q.front();
                q.pop();
                for (int i : itemm[f]) {
                    itemIn[i]--;
                    if (itemIn[i] == 0) {
                        q.push(i);
                        ans.push_back(i);
                        cnt++;
                    }
                }
            }

            if (cnt != items.size())
                return {};
        }
        return ans;
    }
};