Leetcode 2020年2月周赛题解

2020-02-16 14:59 CST

2020-02-16 14:59 CST

Contest 174

2月最简单的一场周赛,不提了

Contest 175

检查整数及其两倍数是否存在

题意:给定一个数组,检查数组中是否存在两个数恰好一个是另一个的两倍

题解:类似两数和,一个哈希表搞定

制造字母异位词的最小步骤数

给你两个长度相等的字符串 s 和 t。每一个步骤中,你可以选择将 t 中的 任一字符 替换为 另一个字符。找到使 t 成为 s 的字母异位词的最小步骤数。

题解:比较字母计数即可,s中出现的+1,t中的-1

推文计数

请你实现一个能够支持以下两种方法的推文计数类 TweetCounts:

  1. recordTweet(string tweetName, int time): 记录推文发布情况:用户 tweetName 在 time(以 秒 为单位)时刻发布了一条推文。
  2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime): 返回从开始时间 startTime(以 秒 为单位)到结束时间 endTime(以 秒 为单位)内,每 分 minute,时 hour 或者 日 day (取决于 freq)内指定用户 tweetName 发布的推文总数。

freq 的值始终为 分 minute,时 hour 或者 日 day 之一,表示获取指定用户 tweetName 发布推文次数的时间间隔。 第一个时间间隔始终从 startTime 开始,因此时间间隔为 $[startTime, startTime + delta1>,  [startTime + delta1, startTime + delta2>, [startTime + delta2, startTime + delta3>, ... , [startTime + deltai, min(startTime + delta*(i+1), endTime + 1)>$,其中 i 和 delta(取决于 freq)都是非负整数。

题解:可以将每个用户的推文时间存储方式换成更有效的平衡二叉树。在查询时只要先在对应用户的所有推文中查询时间范围的上下界,然后在上下界范围内遍历推文发布时间即可。(实际上使用set即可)

class TweetCounts {
    map<string, set<int>> user;
public:
    TweetCounts() {
    }
    
    void recordTweet(string tweetName, int time) {
        user[tweetName].insert(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int length = 0;
        if (freq == "minute")
            length = 60;
        else if (freq == "hour")
            length = 60 * 60;
        else
            length = 60 * 60 * 24;
        vector<int> ans((endTime - startTime) / length + 1);
        auto begin = user[tweetName].lower\_bound(startTime);
        auto end = user[tweetName].upper\_bound(endTime);
        for (; begin != end; ++begin) {
            ++ans[(*begin - startTime) / length];
        }
        return ans;
    }
};

参加考试的最大学生数

题意:给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的(不可用),就用 '#' 表示;否则,用 '.' 表示。 学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷,但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。学生必须坐在状况良好的座位上。

题解: 方法1[https://leetcode-cn.com/problems/maximum-students-taking-exam/solution/er-fen-tu-zui-da-du-li-ji-by-lightcml/]:只关心可以坐人的座位,我们把作为按照列下标的奇偶建二分图,S向奇数下标的座位连边,偶数下标的座位向T连边,有冲突的座位奇数座位向偶数座位连边。图中所有边流量都是1。直接跑二分图最大点独立集就行,即可以坐人的座位数-最大流。

方法2:DP+记忆化

class Solution {
    int memory[8][1 << 8];
    vector<int> compressed\_seats;
    int f(int X, int row\_num, int width) {
        if (memory[row\_num][X] != -1)
            return memory[row\_num][X];
        int ans = 0;
        for (int scheme = 0; scheme != (1 << width); ++scheme) {
            if (scheme & ~X || scheme & (scheme << 1))
                continue;
            int curans = 0;
            for (int j = 0; j != width; ++j)
                if ((1 << j) & scheme)
                    ++curans;
            if (row\_num == compressed\_seats.size() - 1)
                ans = max(ans, curans);
            else {
                int next\_seats = compressed\_seats[row\_num + 1];
                next\_seats &= ~(scheme << 1);
                next\_seats &= ~(scheme >> 1);
                ans = max(ans, curans + f(next\_seats, row\_num + 1, width));
            }
        }
        memory[row\_num][X] = ans;
        return ans;
    }
    
    int compress(vector<char>& row) {
        int ans = 0;
        for (char c : row) {
            ans <<= 1;
            if (c == '.')
                ++ans;
        }
        return ans;
    }

public:
    int maxStudents(vector<vector<char>>& seats) {
        for (int i = 0; i != seats.size(); ++i)
            for (int j = 0; j != (1 << seats[0].size()); ++j)
                memory[i][j] = -1;
        for (auto row: seats)
            compressed\_seats.push\_back(compress(row));
        return f(compressed\_seats[0], 0, seats[0].size());
    }
};

https://leetcode-cn.com/problems/maximum-students-taking-exam/solution/can-jia-kao-shi-de-zui-da-xue-sheng-shu-by-leetcod/

Contest 176

相对难一点的一次周赛

统计有序矩阵中的负数

题意:一个矩阵,每行每列都非降序排列,找出矩阵内的负数个数

解法:行顺序,列倒序遍历,时间复杂度$O(m)$,空间复杂度$O(1)$

最后 K 个数的乘积

题意:设计一个类,含有两个函数与一个构造函数,构造出一个数字列表后,可以调用addNum函数来添加数到数字列表最后,也可以调用getProduct(int k)来获取最后k个数的乘积,已知这两个函数的调用次数和不超过40000次,可以保证数字列表中任意k数的乘积都不会超过32-bits范围

题解:直接考虑维护一个前缀积 $pre[i]$ 表示前 i 个数的乘积即可,然后遇0则将整个数组清零,维护数组长度,求最后k个数的乘积的时候,只需要先考虑数组长度是否达到了k,否则返回0(因为这意味着最后k个数中含有0)。如果达到了返回$pre[n]/pre[n-k]$即可(n为数组长度)

最多可以参加的会议数目

题意:多个会议,给出每个会议的开始时间与结束时间,每天只能参加一个会议,但是每个会议可以只参加其中的某几天或1天,请问最多能参加多少个会议。

题解:贪心,选择end尽可能早的会议参加

多次求和构造目标数组

题意:给你一个整数数组 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] 完成

题解:我们正向难以解决的时候,可以考虑使用逆向的方式进行思考。我们可以考虑是否能从目标数组得到全1数组,我们发现,最后一次操作生成的数是之前所有数的和所以必然是最大的,即原数为$maxn-(sum-maxn)$.这样只要能倒推回全1数组就返回true。但是这种情况会在$[1,1000000]$此类的测试用例下可能超时,所以可以考虑减去多次,即倒退一次后仍为最大继续倒退这个数的情况,这种情况下,每次倒退幅度都是其他数的和$maxn-(sum-maxn)$,我们只要考虑一次减去k个幅度使得最大数比第二大的数小或者为1即可(分类讨论下即第二大的是否为1).

注意整数的溢出,注意边界情况

bool isPossible(vector<int>& target) {
        priority\_queue<int>q;
        long long sum=0;
        if(target.size()==1){
            if(target[0]==1)return true;
            return false;
        }
        for(auto x:target){q.push(x);sum+=(long long)x;}
        while(q.top()>1){
            long long maxn =(long long) q.top();q.pop();
            long long secMax =(long long) q.top();
            long long k;
            if(secMax == 1){
                k=(maxn-1+sum-maxn-1)/(sum-maxn);
            }else{
                k=(maxn-secMax)/(sum-maxn)+1;
            }
            long long delta = k*(sum-maxn);
            sum-=delta;
            maxn-=delta;
            if(maxn<=0) return false;
            q.push((int)maxn);
        }
        return true;
    }

Contest 177

非常简单的一次,可惜我白痴了一下(

日期之间隔几天

题目:给定两个日期,求解日期差多少天

题解:由于限制了范围,可以全部以0000-01-01作为起点或者1971-01-01作为起点,然后再相减就可以

验证二叉树

题目:给定两数组,$left[i]$表示节点i的左子节点序号,对应的有right数组,验证是否是二叉树且只有一棵。

题解: 对于一个包含 n 个节点 m 条边的无向图,如果它是一棵树,那么必须满足以下三个条件中的两个:边数 = 点数 - 1;该无向图连通;该无向图无环。 第一点通过统计-1个数即可,第二点可以利用搜索遍历的方式进行,第三点可用并查集检查。

最接近的因数

题意:给定一个数x,求x+1和x+2中因数最接近的一对。如给定x=4,最接近的一对就是(2,3)

题解:暴力每一次从平方根递减即可,注意及时跳出循环

形成三的最大倍数

题意:给一个数组里面的数,你对其选择其中的一部份数进行组合成一个字符串,使得组合出来的字符串代表的数字尽可能大并为3的倍数

考虑3的余数,要最大肯定时位数最多,那么我们就要尽可能的保留多的数字,只需要考虑如何将全部的数相加后的和减少尽量少的数字使其能够维持在3的倍数即可。考虑余数即可。

class Solution {
    vector<int> a[3],b;
    string ans;
public:
    string largestMultipleOfThree(vector<int>& digits) {
        int s=0,i;
        for(i=0;i<3;i++)a[i].clear();
        b.clear();
        for(auto c:digits)
        {
            s+=c;
            a[c%3].push\_back(c);
        }
        for(i=0;i<3;i++)sort(a[i].begin(),a[i].end(),greater<int>());
        if(s%3)if(!a[s%3].empty())a[s%3].pop\_back();
        else for(i=0;i<2;i++)a[s%3^3].pop\_back();
        for(i=0;i<3;i++)for(auto c:a[i])b.push\_back(c);
        sort(b.begin(),b.end(),greater<int>());
        ans="";
        if(b.empty()||b.front())for(auto c:b)ans+=c^'0';
        else ans="0";
        return ans;
    }
};