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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-02-16

第一题:

题解略

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
展开全部 24 讨论