LeetCode2020第176场周赛

5340. 统计有序矩阵中的负数

题目描述

给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列。 

请你统计并返回 grid 中 负数 的数目。

 

示例 1:

输入:grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出:8
解释:矩阵中共有 8 个负数。

示例 2:

输入:grid = [[3,2],[1,0]]
输出:0

示例 3:

输入:grid = [[1,-1],[-1,-1]]
输出:3

示例 4:

输入:grid = [[-1]]
输出:1

题解

遍历二维数组,统计负数的个数即可。
时间复杂度为:O(n^2)
空间复杂度为:O(1)

代码

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int cnt = 0;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(grid[i][j] < 0){//统计负数的个数
                    ++cnt;
                }
            }
        }
        return cnt;
    }
};

5341. 最后 K 个数的乘积

题目描述

请你实现一个「数字乘积类」ProductOfNumbers,要求支持下述两种方法:

1. add(int num)

  • 将数字 num 添加到当前数字列表的最后面。

2. getProduct(int k)

  • 返回当前数字列表中,最后 k 个数字的乘积。
  • 你可以假设当前列表中始终 至少 包含 k 个数字。

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

 

示例:

输入:
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

输出:
[null,null,null,null,null,null,20,40,0,null,32]

解释:
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // 返回  0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32 

 

题解1

周赛的时候没有多想,上来直接用vector来存储所有的数,add函数用push_back来实现。最后k个元素乘积直接从vector的最后一个元素开始,将k个元素乘起来即可。

时间复杂度为:O(n)
空间复杂度为:O(n)

代码1

class ProductOfNumbers {
public:
    vector<int>vec;
    ProductOfNumbers() {

    }

    void add(int num) {
        vec.push_back(num);
    }

    int getProduct(int k) {
        int len = vec.size(), res = 1;
        for(int i = len - 1; i >= len - k; --i){
            res = res * vec[i];
        }
        return res;
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

题解2

参照LeetCode – 圈子,对于第二题给出了许多优化的算法。题目中给出的限制条件需要注意。

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

对于任一连续序列的乘积都小于32位整数范围,表示序列中最多只有31个数大于1(2^{31} – 1),其它数字都是0和1。所以可以用前缀和来统计0-100这101个数字在序列中出现的个数,这里空间开销是101 * n(n是序列的总长度)。计算最后K个数的乘积,只需要先找出每个数字num出现的次数cnt,cnt_{num} = vec[n][num] – vec[n – k][num],出现0,最后乘积就为0,出现1,则跳过1不算。然后再求其它数字乘积即可。

这里我介绍前缀积的思路。数组存储连续数字的乘积,遇到0,清除数组,重新统计。当最后数组长度不足K时,表示乘积为0,否则就用总乘积除以前面元素的乘积。
时间复杂度为:O(1)
空间复杂度为:O(n)

代码2

class ProductOfNumbers {
public:
    vector<int>vec;
    ProductOfNumbers() {
        vec.clear();
        vec.push_back(1);
    }

    void add(int num) {
        if(num == 0){//遇到0,清空前缀积数组
            vec.clear();
            vec.push_back(1);
        }
        else{
            vec.push_back(vec.back() * num);
        }
    }  
    int getProduct(int k) {
        if(vec.size() - 1 < k){//数组长度不足K表示,最后K个数中存在0
            return 0;
        }
        else{
            return vec[vec.size() - 1] / vec[vec.size() - 1 - k];
        }
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

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

题目描述

给你一个数组 events,其中 events[i] = [startDayi, endDayi] ,表示会议 i 开始于 startDayi ,结束于 endDayi 。

你可以在满足 startDayi i 中的任意一天 d 参加会议 i 。注意,一天只能参加一个会议。

请你返回你可以参加的 最大 会议数目。

 

示例 1:

输入:events = [[1,2],[2,3],[3,4]]
输出:3
解释:你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。

示例 2:

输入:events= [[1,2],[2,3],[3,4],[1,2]]
输出:4

示例 3:

输入:events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
输出:4

示例 4:

输入:events = [[1,100000]]
输出:1

示例 5:

输入:events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
输出:7

题解

贪心+优先队列
首先将区间按开始时间进行排序,然后结束时间早的先安排。还需要鼗安排冲突,不合理的去掉。
时间复杂度为:O(nlogn)
空间复杂度为:O(n)

代码

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        priority_queue<int, vector<int>, greater<int>>que;
        int cnt = 0, idx = 1, i = 0;
        //先排序
        sort(events.begin(), events.end());
        while(i < events.size() || que.size() > 0){
            while(i < events.size() && events[i][0] == idx){//开始时间为idx的,均添加到优先队列
                que.push(events[i][1]);
                ++i;
            }
            while(que.size() > 0 && que.top() < idx){//去除安排冲突的
                que.pop();
            }
            if(que.size() > 0){//优先安排结束时间早的
                ++cnt;
                que.pop();
            }
            ++idx;
        }
        return cnt;
    }
};

5343. 多次求和构造目标数组

题目描述

给你一个整数数组 target 。一开始,你有一个数组 A ,它的所有元素均为 1 ,你可以执行以下操作:
  • 令 x 为你数组里所有元素的和
  • 选择满足 0  的任意下标 i ,并让 A 数组里下标为 i 处的值为 x 。
  • 你可以重复该过程任意次

如果能从 A 开始构造出目标数组 target ,请你返回 True ,否则返回 False 。

 

示例 1:

输入:target = [9,3,5]
输出:true
解释:从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ,选择下标 1
[1, 3, 1], 和为 5, 选择下标 2
[1, 3, 5], 和为 9, 选择下标 0
[9, 3, 5] 完成

示例 2:

输入:target = [1,1,1,2]
输出:false
解释:不可能从 [1,1,1,1] 出发构造目标数组。

示例 3:

输入:target = [8,5]
输出:true

题解

正向思考,不知道用所有的数字之和去替换哪一个数字,尝试的话可能性太多,实现难度太大。反向思考的话,数组中最大的数字显然是上一个数组中所有数字之和,而它所替换的数字等于最大的数字减去其它数字之和。如此替换下去,如果最后所有的数字都为1,表示可以构造目标数组,一旦出现数字0或负数,表示不能构造。

代码

class Solution {
public:
    bool isPossible(vector<int>& target) {
        long long int sum = 0;
        int rep_num = 0;
        bool flag = true;
        priority_queue<int>que;
        for(int i = 0; i < target.size(); ++i){
            sum += target[i];
            que.push(target[i]);
        }
        while(que.top() != 1){
            sum = sum - que.top();//除去最大数字其它数字之和
            if(sum == 1){
                flag = true;
                break;
            }
            /*
            这里用除法而不用减法是为了处理像[100000, 1]这样的例子超时的问题
            用除法,直接使当前的最大数字小于其它数字之和,避免多轮最大数字都是同一个。
            */
            if(que.top() / sum == 0 || (que.top() % sum == 0)){//出现负数和0
                flag = false;
                break;
            }
            else{
                que.push(que.top() % sum);
                sum = sum + que.top() % sum;//上一个数组的所有元素之和
                que.pop();
            }
        }
        if(flag){
            return true;
        }
        else{
            return false;
        }
    }
};

转载请注明:Onwaier‘s Blog » LeetCode2020第176场周赛