pq|dfs|快排

lc1985

简单题 简单做

上堆/快排也行

按字符串长度降序、长度相同则按字典序降序排序数字字符串数组，返回第 k 大的元素。

class Solution {
public:
string kthLargestNumber(vector<string>& nums, int k) {
sort(nums.begin(), nums.end(),
[](string s1, string s2)->bool
{
if(s1.size() != s2.size()) return s1.size() > s2.size(); //先比字符串的长度
else return s1 > s2;//再比字符串的大小
});
return nums[k - 1];//返回第k个大的
}
};

优先队列

class Solution {
private:
static bool cmp(const string& s1, const string& s2) {
if(s1.length() != s2.length()) return s1.length() < s2.length();
for(int i = 0; i < s1.length(); ++i) {
if(s1[i] != s2[i])
return s1[i] < s2[i];
}
return false;
};
public:
string kthLargestNumber(vector<string>& nums, int k) {
priority_queue<string, vector<string>, decltype(&Solution::cmp)> q(cmp);
for(const auto& s: nums)
q.push(s);
while(!q.empty() && --k)
q.pop();
return q.top();
}
};

快排接口 优雅的比较函数😋

class Solution {
public:
static bool cmp(string s1, string s2) {
return s1.size() != s2.size() ? s1.size() > s2.size() : s1 > s2;
}

string kthLargestNumber(vector<string>& nums, int k)

{
nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), cmp);
return nums[k - 1];
}
};

lc3331

感觉就是当图来做的，注意回溯处理

先建树，DFS回溯维护每个字符的最近祖先，把同字符子节点移到最近祖先下重构树

最后DFS统计每个节点的子树大小

class Solution {
public:
vector<int> findSubtreeSizes(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<int>> g(n);
for (int i = 1; i < n; i++)
g[parent[i]].push_back(i);

int ancestor[26];
ranges::fill(ancestor, -1);
auto rebuild = [&](auto&& rebuild, int x) -> void {
int sx = s[x] - 'a';
int old = ancestor[sx];
ancestor[sx] = x;
for (int i = g[x].size() - 1; i >= 0; i--) {
int y = g[x][i];
int anc = ancestor[s[y] - 'a'];
if (anc != -1) {
g[anc].push_back(y);
g[x][i] = -1; // -1 表示删除 y
}
rebuild(rebuild, y);
}
ancestor[sx] = old; // 恢复现场
};
rebuild(rebuild, 0);

vector<int> size(n, 1); // 注意这里已经把 1 算进去了
auto dfs = [&](auto&& dfs, int x) -> void {
for (int y : g[x]) {
if (y != -1) { // y 没被删除
dfs(dfs, y);
size[x] += size[y];
}
}
};
dfs(dfs, 0);
return size;
}
};

class Solution {
public:
vector<int> findSubtreeSizes(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<int>> g(n);
for (int i = 1; i < n; i++)
g[parent[i]].push_back(i);

vector<int> size(n, 1);
int ancestor[26];
ranges::fill(ancestor, -1);

auto dfs = [&](auto&& dfs, int x) -> void {
int sx = s[x] - 'a';
int old = ancestor[sx];
ancestor[sx] = x;
for (int y : g[x]) {
dfs(dfs, y);
int anc = ancestor[s[y] - 'a'];
size[anc < 0 ? x : anc] += size[y];
}
ancestor[sx] = old; // 恢复现场
};
dfs(dfs, 0);
return size;
}
};