头像

胡图图

逐渐退出算法界的辣鸡大学生




离线:4小时前



胡图图
1个月前
const int N = 13;
const int M = 1 << 13;

int f[N][M];

class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {

        memset(f,0x3f,sizeof f);

        int n = cost.size();
        int m = cost[0].size();

        f[0][0] = 0;

        for(int i=0;i<n;i++)
            for(int j=0;j<1<<m;j++)
            {
                for(int v=0;v<m;v++)
                {
                    int state = j | (1 << v);
                    f[i + 1][state] = min(f[i + 1][state],f[i][j]+cost[i][v]);
                }

            }

        int res = 0x3f3f3f3f;

        for(int i=0;i<1<<m;i++)
        {
            int value = 0;
            for(int j=0;j<m;j++)
            {
                if(i >> j & 1) continue;
                int t = 0x3f3f3f3f;
                for(int k=0;k<n;k++)
                    t = min(t,cost[k][j]);
                value += t;

            }

            res = min(res,f[n][i] + value);
        }


        return res;
    }
};



胡图图
1个月前
#define ll long long

const int mod = 1e9 + 7;
const int N = 16;

ll posf[N][N];
ll negf[N][N];

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {

        memset(posf,-0x3f,sizeof posf);
        memset(negf,0x3f,sizeof negf);

        int n = grid.size();
        int m = grid[0].size();

        if(grid[0][0] >= 0 ) posf[0][0] = grid[0][0];
        else negf[0][0] = grid[0][0];

        bool flag = false;

        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                ll x = grid[i][j];

                if(x == 0) flag = true;

                if(i == 0 && j == 0) continue;


                if(i > 0) 
                {
                    if(posf[i - 1][j] >= 0)
                    {
                        ll value = posf[i - 1][j] * x;
                        if(value >= 0) posf[i][j] = max(posf[i][j],value);
                        else negf[i][j] = min(negf[i][j],value);
                    }

                    if(negf[i - 1][j] < 0)
                    {
                        ll value = negf[i - 1][j] * x;
                        if(value >= 0) posf[i][j] = max(posf[i][j],value);
                        else negf[i][j] = min(negf[i][j],value);
                    }
                }

                if(j > 0)
                {
                    if(posf[i][j - 1] >= 0)
                    {
                        ll value = posf[i][j - 1] * x;
                        if(value >= 0) posf[i][j] = max(posf[i][j],value);
                        else negf[i][j] = min(negf[i][j],value);
                    }

                    if(negf[i][j - 1] < 0)
                    {
                        ll value = negf[i][j - 1] * x;
                        if(value >= 0) posf[i][j] = max(posf[i][j],value);
                        else negf[i][j] = min(negf[i][j],value);
                    }
                }


            }

        if(posf[n - 1][m - 1] < 0) 
        {
            if(flag) return 0;
            else return -1;
        }

        return posf[n - 1][m - 1] % mod;
    }
};



胡图图
1个月前
#pragma GCC optimize(2)

unordered_set<string> st;
string str;

class Solution {
public:
    int maxUniqueSplit(string s) {

        int n = s.size();

        if(n == 1) return 1;

        int res = 1;

        for(int i=0;i < 1 << n - 1 ;i++)
        {
            int c = 1;

            st.clear();

            str="";

            bool flag = true;

            for(int j = 0 ; j < n - 1 ; j ++ )
            {
                str += s[j];
                if(i >> j & 1)
                {
                    c ++ ;
                    if(st.count(str))
                    {
                        flag = false;
                        break;
                    }
                    st.insert(str);
                    str = "";
                }

            }

            if(!flag) continue;
            str += s[n - 1];

            if(st.count(str)) flag = false;
            st.insert(str);

            if(flag) res = max(res,c);
        }

        return res;

    }
};



胡图图
1个月前
class Solution {
public:
    string reorderSpaces(string text) {

        vector<string> v;

        int c = 0;

        while(text.size() && text.back() == ' ') 
        {
            text.pop_back();
            c ++ ;
        }

        reverse(text.begin(),text.end());

        while(text.size() && text.back() == ' ') 
        {
            text.pop_back();
            c ++ ;
        }

        reverse(text.begin(),text.end());

        int i = 0;

        while(i < text.size())
        {
            string s = "";

            while(i < text.size() && text[i] != ' ')
            {
                s += text[i];
                i ++ ;
            }

            while(i < text.size() && text[i] == ' ')
            {
                c ++ ; 
                i ++ ;
            }

            v.push_back(s);    
        }

        int t = v.size();

        string res = "";

        if(t != 1)
        {
            int a = c / (t - 1);
            c = c % (t - 1);

            for(int i=0;i<v.size();i++)
            {
                res += v[i];
                if(i!=v.size() - 1) 
                {
                    for(int j=0;j<a;j++)
                        res += ' ';
                }
            }

            while(c -- )
            {
                res += ' ';
            }
        }
        else
        {
            res += v[0];
            while(c -- ) res += ' ';
        }

        return res;
    }
};



胡图图
1个月前
class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {

        map<int,int> mp;

        int sum = 0;

        for(auto x : nums) sum = (sum + x) % p;

        if(sum == 0) return 0;

        int n = nums.size();

        int res = n;

        int s = 0;

        mp[0] = -1;

        for(int i = 0 ; i < n ; i ++ )
        {
            s = (s + nums[i]) % p;
            int t  = ((s - sum) % p + p) % p;
            if(mp.count(t)) res = min(res,i - mp[t]);
            mp[s] = i;
        }


        if(res == n) res = -1;

        return res;
    }
};



胡图图
1个月前
const int N = 1e5 + 10;

const int mod = 1e9 + 7;

int power[N];

class Solution {
public:
    int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {

        memset(power,0,sizeof power);

        int n = nums.size();

        for(auto &v : requests)
        {
            int a = v[0];
            int b = v[1];

            power[a] ++ ;
            power[b + 1] -- ; 
        }

        for(int i=1;i<N;i++) power[i] += power[i - 1];

        sort(power,power + n);
        sort(nums.begin(),nums.end());

        int res = 0;

        for(int i=0;i<n;i++)
        {
            res = (res + 1ll * power[i] * nums[i] % mod) % mod;
        }

        return res;
    }
};



胡图图
1个月前
class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {

        int n = arr.size();

        int no = 1,odd = 0;
        int ne = 0,even = 0;

        int sum = 0;

        int res = 0;

        for(int i = 0 ; i < n ; i ++ )
        {
            sum += arr[i];

            if(i & 1)
            {
                res += ne * sum - even;
                no ++ ;
                odd += sum;  
            }
            else
            {
                res += no * sum - odd;
                ne ++ ;
                even += sum; 
            }
        }


        return res;
    }
};



胡图图
1个月前
const int N = 65;

int l[N],r[N],u[N],d[N];

int e[N];

vector<int> order;

vector<int> ver[N];

bool topsort(int target)
{
    int cnt = 0;

    queue<int> q;

    for(int i = 0 ; i < N ; i ++ )
    {
        if(d[i] == -1) continue;
        if(e[i] == 0)
            q.push(i);
    }

    while(q.size())
    {
        int t = q.front();
        q.pop();
        cnt ++ ;
        order.push_back(t);

        for(auto x : ver[t])
        {
            if(--e[x] == 0)
                q.push(x);
        }
    }

    return cnt == target;
}

class Solution {
public:
    bool isPrintable(vector<vector<int>>& targetGrid) {

        int target = 0;

        for(int i = 0 ; i < N ; i ++ ) ver[i].clear();

        memset(e,0,sizeof e);

        order.clear();

        int n = targetGrid.size();
        int m = targetGrid[0].size();

        vector<vector<int>> g(n,vector<int>(m,-1));

        memset(l,0x3f,sizeof l);
        memset(u,0x3f,sizeof u);
        memset(r,-1,sizeof r);
        memset(d,-1,sizeof d);

        for(int i = 0 ; i < n ; i ++ )
            for(int j = 0 ; j < m ; j ++ )
            {
                int x = targetGrid[i][j];

                l[x] = min(l[x],j);
                r[x] = max(r[x],j);

                u[x] = min(u[x],i);
                d[x] = max(d[x],i);
            }

        for(int c = 0 ; c < N ; c ++ )
        {
            if(d[c] == -1) continue;
            target ++ ;
        }

        for(int i = 0 ; i < n ; i ++ )
            for(int j = 0 ; j < m ; j ++ )
            {
                int x = targetGrid[i][j];
                for(int c = 0 ; c < N ; c ++ )
                {
                    if(d[c] == -1) continue;
                    if(c == x) continue;
                    if(u[c] <= i && d[c] >= i && l[c] <= j && r[c] >= j)
                    {
                        ver[c].push_back(x);
                        e[x] ++ ;
                    }
                }
            }

        if(!topsort(target)) return false;

        for(auto i : order)
        {
            for(int a = u[i] ; a <= d[i] ; a ++ )
                for(int b = l[i] ; b <= r[i] ; b ++ )
                    g[a][b] = i;
        }


        return g == targetGrid;
    }
};



胡图图
1个月前
vector<int> p[10];

class Solution {
public:
    bool isTransformable(string s, string t) {

        int n = s.size();

        for(int i=0;i<10;i++)
        {
            p[i].clear();
        }

        for(int i=0;i<n;i++)
        {
            int x = s[i] - '0';
            p[x].push_back(i);
        }

        for(int i=n-1;i>=0;i--)
        {
            int x = t[i] - '0';

            if(p[x].size() == 0) return false;

            int cur = p[x].back();

            p[x].pop_back();

            for(int j=x+1;j<10;j++)
            {
                if(p[j].size() == 0) continue;

                if(p[j].back()> cur) return false;
            }
        }

        return true;
    }
};



胡图图
1个月前
const int N = 1010;

struct Edge{
    int a,b;
    int w;
    bool operator<(const Edge& t) const
    {
        return w < t.w;
    }
};

vector<Edge> edge;

int n;

int fa[N];

int find(int x)
{
    if(fa[x] == x) return x;

    return fa[x] = find(fa[x]);
}


class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {

        n = points.size();  

        edge.clear();

        memset(fa,-1,sizeof fa);


        for(int i=0;i<n;i++) fa[i] = i;

        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                int a = points[i][0];
                int b = points[i][1];
                int c = points[j][0];
                int d = points[j][1];

                int x = abs(a - c) + abs(b - d);

                edge.push_back({i,j,x});
            }
        }

        sort(edge.begin(),edge.end());

        int res = 0;

        for(auto &e : edge)
        {
            int a = e.a;
            int b = e.b;
            int w = e.w;

            a = find(a);
            b = find(b);

            if(a == b) continue; ;

            fa[a] = b;

            res += w;            

        }

        return res;

    }
};