讨论/题目交流/🏆 第 155 场力扣周赛/
🏆 第 155 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。
image.png

共 14 个回复

题解已到 https://leetcode-cn.com/circle/article/wNK6s3/

今天有事情缺席了周赛 刚补完题目 题解稍后就来~~
先占坑:

  1. 排序 + 暴力
  2. 容斥原理 + 二分
  3. 并查集
  4. 变种拓扑排序,题目比较难懂
8

10

丑数这道题的这个例子,为什么,10不是丑数啊????

输入:n = 4, a = 2, b = 3, c = 4
输出:6
解释:丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。
7

这周的周赛有点残忍啊。。。。

6

丑数用的二分查找大法
首先计算各种最小公倍数,然后用二分查找发现是否存在一个数k,使小于等于k的丑数个数是n

class Solution {
    private long gcd(long a, long b){
        long x;
        x = a % b;
        while(x!=0){
            a = b;
            b = x;
            x = a % b;
        }
        return b;
    }
    private long getUglyNumberNums(long k, long a, long b, long c, long ab, long bc, long ac, long abc){// 增函数
        long an = k/a, bn = k/b, cn = k/c, abn = k / ab, bcn = k / bc, acn = k / ac, abcn = k / abc;
        return an + bn + cn - abn - bcn - acn + abcn;
    }
    public int nthUglyNumber(long n, long a, long b, long c) {
        long ab, bc, ac, abc, t;
        long res=0,l,r;
        t = 0;
        ab = gcd(a,b);
        bc = gcd(b,c);
        ac = gcd(a,c);
        // 最小公倍数
        ab = a*b/ab;
        bc = b*c/bc;
        ac = a*c/ac;
        abc = ab*bc/gcd(ab,bc);
        l = 1;r = 2000000000;
        while(l<=r&&t!=n){
            res = (l+r)/2;
            t = getUglyNumberNums(res,a,b,c,ab,bc,ac,abc);
            if(t<n) l = res + 1;
            else if(t==n) break;
            else r = res - 1;
        }
        while(res%a!=0&&res%b!=0&&res%c!=0) res--;  // 往下找最后一个丑数
        return (int)res;
    }
}
2

力扣周赛 155 第四题题解

本题考察拓扑排序。拓扑排序是图论中的基本算法,其基本步骤是:

  • 以邻接表形式存储图,同时计算出每个点的入度。入度的计算可以在连边时顺带完成。
  • 将所有入度为 00。的点入队。
  • 对于队列中的每一个点,将其输出后出队,然后遍历以它为起点的每一条边,将对应终点的入度减去 11。如果终点的入度变为 00,则将终点入队。
  • 直到队列为空。

如果此时所有顶点都已经被输出,那么就得到了一个可行的拓扑序列。如果还有未被输出的顶点,代表图中一定有环(对应本题的无解情形)。

下面具体看这道题。

  • 任务被分成了若干组,每组内的任务必须相邻,这实际上提示我们要对组进行一个排序。
  • 每个任务有若干前置任务。这里需要考虑两种情形。
    1. 前置任务和当前任务在不同的组中。这就构成了两个任务组之前的拓扑关系。
    2. 前置任务和当前任务在同一个组中。这就构成了同一个任务组中两个任务间的拓扑关系。

由于还有一些任务是不成组的(组为 −1-1),我们进行预先处理,把这些任务当成只含有一个任务的组,以便后面进行统一处理。

根据上面的分析,我们知道,需要构建两个级别的图:

  1. 组级的,需要构建 11 个。
  2. 组内的,需要构建 m+km+k 个(kk 为不成组的任务的个数)

建立好图后,我们首先进行组级的拓扑排序,得到组的序列。
然后,我们对每一个组分别进行拓扑排序,得到组内的序列,并将其加入到最后的结果中。

如果任意一次拓扑排序没有成功进行(输出的点的数目少于点的总数),就说明无解,返回一个空数组。
如果全都顺利进行,我们就得到了一个可行的解。

思考 本题只要求给出一个可行解。如果要求给出一个字典序最小的解,需要对上述代码进行怎样的调整?

class Graph {
    unordered_map<int, vector<int>> adj;
    unordered_map<int, int> indegree;
public:
    Graph() {}
    
    Graph(int n) {
        adj = unordered_map<int, vector<int>>{};
        indegree = unordered_map<int, int>{};
        for (int i = 0; i < n; ++i) {
            indegree[i] = 0;
            adj[i] = vector<int>{};
        }
    }
    
    Graph(vector<int> &vec) {
        adj = unordered_map<int, vector<int>>{};
        indegree = unordered_map<int, int>{};
        for (const int &i : vec) {
            indegree[i] = 0;
            adj[i] = vector<int>{};
        }
    }
    
    void addEdge(int from, int to) {
        adj[from].push_back(to);
        indegree[to]++;
    }
    
    vector<int> sort() {
        queue<int> q;
        vector<int> ans;
        for (const auto &p : indegree) {
            if (p.second == 0) q.push(p.first);
        }
        
        int cnt = 0;
        while (!q.empty()) {
            int h = q.front();
            q.pop();
            ans.push_back(h);
            cnt++;
            for (const auto &i : adj[h]) {
                indegree[i]--;
                if (indegree[i] == 0) q.push(i);
            }
        }
        
        return ans;
    }
};

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItems(m, vector<int>{});
        for (int i = 0; i < n; ++i) {
            if (group[i] >= 0) groupItems[group[i]].push_back(i);
            else {
                // 单独的任务(不成组的),每一个单独放到一个组中。
                group[i] = groupItems.size();
                groupItems.push_back(vector<int>{i});
            }
        }
        
        Graph groupGraph = Graph(groupItems.size());
        vector<Graph> groupItemGraphs(groupItems.size());
        for (int i = 0; i < groupItems.size(); ++i) {
            groupItemGraphs[i] = Graph(groupItems[i]);
        }
        for (int i = 0; i < n; ++i) {
            for (const int &item : beforeItems[i]) {          
                int gi = group[i];
                if (gi == group[item]) {
                    // 前置任务在同一个组中,设置组内拓扑关系。
                    groupItemGraphs[gi].addEdge(item, i);
                } else {
                    // 前置任务在另一个组中,设置组间拓扑关系。
                    groupGraph.addEdge(group[item], gi);
                }
            }
        }

        vector<int> groupOrder = groupGraph.sort();
        vector<int> ans;
        if (groupOrder.size() < groupItems.size()) return ans;
        for (const int &i : groupOrder) {
            vector<int> order = groupItemGraphs[i].sort();
            if (order.size() < groupItems[i].size()) return vector<int>{};
            else for(const int &j : order) ans.push_back(j);
        }
        return ans;
    }
};
3

有大佬公布一下答案吗?

2

我太难了!!!!!!!!!

1

做的一脸懵比

1

class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
res = []
count = 0
for i in range(2,2*10^9):
if i % a == 0 or i % b == 0 or i % c == 0:
res.append(i)
count = count + 1
if count == n:
break
return res[n-1]

python 这样写为什么会出现索引超出限制的错误。。