周赛 – 176

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

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

代码

viv丑陋版

看到数据范围我选择直接全部遍历一遍数负数个数

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

zz美丽版

我的上帝!瞧瞧这优美的三行代码!

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int ans = 0;
        for(auto row: grid) for(auto v: row) if(v < 0) ans++;
        return ans;
    }
};

2. 最后 K 个数的乘积

请你实现一个「数字乘积类」ProductOfNumbers,要求支持下述两种方法:
1. add(int num)
将数字 num 添加到当前数字列表的最后面。

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

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

样例

示例 1:

输入:
[“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

提示

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

代码

viv丑陋版

看到题目第一眼想到前缀积
然后发现刚才太无脑了,如果遇到0会很麻烦。
所以我处理了一下。首先为了避免前缀积数组里出现0,在添加元素更新前缀积数组时,我将该数组位的值设置为1,重新开始计算前缀积。
其次,在计算倒数k个数字的积时,我为了方便添加了一个zero数组,用来计算截至该位0的数目,这样可以用来计算指定区间内是否存在0,如果存在,答案直接返回0。

class ProductOfNumbers {
private:
    int pro[40005];
    int zero[40005];
    int tot;
public:
    ProductOfNumbers() {
        tot = 0;
        pro[0] = 1;
        zero[0] = 0;
    }
    
    void add(int num) {
        ++tot;
        if(num == 0) {
            pro[tot] = 1;
            zero[tot] = zero[tot - 1] + 1;
        }
        else {
            pro[tot] = pro[tot - 1] * num;
            zero[tot] = zero[tot - 1];
        }
    }
    
    int getProduct(int k) {
        if(zero[tot] - zero[tot - k] != 0) return 0;
        return pro[tot] / pro[tot - k];
    }
};
/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

zz美丽版

zz和我的想法完全不一样。
他是根据题目中说数据不会爆int来推算,如果我们省略掉所有不会对结果造成影响的1,乘法操作的次数不会很多。
先使用vector<pair<int, int>>来依次记录添加进来的数字及其数目,如果遇到非1数字直接添加(num, 1),否则,如果遇到1,添加(1, 连续1的数目)。
在计算乘积的过程中直接暴力,遇到1跳过。

class ProductOfNumbers {
public:
    vector<pair<int, int>> storage;
    ProductOfNumbers() {
        storage.clear();
    }
    
    void add(int num) {
        if(storage.size() == 0 || num != 1) storage.push_back(make_pair(num, 1));
        else {
            if(storage.back().first != 1) storage.push_back(make_pair(num, 1));
            else {
                int cnt = storage.back().second + 1;
                storage.pop_back();
                storage.push_back(make_pair(num, cnt));
            }
        }
    }
    
    int getProduct(int k) {
        int n = storage.size(), ret = 1;
        for(int i=n-1; i>=0 && k>0; i--) {
            if(storage[i].first == 0) return 0;
            if(storage[i].first == 1) k -= storage[i].second;
            else {
                k -= 1;
                ret *= storage[i].first;
            }
        }
        return ret;
    }
};
/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

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

给你一个数组 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 <= eventsi <= eventsi <= 10^5

代码

viv丑陋版

经过接近1h的挣扎我放弃治疗了……
我知道是贪心,可我怎么都贪不明白……

zz美丽版

首先将所有会议按照开始时间递增排序,然后逐天遍历。
对于每一天,将时间符合要求的会议放入按照结束时间递减自动排序的优先队列,将时间不符合要求的会议弹出,并弹出一个元素作为当天开的会。

const int MAXN = 1e5 + 5;
struct Event {
    int start, end;
    Event() {}
    Event(int s0, int e0) {
        start = s0;
        end = e0;
    }
    bool operator < (const Event& b) const {
        return end > b.end;
    }
} event[MAXN];

priority_queue<Event> que;
bool cmp(const Event &a, const Event &b) {
    return a.start < b.start;
}
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int n = events.size(), ans = 0;
        int mn = events[0][0], mx = events[0][6];

        for(int i=0; i<n; i++) {
            event[i] = Event(events[i][0], events[i][7]);
            mn = min(mn, events[i][0]);
            mx = max(mx, events[i][8]);
        }
        sort(event, event+n, cmp);
        while(!que.empty()) que.pop();
        for(int i=mn, j=0; i<=mx; i++) {
            while(j<n && event[j].start <= i) {
                que.push(event[j]);
                j++;
            }
            while(!que.empty() && que.top().end<i) que.pop();
            if(!que.empty()) {
                ans++;
                que.pop();
            }
        }
        return ans;
    }
};

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

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

代码

viv丑陋版

viv没打比赛也不会做。

zz美丽版

正向考虑有些麻烦,可以反向倒推
假设在最后一次操作之前局面为和为$rest$的一堆数字和一个$x$,假设此时$rest+x=pre_sum$。那么我们的最后一步操作就是将$x$的值改为$pre_sum$,假设$rest+pre_sum=cur_sum$。
很显然,$cur_sum$是可以求得的,在最后一步操作过后,它应该为所有数字的和。$pre_sum$也很简单,应该是所有数字中最大的那个,我们可以维护一个优先队列来实现快速存取。
综上,我们可以算出$rest$的值,并进一步推得$x$的值。其他局面同理,在操作过程中如果某个数小于1,就不行。

typedef long long LL;
class Solution {
public:
    bool isPossible(vector<int>& target) {
        priority_queue<LL> que;
        int n = target.size();
        long long sum = 0;
        for(auto v: target) que.push(v), sum += v;
        while(sum > n) {
            LL cur = que.top(); que.pop();
            LL rest = sum - cur;
            LL pre = cur - rest;
            if(rest < 1 || pre < 1) return false;
            sum = cur;
            que.push(pre);
        }
        return true;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇