你有一個下標從?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];}
};