$\large\color{orange}{比赛入口:}$$ \color{orange}{LeetCode312} $$ \large\color{orange}{周赛} $
$\large\color{green}{2418. 按身高排序}$
结构体排序,时间复杂度:$O(nlogn)$
class Solution {
public:
typedef pair<int, string> pii;
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
vector<pii> T;
int n = names.size();
for(int i = 0; i < n; i ++ ) T.push_back({heights[i], names[i]});
sort(T.begin(), T.end());
vector<string> res;
for(int i = n - 1; i >= 0; i -- ) res.push_back(T[i].second);
return res;
}
};
$\large\color{orange}{2419. 按位与最大的最长子数组}$
位运算 + 双指针,时间复杂度:$O(n)$
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int maxv = 0;
for(auto &x : nums) maxv = max(maxv, x);
int maxv_len = 1;
int n = nums.size();
for(int i = 0; i < n; i ++ ){
if(nums[i] == maxv){
int j = i;
while(j < n && nums[j] == maxv) j ++ ;
maxv_len = max(maxv_len, j - i);
i = j - 1;
}
}
return maxv_len;
}
};
$\large\color{orange}{2420. 找到所有好下标}$
前缀和,时间复杂度:$O(n)$
class Solution {
public:
static const int N = 1E5 + 10;
int pre[N], last[N];
vector<int> goodIndices(vector<int>& nums, int k) {
int n = nums.size();
int cnt = 1;
for(int i = 0; i < n; i ++ ){
if(!i) pre[i] = cnt;
else{
if(nums[i] <= nums[i - 1]) cnt ++ ;
else cnt = 1;
pre[i] = cnt;
}
}
cnt = 1;
for(int i = n - 1; i >= 0; i -- ){
if(i == n - 1) last[i] = cnt;
else{
if(nums[i] <= nums[i + 1]) cnt ++ ;
else cnt = 1;
last[i] = cnt;
}
}
vector<int> res;
for(int i = k; i < n - k; i ++ ){
if(pre[i - 1] >= k && last[i + 1] >= k) res.push_back(i);
}
return res;
}
};
$\large\color{red}{2421. 好路径的数目}$
并查集
class Solution {
public:
map<int, vector<int>> mp;
static const int N = 1E5 + 10, M = 2 * N;
int h[N], e[N], ne[N], idx;
int p[N], cnt[N], maxv[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void establish(vector<vector<int>>& edges){
memset(h, -1, sizeof h);
idx = 0;
for(auto &edge : edges){
add(edge[0], edge[1]);
add(edge[1], edge[0]);
}
}
int find(int x){
if(p[x] == x) return x;
return p[x] = find(p[x]);
}
int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
establish(edges);
int n = vals.size();
for(int i = 0; i < n; i ++ ) mp[vals[i]].push_back(i);
for(int i = 0; i < n; i ++ ) p[i] = i, cnt[i] = 1, maxv[i] = vals[i];
int res = 0;
for(auto it = mp.begin(); it != mp.end(); it ++ ){
for(auto x : it->second){
for(int k = h[x]; k != -1; k = ne[k]){
int y = e[k];
if(vals[y] > vals[x]) continue;
int px = find(x), py = find(y);
if(px == py) continue;
if(maxv[px] > maxv[py]){
maxv[py] = maxv[px];
p[py] = px;
}else{
res += cnt[px] * cnt[py];
p[py] = px;
cnt[px] += cnt[py];
}
}
}
}
return res + n;
}
};