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

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 统计有序矩阵中的负数
5 分 - 最后 K 个数的乘积
5 分 - 最多可以参加的会议数目
6 分 - 多次求和构造目标数组

展开讨论
共 24 个讨论

第一题:

题解略

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (grid[i][j] < 0) {
                    ret++;
                }
            }
        }
        return ret;
    }
};

第二题:

第二题注意看数据条件

题目数据保证:任何时候,任一连续数字序列的乘积都在 32-bit 整数范围内,不会溢出。

也就是说,在任一连续数字序列中,要么存在 0 ,要么比 1 大的数不超过 31 个(最大是 2312^31 )

  • 解法一:

题目数据说了,0<=num<=1000<=num<=100,那么我们可以维护每个数字的个数前缀和,查询时,只需要求出后 k 个数字中,有多少个 0 ,有多少个 1 ,有多少个 2 ...,如果存在 0 ,直接返回 0 ,其他情况直接累乘比 1 大的数

class ProductOfNumbers {
public:
    
    vector<vector<int>> cache;
    
    ProductOfNumbers() {
        cache.clear();
        cache.push_back(vector<int>(101, 0));
    }
    
    void add(int num) {
        vector<int> t = cache[cache.size() - 1];
        t[num]++;
        cache.push_back(t);
    }
    
    int getProduct(int k) {
        vector<int> t = cache[cache.size() - 1];
        for (int i = 0;i <= 100;i++) {
            t[i] -= cache[cache.size() - 1 - k][i];
        }
        if (t[0] > 0) {
            return 0;
        }
        int ret = 1;
        for (int i = 2;i <= 100;i++) {
            for (int j = 0;j < t[i];j++) {
                ret *= i;
            }
        }
        return ret;
    }
};
  • 解法二:

上面代码需要开 n∗101n*101 的二维数组,其实除了判断 0 是否存在外,1可以直接丢掉,其他的数并不需要统计,只需要枚举出来即可

class ProductOfNumbers {
public:
    
    vector<vector<int>> cache;
    int lastZero;
    int index;
    
    ProductOfNumbers() {
        cache.clear();
        lastZero = -1;
        index = 0;
    }
    
    void add(int num) {
        if (num == 0) {
            lastZero = index;
        } else if (num > 1) {
            cache.push_back({index, num});
        }
        index++;
    }
    
    int getProduct(int k) {
        int n = index;
        if (lastZero >= n - k) {
            return 0;
        }
        int ret = 1;
        for (int i = (int)cache.size() - 1;i >= 0 && cache[i][0] >= n - k;i--) {
            ret *= cache[i][1];
        }
        return ret;
    }
};
  • 解法三:

前缀积,碰到 0 时清除前缀积,重新统计,这样不会出现除 0 的情况,也不会出现溢出的情况

class ProductOfNumbers {
public:
    
    vector<int> cache;
    
    ProductOfNumbers() {
        cache.clear();
        cache.push_back(1);
    }
    
    void add(int num) {
        if (num == 0) {
            cache.clear();
            cache.push_back(1);
        } else {
            cache.push_back(cache[cache.size() - 1] * num);
        }
    }
    
    int getProduct(int k) {
        int n = cache.size() - 1;
        if (n - k < 0) {
            return 0;
        } else {
            return cache[n] / cache[n - k];
        }
    }
};

第三题:

贪心题,当我们在分配时间 t 时,为了让选择的会议多一点,根据可行会议的结束时间,也就是区间的右端点排序,结束时间早的先分配。

既要判断区间的可行性,又要根据右端点选择区间分配,我们可以借助优先队列来解决这个问题

时间复杂度:o(nlogn)o(nlogn)

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        priority_queue<int, vector<int>, greater<int>> q;
        
        sort(events.begin(), events.end());
        int ret = 0;
        int last = 1;
        int i = 0;
        while (i < events.size() || q.size() > 0) {
            while (i < events.size() && events[i][0] == last) {
                q.push(events[i][1]);
                i++;
            }
            while (q.size() > 0 && q.top() < last) {
                q.pop();
            }
            if (q.size() != 0) {
                q.pop();
                ret++;
            }
            last++;
        }
        return ret;
    }
};

第四题:

顺着推肯定是没戏,我们考虑倒着推

按照题目意思,假设数组 [a1,a2,a3,...,an][a_{1},a_{2},a_{3},...,a_{n}] 的和是 s,那么这个 s 肯定比这数组里面任一个数都要大。不管替换成哪个数,生成出来的数组的最大值一定是 s 。

倒过来,假设数组 [b1,b2,b3,...,bn][b_{1},b_{2},b_{3},...,b_{n}] 是生成后的数组,那么最大值一定是上一轮的和

假设这个最大值是 p ,当前数组的和是 s ,那么上一轮的数组的和是 p ,这个最大值替换成 p - (s - p)

这个题的解法就是不断的将最大值还原,直到整个数组都变成了 1

这个解法是可以过的,那是因为 leetcode 的数据弱。

特殊用例:有大佬提出一个测试的测试用例,[1000000000, 1]

这个测试用例每一轮最大值只减 1 ,需要减 999999999 次才可以得到结果,会导致超时

优化方式:

我们回到刚才这个结论:

假设这个最大值是 p ,当前数组的和是 s ,那么上一轮的数组的和是 p ,这个最大值替换成 p - (s - p)

如果下一轮的最大值仍然是这一个,那么下一轮这个最大值仍然是减去上一轮的差值,因为这一轮的差值不变

我们假设数组中第二大的数为 p2p_{2} ,如果 p2=1p_{2}=1 ,我们只需要判断能否最大值不断减去 s - p 得到 1,否则,我们需要将最大值减到比 p2p_{2} 小,p−n∗(s−p)<p2p - n * (s - p) < p_{2}

化简可得:n>(p2−p)/(s−p)n > (p_{2} - p) / (s - p) 即,n=(p2−p)//(s−p)+1n = (p_{2} - p) // (s - p) + 1

也就是我们可以减 n 轮把最大值 p 减到比 p2p_{2} 小

n 轮后,最大值 p 替换成 p−n∗(s−p)p - n * (s - p),数组的和替换成 p−(n−1)∗(s−p)p - (n - 1) * (s - p)

class Solution {
public:
    bool isPossible(vector<int>& target) {
        if (target.size() == 1) {
            if (target[0] == 1) {
                return true;
            } else {
                return false;
            }
        }
        priority_queue<int> q;
        long long s = 0;
        for (int i = 0;i < target.size();i++) {
            q.push(target[i]);
            s += target[i];
        }
        while (1) {
            if (q.top() == 1) {
                return true;
            }
            long long p = q.top();
            q.pop();
            if (q.top() == 1) {
                if ((p - 1) % (s - p) == 0) {
                    return true;
                } else {
                    return false;
                }
            } else {
                long long n = (p - q.top()) / (s - p) + 1;
                long long x = p - (s - p) * n;
                s = p - (s - p) * (n - 1);
                if (x <= 0) {
                    return false;
                }
                q.push(x);
            }
        }
        return false;
    }
};

感谢评论区@hua_shuo,指出第四题不严谨的地方

19

感觉这次变难了。 T3 都那么难。 T4居然自己还没思路。

最后二十分钟AC了。 真是神助。

T1: 签到题
直接搜索或者用一个指针搜索都行。 数据范围很小, 随便过。

时间复杂度O(nm)O(nm) 或 O(n+m)O(n + m).
空间复杂度O(1)O(1)

T2:
这次的T2开始难度就有一些了。
因为数组中可能有0, 所以不能简单用前缀积来做。需要更改一下做法。
还是开前缀数组。 记录的是从上一个非0数到该数的乘积。
按照题意扫描。 每次碰到0则把前缀积变为1然后继续做。 记录最后一个0的位置, 当最后k个元素超过0的位置时可以直接输出0,否则用前缀数组来做。

时间复杂度O(n)O(n).
空间复杂度O(n)O(n)

T3:
这道题我没想到简单一点的算法。按天数采取一种贪心算法可以对。
考虑每一天, 因为一天只能参加一个会议。 所以如果那天有会议在召开, 则选择结束时间较早的会议。 这样可以使后面的天数中有更多选择, 答案不会变差。
因此, 维护当前正在召开的会议即可达到这个目的。 先把会议按照起始时间排序, 依次枚举每一天。 如果那一天恰好是某会议的开始时间则把它加入“当前正在召开的会议”。 然后从中选出一个离结束时间最近的来参加。
显然, 简单最标记会超时, 使用优先队列优化即可通过本题。

时间复杂度O(nlogn)O(nlogn).
空间复杂度O(n)O(n)

T4
做了T3再来做T4就感觉没那么难了。
考虑倒推法。 因为每个数都是正数, 所以数组的和必然大于每个数。 所以, 当我们得到一个操作后的数组可以还原到操作前的数组。

因此, 算法如下:

  1. 先找出最大的数。 若最大的数为1, 返回true.
  2. 将最大的数减去其他所有数之和。如果该数为0或者负, 返回false.
  3. 将原来最大的数用2中得到数替换。

@ottff 提出如果数据是[1e9, 1]的话, 会超时。 因此, 记录最大和次大数。 每一次看最大的数能够减多少次会比次大数小。 然后一并减掉就可以了。 这种一定要注意边界情况。

经过优化后, 每个数操作后一定会少于其原来的一半。 因此, 针对每个数的操作最多O(logV)O(logV)次, 因此不会超时。

时间复杂度O(nlog(max(ai)))O(nlog(max(a_i)))
空间复杂度O(1)O(1)

13

我真是佛了,第三题的意思原来是,参加会议不用从头听到尾,而是随便迟到早退,选一天去摸个鱼就可以直接跑路?

9

第四题应该增加数据
[1000000000,1]

8

T2 不同语言的超时标准有问题吧,有的语言暴力都可以过

6

第三题解法分享(贪心+优先队列)

5342. 最多可以参加的会议数目

这道题本来以为简单的贪心可以做,尝试了几次,发现总是不能处理某些情况的输入。最后发现还是得用优先队列结合贪心法来做。

优先队列的做法是模拟一个人的日程:第一天的时候,查看所有已经开始、还未参加的会议,找出其中将会最早结束的会议。注意一天只能参加一个会议。每一天都这样决策的话,最后就可以参加最多数量的会议。

那么,我们的优先队列中存储所有到当前日期为止的所有已经开始、还未参加的会议。当新的一天到来时,队列中加入新开始的会议;而这一天参加了某个会议,就将会议从队列中删除。

根据以上的分析,优先队列的排序条件是:按照会议的结束时间排序。而会议进入队列的顺序是按照会议的开始时间,所以在一开始需要对会议数组做一个排序。

代码如下:

public int maxEvents(int[][] events) {
    // 会议按照开始时间排序
    Arrays.sort(events, (e1, e2) -> Integer.compare(e1[0], e2[0]));

    // 优先队列按照结束时间排序
    PriorityQueue<int[]> pq = new PriorityQueue<>((e1, e2) -> Integer.compare(e1[1], e2[1]));

    int N = events.length;
    int i = 0;
    int d = 1;
    int count = 0;
    while (i < N || !pq.isEmpty()) {
        // 模拟第 d 天的决策
        // 将已经开始的会议加入队列
        while (i < N && events[i][0] <= d) {
            pq.add(events[i]);
            i++;
        }

        // 找出一个可以参加的最早结束的会议
        while (!pq.isEmpty()) {
            int[] e = pq.poll();
            if (e[1] >= d) {
                count++;
                break;
            }
        }
        d++;
    }

    return count;
}
4

我就想问一下 [2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,0,...] 能卡掉多少人,,,

你这数据也太不走心了

3

今天周赛第四题针对[1000000000,1]这个测试用例,预期结果有错误 @LeetCode。如下图:
image.png

2

第三题输入[[1,2],[1,2],[3,3],[1,5],[1,5]]
为什么么是5天那 一直卡在这;
Untitled.png

1