专栏首页算法修养LeetCode Contest 166

LeetCode Contest 166

LeetCode Contest 166

第一次知道LeetCode 也有比赛。

很久没有打过这种线上的比赛,很激动。

直接写题解吧

第一题

很弱智

class Solution {
public:
    int subtractProductAndSum(int n) {
        
        int num1=0;
        int num2=1;
        
        while(n)
        {
            int x = n%10;
            num1+=x;
            num2*=x;
            n/=10;
        }
        
   
        
        return num2-num1;
        
        
        
    }
};

第二题 也很简单的,我先排个序。

但是在用c++的快排的时候,被坑了,我一直的习惯是写自定义比较函数,没有写运算符重载,不知道为什么一直RE,浪费了挺多时间

 struct Node
    {
        int value;
        int index;
        Node(){}
        Node(int value,int index)
        {
            this->value = value;
            this->index = index;
        }
      bool operator <(const Node &x)const
    {
        return value<x.value; 
    }
    };


class Solution {
public:
    int vis[1005];
    Node a[1005];
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int len = groupSizes.size();
        
        for(int i=0;i<len;i++)
        {
            a[i] = Node(groupSizes[i],i);
        }
        sort(a,a+len);
        vector<vector<int>> ans;
        
        vector<int> res;
        res.push_back(a[0].index);
        int num=0;
        for(int i=1;i<len;i++)
        {
            
            if(a[i].value==a[i-1].value)
            {
                if(res.size()==a[i].value)
                {
                    ans.push_back(res);
                    res.clear();
                    res.push_back(a[i].index);
                    continue;
                }
                res.push_back(a[i].index);
            }
            else
            {
                ans.push_back(res);
                res.clear();
                res.push_back(a[i].index);
            }
        }
        
        if(res.size()!=0)
        {
            ans.push_back(res);
        }
        
        return ans;
        
    }
    
   
};

第三题

二分,一次过,没有怎么浪费时间

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        
        int num=0;
        for(int i=0;i<nums.size();i++)
        {
            num=max(num,nums[i]);
        }
        int start = 1;
        int end = num;
        
        while(start<=end)
        {
            int mid = (start+end)/2;
            
            int sum=0;
            for(int i=0;i<nums.size();i++)
            {
                int x;
                if(nums[i]%mid==0)
                     x = nums[i]/mid;
                else
                    x = nums[i]/mid +1;
                
                sum+=x;
            }
            
            if(sum > threshold)
            {
                start = mid + 1;
                continue;
            }
            
            if(sum <= threshold)
            {
                end = mid - 1;
                continue;
            }
        }
        
        return start;
        
    }
};

第四题

看着挺唬人的,我一开始纠结是不是DP,但是一看数据,最多只有3啊,暴力搜索,用位运算保存矩阵的状态,然后注意剪枝就过了。但是因为在第二题上耽误了一些时间,导致比赛结束后,才过了第四题,哎。。

class Solution {
public:
    int vis[10005];
    int ans[10005];
    int map[10][10];
    int n,m;
    int result;
    int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    int minFlips(vector<vector<int>>& mat) {

        int len = mat.size();
        n=len;
        m=mat[0].size();
        for(int i=0;i<mat.size();i++)
        {

            for(int j=mat[i].size()-1;j>=0;j--)
            {
                map[i][j] = mat[i][j];
            }

        }

        result = 9999999;

        int x = compute();
        if(x==0)
            return 0;
        vis[x]=1;
        ans[x]=0;

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                fun(i,j,1);

                map[i][j] ^= 1;

                for(int k=0;k<4;k++)
                {
                    int xx = i+dir[k][0];
                    int yy = j+dir[k][1];

                    if(xx>=0&&xx<n&&yy>=0&&yy<m)
                        map[xx][yy] ^=1;
                }
            }
        }
        if(result == 9999999 )
            result =-1;

        return result;


    }

    void fun(int x,int y,int res)
    {
        map[x][y] ^= 1;

        for(int i=0;i<4;i++)
        {
            int xx = x+dir[i][0];
            int yy = y+dir[i][1];

            if(xx>=0&&xx<n&&yy>=0&&yy<m)
                map[xx][yy] ^=1;
        }

        int v = compute();
        if(vis[v]==1)
        {
            if(res>=ans[v])
            {
                return;
            }
            else
            {
                ans[v]=res;
            }
        }
        if(v==0)
        {
            result=min(result,res);
            return;
        }

        vis[v]=1;
        ans[v]=res;

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {

                fun(i,j,res+1);


                map[i][j] ^= 1;

                for(int k=0;k<4;k++)
                {
                    int xx = i+dir[k][0];
                    int yy = j+dir[k][1];

                    if(xx>=0&&xx<n&&yy>=0&&yy<m)
                        map[xx][yy] ^=1;
                }
            }
        }
    }

    int compute()
    {
        int x=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                x <<= 1;
                x |= map[i][j];
            }
        }

        return x;
    }
};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2016天梯模拟赛 进阶题解

    L2-005 集合相似度 题目链接: https://www.patest.cn/contests/gplt/L2-005 题目的意思是要求两个集合的交集中...

    ShenduCC
  • LeetCode 1291. Sequential Digits

    ShenduCC
  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC
  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • Day2上午解题报告

    预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-2 使用函数求特殊a串数列和

    给定两个均不超过9的正整数a和n,要求编写函数求a+aa+aaa++⋯+aa⋯a(n个a)之和。

    C you again 的博客
  • 浙大版《C语言程序设计(第3版)》题目集 习题5-4 使用函数求素数和

    其中函数prime当用户传入参数p为素数时返回1,否则返回0;函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

    C you again 的博客
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题4-6 水仙花数

    水仙花数是指一个N位正整数(N≥3),它的每个位上的数字的N次幂之和等于它本身。例如:153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。

    C you again 的博客
  • HDU 1573 X问题

    Problem Description 求在小于等于N的正整数中有多少个X满足: Input 输入数据的第一行为一个正整数T,表示有T组测试数据。每组测...

    attack

扫码关注云+社区

领取腾讯云代金券