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;

    }

};

巴特西

LeetCode Contest 166

最新文章

热门文章