3.0万

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;

}
};