On the shoulders of giants.

weekly-contest-176

统计有序矩阵中的负数

给你一个 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

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -100 <= grid[i][j] <= 100
题解

直接遍历,也可以用单调性,但时间复杂度不变,所以还是写简单一点。

时间复杂度:\(O(nm)\)

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

最后 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 

提示:

  • addgetProduct 两种操作加起来总共不会超过 40000 次。
  • 0 <= num <= 100
  • 1 <= k <= 40000
题解

直接开数组存放 \(O(1)\) ,然后枚举算出结果 \(O(k)\) 。

class ProductOfNumbers {
public:
    vector<int> nums;
    ProductOfNumbers() {}
    
    void add(int num) {
        nums.push_back(num);
    }
    
    int getProduct(int k) {
        int n = nums.size(), sum = 1;
        for(int i = k; 1 <= i; i--) {
            sum *= nums[n - i];
        }
        return sum;
    }
};

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

最多可以参加的会议数目

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

你可以在满足 startDayi <= d <= endDayi中的任意一天 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

提示:

  • 1 <= events.length <= 10^5
  • events[i].length == 2
  • 1 <= events[i][0] <= events[i][1] <= 10^5
题解

贪心:如果要在某一天选出一个会议参加,无疑是选已开始且最快到结束的会议,这样才会提供更多其他会议以后的选择机会。

于是,我们维护某一天能够参加的会议(已开始,未结束),然后选出结束时间最小的会议参加。

于是我们枚举每一天,然后用小根堆维护结束时间。

时间复杂度:\(O(n\log m)\) ,n 为天数, m 为平均每天能参加的会议数。

const int N = 1E5 + 10;
class Solution {
public:
    priority_queue<int> pq;
    vector<int> index[N];
    int maxEvents(vector<vector<int>>& events) {
        int lim = 0, count = 0;
        for(int i = 0; i < events.size(); i++) {
            index[events[i][0]].push_back(i);
            lim = max(lim, events[i][1]);
        }
        for(int i = 1; i <= lim; i++) {
            for(auto x : index[i]) {
                pq.push(-events[x][1]);
            }
            while(!pq.empty() && -pq.top() < i) {
                pq.pop();
            }
            if(!pq.empty()) {
                pq.pop();
                count++;
            }
        }
        return count;
    }
};

多次求和构造目标数组

给你一个整数数组 target 。一开始,你有一个数组 A ,它的所有元素均为 1 ,你可以执行以下操作:

  • 令 x 为你数组里所有元素的和
  • 选择满足 0 <= i < target.size 的任意下标 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

提示:

  • N == target.length
  • 1 <= target.length <= 5 * 10^4
  • 1 <= target[i] <= 10^9
题解

数学:在数组中,最大的数是更改前所有数的和,我们假设 x 为数组中最大值,y 为数组中次大值,s 为数组中数的总和。

假设 \(1 < y\) ,即恢复后不可能是目标状态:

恢复后数 x 变成 x-(s-x) ,但如果恢复后最大值还是这个位置的值,我们还要执行 -(s-x)

可以发现 s-x 是一个定值,所以我们的目标是,让 x 变成比 y 小的数,用不等式表示就是:\(x-k(s-x) < y\)

得 \(k=\frac{x-y}{s-x}+1\) 。

如果 \(y == 1\) ,即恢复后是最后的状态:

我们要验证恢复后的状态是否为目标状态,即 \(x-k(s-x)=y,k\in Z\)

我们用大根堆维护数组,然后更新。

时间复杂度:\(O(n\log s)\)

class Solution {
public:
    bool isPossible(vector<int>& target) {
        priority_queue<long long> tree;
        long long sum = 0;
        for(auto x : target) {
            tree.push(x);
            sum += x;
        }
        if(tree.size() == 1) return tree.top() == 1;
        while(tree.top() != 1) {
            long long x = tree.top();
            tree.pop();
            long long y = tree.top();
            if(y == 1) {
                return (x - y) % (sum - x) == 0;
            }
            long long k = (x - y) / (sum - x) + 1;
            long long old = x;
            x = x - k * (sum - x);
            if(x < 1) return false;
            sum = sum - old + x;
            tree.push(x);
        }
        return true;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注