第 128 场 LeetCode 双周赛题解
A 字符串的分数
模拟
class Solution {
public:
int scoreOfString(string s) {
int res = 0;
for (int i = 1; i < s.size(); i++)
res += abs(s[i] - s[i - 1]);
return res;
}
};
B 覆盖所有点的最少矩形数目
排序:先按照 x i x_i xi 排序,然后顺序遍历数组,尽可能将 p o i n t s [ i ] points[i] points[i] 放入已有的矩形中
class Solution {
public:
int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
sort(points.begin(), points.end());
int res = 0;
int n = points.size();
for (int i = 0, j = 0; i < n; i = ++j) {
res++;
while (j + 1 < n && points[j + 1][0] - points[i][0] <= w)
j++;
}
return res;
}
};
C 访问消失节点的最少时间
最短路: dijkstra+一个节点时间判断
class Solution {
public:
vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
vector<pair<int, int>> e[n];
for (auto& edge : edges) {
e[edge[0]].push_back({edge[1], edge[2]});
e[edge[1]].push_back({edge[0], edge[2]});
}
int inf = 1e9;
vector<int> p(n, inf);
p[0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.emplace(0, 0);
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (p[u] < d)
continue;
for (auto& [v, w] : e[u]) {
int npv = d + w;
if (npv < p[v] && npv < disappear[v]) {
p[v] = npv;
q.emplace(npv, v);
}
}
}
for (auto& i : p)
if (i == inf)
i = -1;
return p;
}
};
D 边界元素是最大值的子数组数目
单调栈+哈希:遍历数组,维护一个非递增的栈,每次出栈时,将出栈元素的出现次数清零,每次元素进栈时出现次数+1,同时更新答案
class Solution {
public:
long long numberOfSubarrays(vector<int>& nums) {
long long res = 0;
stack<int> st;
unordered_map<int, int> cnt;
for (int i = 0; i < nums.size(); i++) {
while (!st.empty() && st.top() < nums[i]) {
cnt[st.top()] = 0;
st.pop();
}
res += ++cnt[nums[i]];
st.push(nums[i]);
}
return res;
}
};
原文地址:https://blog.csdn.net/weixin_40519680/article/details/137738325
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!