苏州大写的网站建设,科技公司网页图片,公司网站建立流程,购物网站排名大全目录 100148.最小数字游戏
题目描述
思路分析
代码详解
100169.移除栅栏得到的正方形田地的最大面积
题目描述
思路分析
代码详解
100156.转换字符串的最小成本I
题目描述
思路分析
代码详解
100158.转换字符串的最小成本II
题目描述
思路分析
代码详解 100148.…
目录 100148.最小数字游戏
题目描述
思路分析
代码详解
100169.移除栅栏得到的正方形田地的最大面积
题目描述
思路分析
代码详解
100156.转换字符串的最小成本I
题目描述
思路分析
代码详解
100158.转换字符串的最小成本II
题目描述
思路分析
代码详解 100148.最小数字游戏
题目描述 你有一个下标从 0 开始、长度为 偶数 的整数数组 nums 同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下 每一轮Alice 先从 nums 中移除一个 最小 元素然后 Bob 执行同样的操作。接着Bob 会将移除的元素添加到数组 arr 中然后 Alice 也执行同样的操作。游戏持续进行直到 nums 变为空。 返回结果数组 arr 。 思路分析
小根堆直接模拟
代码详解
class Solution {
public:vectorint numberGame(vectorint nums) {priority_queueint,vectorint,greaterint pq{nums.begin() , nums.end()};vectorint 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, vectorint hFences, vectorint vFences){unordered_setint 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, vectorchar original, vectorchar changed, vectorint cost){long long ret 0;int n original.size();vectorvectorint minc(26 , vectorint(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, vectorstring original, vectorstring changed, vectorint 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();vectorlong long dp(n 1, inf);dp[n] 0;for (int i n - 1; i 0; i--){if (source[i] target[i])dp[i] dp[i1];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[j1] d[id[x]][id[y]]);}}return dp[0] inf ? -1 : dp[0];}
};
