Re: [閒聊] 每日LeetCode已回收
: 連題目是什麼都不知道 :)
: 這是要怎麼寫
好像修好了
不過看起來就只是讓這題變不是 premium
1061. Lexicographically Smallest Equivalent String
對所有 i，要讓 A[i] == B[i]
標準的 union find，把 parent 設成最小的那個就可以了
總共只會有 26*26 = 676 種可能的 query
甚至比 s1 的最大長度 1000 還少
class Solution {
public:
vector<int> parent = vector<int>(128);
int find(int a) {
if (parent[a] != a)
parent[a] = find(parent[a]);
return parent[a];
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u > v) swap(u, v);
parent[v] = u;
}
string smallestEquivalentString(string s1, string s2, string baseStr) {
for (int i = 0; i < 128; i++)
parent[i] = i;
int n = s1.size();
for (int i = 0; i < n; i++)
merge(s1[i], s2[i]);
for (char& c: baseStr)
c = find(c);
return baseStr;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673660915.A.8BE.html
推
01/14 09:51,
2年前
, 1F
01/14 09:51, 1F
推
01/14 17:23,
2年前
, 2F
01/14 17:23, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 192 之 719 篇)：