LeetCode,第377场周赛,个人题解
目录
100148.最小数字游戏
题目描述
你有一个下标从?0?开始、长度为?偶数?的整数数组?
nums
?,同时还有一个空数组?arr
?。Alice 和 Bob 决定玩一个游戏,游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下:
- 每一轮,Alice 先从?
nums
?中移除一个?最小?元素,然后 Bob 执行同样的操作。- 接着,Bob 会将移除的元素添加到数组?
arr
?中,然后 Alice 也执行同样的操作。- 游戏持续进行,直到?
nums
?变为空。返回结果数组?
arr
?。
思路分析
小根堆直接模拟
代码详解
class Solution {
public:
vector<int> numberGame(vector<int>& nums) {
priority_queue<int,vector<int>,greater<int>> pq{nums.begin() , nums.end()};
vector<int> ret;
int x , y;
while(pq.size())
{
y = pq.top();pq.pop();
x = pq.top() , pq.pop();
ret.push_back(x);
ret.push_back(y);
}
return ret;
}
};
100169.移除栅栏得到的正方形田地的最大面积
题目描述
有一个大型的?
(m - 1) x (n - 1)
?矩形田地,其两个对角分别是?(1, 1)
?和?(m, n)
?,田地内部有一些水平栅栏和垂直栅栏,分别由数组?hFences
?和?vFences
?给出。水平栅栏为坐标?
(hFences[i], 1)
?到?(hFences[i], n)
,垂直栅栏为坐标?(1, vFences[i])
?到?(m, vFences[i])
?。返回通过?移除?一些栅栏(可能不移除)所能形成的最大面积的?正方形?田地的面积,或者如果无法形成正方形田地则返回?
-1
。由于答案可能很大,所以请返回结果对?
109 + 7
?取余?后的值。注意:田地外围两个水平栅栏(坐标?
(1, 1)
?到?(1, n)
?和坐标?(m, 1)
?到?(m, n)
?)以及两个垂直栅栏(坐标?(1, 1)
?到?(m, 1)
?和坐标?(1, n)
?到?(m, n)
?)所包围。这些栅栏?不能?被移除。
思路分析
先对两个方向栅栏进行排序,然后哈希表记录所有水平可能间隔
枚举垂直可能间隔,如果已经在哈希表存在,则为可能答案,维护答案的最大值即可
代码详解
class Solution
{
public:
const int MOD = 1e9 + 7;
int maximizeSquareArea(int m, int n, vector<int> &hFences, vector<int> &vFences)
{
unordered_set<int> hash;
hFences.emplace_back(m);
vFences.emplace_back(n);
sort(hFences.begin(),hFences.end());
sort(vFences.begin(),vFences.end());
int n1 = hFences.size(), n2 = vFences.size(), x, ans = 0;
for (int i = 0; i < n1; i++)
{
x = hFences[i];
hash.insert(x - 1);
for (int j = i - 1; j >= 0; j--)
hash.insert(x - hFences[j]);
}
for (int i = 0; i < n2; i++)
{
x = vFences[i];
if (hash.count(x - 1))
ans = max(ans, x - 1);
for (int j = i - 1; j >= 0; j--)
if (hash.count(x - vFences[j]))
ans = max(ans, x - vFences[j]);
}
return ans ? (((long long)ans * ans) % MOD) : -1;
}
};
100156.转换字符串的最小成本I
题目描述
给你两个下标从?0?开始的字符串?
source
?和?target
?,它们的长度均为?n
?并且由?小写?英文字母组成。另给你两个下标从?0?开始的字符数组?
original
?和?changed
?,以及一个整数数组?cost
?,其中?cost[i]
?代表将字符?original[i]
?更改为字符?changed[i]
?的成本。你从字符串?
source
?开始。在一次操作中,如果?存在?任意?下标?j
?满足?cost[j] == z
? 、original[j] == x
?以及?changed[j] == y
?。你就可以选择字符串中的一个字符?x
?并以?z
?的成本将其更改为字符?y
?。返回将字符串?
source
?转换为字符串?target
?所需的?最小?成本。如果不可能完成转换,则返回?-1
?。注意,可能存在下标?
i
?、j
?使得?original[j] == original[i]
?且?changed[j] == changed[i]
?。。
思路分析
可以直接转换的字符之间可以建立一条有向边,那么我们可以预处理一张有向图,然后跑一边floyd,比对原字符串和目标字符串,如果相同则不做处理
如果不同且有路,那么答案加上路径长度
如果不同且没路,那么就直接返回-1
代码详解
class Solution
{
public:
long long minimumCost(string source, string target, vector<char> &original, vector<char> &changed, vector<int> &cost)
{
long long ret = 0;
int n = original.size();
vector<vector<int>> minc(26 , vector<int>(26,INT_MAX));
for (int i = 0; i < n; i++)
minc[original[i] - 'a'][changed[i] - 'a'] = min(minc[original[i] - 'a'][changed[i] - 'a'],cost[i]);
for (int k = 0; k < 26; k++)
for (int i = 0; i < 26; i++)
for (int j = 0; j < 26; j++)
if (minc[i][j] - minc[i][k] > minc[k][j])
minc[i][j] = minc[i][k] + minc[k][j];
for (int i = 0, len = source.size(); i < len; i++)
if (source[i] == target[i])
continue;
else
{
if (minc[source[i] - 'a'][target[i] - 'a'] == INT_MAX)
return -1;
ret += minc[source[i] - 'a'][target[i] - 'a'];
}
return ret;
}
};
100158.转换字符串的最小成本II
?
题目描述
给你两个下标从?0?开始的字符串?
source
?和?target
?,它们的长度均为?n
?并且由?小写?英文字母组成。另给你两个下标从?0?开始的字符串数组?
original
?和?changed
?,以及一个整数数组?cost
?,其中?cost[i]
?代表将字符串?original[i]
?更改为字符串?changed[i]
?的成本。你从字符串?
source
?开始。在一次操作中,如果?存在?任意?下标?j
?满足?cost[j] == z
? 、original[j] == x
?以及?changed[j] == y
?,你就可以选择字符串中的?子串?x
?并以?z
?的成本将其更改为?y
?。 你可以执行?任意数量?的操作,但是任两次操作必须满足?以下两个?条件?之一?:
- 在两次操作中选择的子串分别是?
source[a..b]
?和?source[c..d]
?,满足?b < c
??或?d < a
?。换句话说,两次操作中选择的下标?不相交?。- 在两次操作中选择的子串分别是?
source[a..b]
?和?source[c..d]
?,满足?a == c
?且?b == d
?。换句话说,两次操作中选择的下标?相同?。返回将字符串?
source
?转换为字符串?target
?所需的?最小?成本。如果不可能完成转换,则返回?-1
?。注意,可能存在下标?
i
?、j
?使得?original[j] == original[i]
?且?changed[j] == changed[i]
?。
思路分析
和上一道题类似的思路,上一题对字符建图,这道题对字符串建图
关键在于如何快速获取字符串,可以选择字符哈希,这里我用的字典树,不过比赛的时候被卡常了,赛后加了个关闭输入输出同步然后过了
具体就是把可转换字符串都插入到字典树,对应单词结尾的字典树节点编号是可以作为字符串的映射的,为了跑floyd就把字典树节点编号再离散化一下
这样得到了最多200个节点的图,完全可以跑floyd
然后对于熟悉这种字符串转换的很容易想到动态规划进一步处理
我们规定dp[i]为下标i 到 n - 1转换成本
然后我们找从下标i开始的可转换子串,结束下标为j,那么dp[i] = min(dp[i] , dp[j + 1] + dist[][])
那么如果source[i] == target[i] ,dp[i]初始化为dp[i + 1]
之所以倒序dp是因为用了字典树存储
代码详解
class Solution
{
public:
Solution(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
}
int nodes[200010][26], id[200010] , idx;
long long inf = 0x3f3f3f3f3f3f3f3f;
int insert(const string &s)
{
int cur = 0;
for (char c : s)
{
if (nodes[cur][c - 'a'] == -1)
nodes[cur][c - 'a'] = idx++;
cur = nodes[cur][c - 'a'];
}
return cur;
};
long long minimumCost(string source, string target, vector<string> &original, vector<string> &changed, vector<int> &cost)
{
int n = original.size() * 2, x, y;
long long d[n][n];
memset(d, 0x3f, sizeof(d));
memset(id, -1, sizeof(id));
memset(nodes, -1, sizeof(nodes));
idx = 1;
int tot = 0;
for (int i = 0; i < original.size(); ++i)
{
x = insert(original[i]), y = insert(changed[i]);
if(id[x] == -1) id[x] = tot++;
if(id[y] == -1) id[y] = tot++;
x = id[x] , y = id[y];
d[x][y] = min(d[x][y], (long long)cost[i]);
}
for (int k = 0; k < tot; ++k)
for (int i = 0; i < tot; ++i)
for (int j = 0; j < tot; ++j)
if (d[i][j] - d[i][k] > d[k][j])
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
n = source.size();
vector<long long> dp(n + 1, inf);
dp[n] = 0;
for (int i = n - 1; i >= 0; i--)
{
if (source[i] == target[i])
dp[i] = dp[i+1];
x = y = 0;
for(int j = i ; j < n ; j++)
{
x = nodes[x][source[j]-'a'],y = nodes[y][target[j]-'a'];
if(y==-1||x==-1) break;
if(id[x]==-1||id[y]==-1) continue;
dp[i] = min(dp[i] , dp[j+1] + d[id[x]][id[y]]);
}
}
return dp[0] == inf ? -1 : dp[0];
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!