第 377 场周赛虚拟参赛记录及补题
2023-12-24 21:54:19
最小数字游戏 3
- 题目
- 思路
模拟 - 代码
class Solution {
public:
vector<int> numberGame(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<int> ans;
for (int i = 0;i < nums.size();i ++)
if (i&1)
ans.push_back(nums[i-1]);
else
ans.push_back(nums[i+1]);
return ans;
}
};
移除栅栏得到的正方形田地的最大面积 4
- 思路
- 思路
细节题,把所有的空隙全考虑一遍。 - 代码
class Solution {
public:
int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
long long ans = 0;
sort(hFences.begin(),hFences.end());
sort(vFences.begin(),vFences.end());
int hlen = hFences.size(),vlen = vFences.size();
int x = 0;
vector<int> hc,vc;
hc.push_back(m-1);
for (int i = 0;i < hlen;i ++) {
hc.push_back(hFences[i]-1);
for (int j = i + 1;j < hlen;j ++)
hc.push_back(hFences[j]-hFences[i]);
hc.push_back(m-hFences[i]);
}
vc.push_back(n-1);
for (int i = 0;i < vlen;i ++) {
vc.push_back(vFences[i]-1);
for (int j = i + 1;j < vlen;j ++)
vc.push_back(vFences[j]-vFences[i]);
vc.push_back(n-vFences[i]);
}
sort(hc.begin(),hc.end());
sort(vc.begin(),vc.end());
int l = hc.size()-1,r = vc.size()-1;
while (l >= 0&&r >= 0&&hc[l] != vc[r]) {
if (hc[l] > vc[r]) l --;
else r --;
}
if (l >= 0 && r >= 0) {
ans = 1ll*hc[l]*hc[l];
return ans%(1000000007);
} else {
return -1;
}
}
};
转换字符串的最小成本 I 5
- 题目
- 示例
- 思路
最短路,先处理26个字母之间的最短路。这样复杂度就是O(262626);
- 代码
class Solution {
public:
long long minimumCost(string source, string target, vector<char> &original, vector<char> &changed, vector<int> &cost) {
int dis[26][26];
memset(dis, 0x3f, sizeof(dis));
for (int i = 0; i < 26; i++) {
dis[i][i] = 0;
}
for (int i = 0; i < cost.size(); i++) {
int x = original[i] - 'a';
int y = changed[i] - 'a';
dis[x][y] = min(dis[x][y], cost[i]);
}
for (int k = 0; k < 26; k++) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
long long ans = 0;
for (int i = 0; i < source.length(); i++) {
int d = dis[source[i] - 'a'][target[i] - 'a'];
if (d == 0x3f3f3f3f) {
return -1;
}
ans += d;
}
return ans;
}
};
转换字符串的最小成本 II 6
- 题意
- 思路
- 代码
int f[200005][26], g[200005];
class Solution {
public:
long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
int n = original.size() * 2;
long long d[n][n];
memset(d, 0x3f, sizeof(d));
long long inf = 0x3f3f3f3f3f3f3f3fll;
int p = 1;
memset(f[0], -1, sizeof(f[0]));
g[0] = -1;
auto insert = [&](string& s) {
int cur = 0;
for(char c : s) {
if(f[cur][c-'a'] == -1) {
f[cur][c-'a'] = p;
memset(f[p], -1, sizeof(f[p]));
g[p] = -1;
p++;
}
cur = f[cur][c-'a'];
}
return cur;
};
int m = 0;
for(int i = 0; i < original.size(); ++i) {
int from = insert(original[i]), to = insert(changed[i]);
if(g[from] == -1)
g[from] = m++;
if(g[to] == -1)
g[to] = m++;
d[g[from]][g[to]] = min(d[g[from]][g[to]], (long long)cost[i]);
}
for(int k = 0; k < m; ++k) {
for(int i = 0; i < m; ++i) {
for(int j = 0; j < m; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
long long dp[source.size() + 1];
dp[source.size()] = 0;
for(int i = source.size() - 1; i >= 0; --i) {
dp[i] = inf;
if(source[i] == target[i])
dp[i] = dp[i+1];
for(int j = i, cur1 = 0, cur2 = 0; j < source.size(); ++j) {
cur1 = f[cur1][source[j]-'a'];
cur2 = f[cur2][target[j]-'a'];
if(cur1 == -1 || cur2 == -1) break;
if(g[cur1] != -1 && g[cur2] != -1)
dp[i] = min(dp[i], d[g[cur1]][g[cur2]] + dp[j+1]);
}
}
if(dp[0] >= inf) return -1;
return dp[0];
}
};
文章来源:https://blog.csdn.net/qq_46264636/article/details/135185698
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!