专栏首页GiantPandaCVLeetCode第166场周赛题解

LeetCode第166场周赛题解

前言

这是LeetCode的第166场周赛的题解,不出意外的又爆炸了,前三题只做了20分钟,第4题因为题意读错了耽误了40分钟,到1小时15分钟左右才写完。排名直接100开完,不过这次倒是一次错误都没有,4份代码都AC了。可惜啦这把。

整数的各位积和之差

  • 题意:给你一个整数 n,请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
  • 数据范围:1 <= n <= 10^5
  • 思路:直接模拟。
  • 复杂度:O(1)
  • 代码:
class Solution {
public:
    int subtractProductAndSum(int n) {
        vector <int> v;
        while(n){
            v.push_back(n%10);
            n/=10;
        }
        int a=1,b=0;
        for(int i=0; i<v.size(); i++){
            a*=v[i];
            b+=v[i];
        }
        return a-b;
    }
};

用户分组

  • 题意:有 位用户参加活动,他们的 ID 从 到 ,每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 ,其中包含每位用户所处的用户组的大小,请你返回用户分组情况(存在的用户组以及每个组中用户的 ID)。你可以任何顺序返回解决方案,ID 的顺序也不受限制。此外,题目给出的数据保证至少存在一种解决方案。
  • 数据范围:
  • 思路:统计一下每个组的人数,开一个维的vector,表示用户所处用户组大小为的用户编号,然后对于,我们把这里面每个分成一组就做完了。
  • 复杂度:O(n)
  • 代码:
class Solution {
public:
    vector <int> v[510];
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        for(int i=0; i<510; i++) v[i].clear();
        int n = groupSizes.size();
        for(int i=0; i<n; i++){
            v[groupSizes[i]].push_back(i);
        }
        vector <vector<int> >ans;
        for(int i=1; i<=n; i++){
            int cnt = 0;
            vector <int> tmp;
            for(int j=0; j<v[i].size(); j++){
                tmp.push_back(v[i][j]);
                cnt++;
                if(cnt==i){
                    ans.push_back(tmp);
                    tmp.clear();
                    cnt=0;
                }
            }
        }
        return ans;
    }
};

使结果不超过阈值的最小除数

  • 题意:给你一个整数数组 nums 和一个正整数 threshold ,你需要选择一个正整数作为除数,然后将数组里每个数都除以它,并对除法结果求和。请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。每个数除以除数后都向上取整,比方说 7/3 = 3 , 10/2 = 5 。题目保证一定有解。
  • 数据范围:
  • 思路:二分,因为函数显然是具有单调性的。
  • 复杂度:O(nlogS),S为二分的上界
  • 代码:
class Solution {
public:
    bool check(int x, vector <int>v, int thres){
        int ans=0;
        for(int i=0; i<v.size(); i++){
            int t = v[i]/x;
            if(v[i]%x!=0) t+=1;
            ans+=t;
            if(ans>thres) return false;
        }
        return true;
    }
    int smallestDivisor(vector<int>& nums, int threshold) {
        int l=1, r=1e9;
        int ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid, nums, threshold)){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return ans;
    }
};

转化为全零矩阵的最少反转次数

  • 题意:给你一个 m x n 的二进制矩阵 mat。每一步,你可以选择一个单元格并将它反转(反转表示 0 变 1 ,1 变 0 )。如果存在和它相邻的单元格,那么这些相邻的单元格也会被反转。(注:相邻的两个单元格共享同一条边。)请你返回将矩阵 mat 转化为全零矩阵的最少反转次数,如果无法转化为全零矩阵,请返回 -1 。二进制矩阵的每一个格子要么是 0 要么是 1 。全零矩阵是所有格子都为 0 的矩阵。
  • 数据范围:1<=n,m<=3。
  • 思路:由于n, m特别小直接BFS爆搜就可以了。最开始以为是高斯消园来着,样例错了很久才反应过来。。。
  • 代码:
class Solution {
public:
    struct node{
        int n, m, step;
        vector <int> v;
        node(){}
        node(int n_, int m_, int step_, vector<int>v_):n(n_),m(m_),step(step),v(v_){}
    };
    int dir[4][2]={{0, 1},{0, -1}, {1, 0}, {-1, 0}};
    int minFlips(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        map <vector<int>, bool>vis;
        queue <node> q;
        node now;
        now.n=n, now.m=m, now.step=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                now.v.push_back(mat[i][j]);
            }
        }
        q.push(now);
        vis[now.v]=1;
        int ans = -1;
        int a[3][3]={0};
        while(q.size()){
            now = q.front();
            q.pop();
            bool flag = true;
            for(int i=0; i<n*m; i++){
                if(now.v[i]>0){
                    flag = false;
                }
            }
            if(flag){
                ans = now.step;
                break;
            }
            //printf("%d\n", now.step);
            node nex;
            nex.n = n, nex.m = m;
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    a[i][j] = now.v[i*m+j];
                }
            }
            int b[3][3]={0};
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    memset(b, 0, sizeof(b));
                    for(int x=0; x<n; x++){
                        for(int y=0; y<m; y++){
                            b[x][y]=a[x][y];
                        }
                    }
                    b[i][j]=a[i][j]^1;
                    for(int k=0; k<4; k++){
                        int tx = i+dir[k][0], ty = j+dir[k][1];
                        if(tx>=0&&tx<n&&ty>=0&&ty<m){
                            b[tx][ty]=a[tx][ty]^1;
                        }
                    }
                    nex.v.clear();
                    for(int x=0; x<n; x++){
                        for(int y=0; y<m; y++){
                            nex.v.push_back(b[x][y]);
                        }
                    }
                    if(!vis[nex.v]){
                        nex.step=now.step+1;
                        vis[nex.v]=1;
                        q.push(nex);
                    }
                }
            }
        }
        return ans;
    }
};

后记

连续爆炸,我顶不住了。。。

本文分享自微信公众号 - GiantPandaCV(BBuf233),作者:BBuf

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • OpenCV图像处理专栏十一 | IEEE Xplore 2015的图像白平衡处理之动态阈值法

    这是OpenCV图像处理专栏的第十一篇文章,之前介绍过两种处理白平衡的算法,分别为灰度世界算法和完美反射算法。今天来介绍另外一个自动白平衡的算法,即动态阈值法,...

    BBuf
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf
  • Leetcode 第 167 场周赛题解

    BBuf
  • 【POJ1456】Supermarket(贪心)

    每个商品有过期日期和价格,每天可以卖一个商品,必须在过期前出售才能收益,求最大收益。

    饶文津
  • C++初始化

    Qt君
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事
  • 【Sichuan 2017D】Dynamic Graph

    300个点的无环图,开始都是白色,每次改变某个节点的颜色(黑/白),问有多少对白点之间存在只有白点的路径。

    饶文津
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack
  • BZOJ2754: [SCOI2012]喵星球上的点名(AC自动机)

    attack
  • 2843 拯救炜哥

    2843 拯救炜哥 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有一天,炜...

    attack

扫码关注云+社区

领取腾讯云代金券