lc1337
pair存入，lambda sort后取出，最开始想用hash，写一半感觉写复杂了
class Solution {
public:
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
int m = mat.size();
int n = mat[0].size();
vector<pair<int,int>>ans;
//统计每一行的军人数量以及索引
for(int i = 0; i < m; i++){
int sum = accumulate(mat[i].begin(), mat[i].end(), 0);
ans.push_back({sum, i});
}
//按照军人数量优先排序，其次是索引排序
sort(ans.begin(), ans.end(), [](pair<int,int>&a, pair<int,int>&b){
if(a.first == b.first){
return a.second < b.second;
}
return a.first < b.first;
});
//统计k个索引
vector<int>cnt;
for(int i = 0; i < k; i++){
cnt.push_back(ans[i].second);
}
return cnt;
}
};
lc743.网络延迟时间
dijkstra
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2)); // 邻接矩阵
for (auto& t : times) {
g[t[0] - 1][t[1] - 1] = t[2];
}
vector<int> dis(n, INT_MAX / 2), done(n);
dis[k - 1] = 0;
while (true) {
int x = -1;
for (int i = 0; i < n; i++) {
if (!done[i] && (x < 0 || dis[i] < dis[x])) {
x = i;
}
}
if (x < 0) {
return ranges::max(dis);
}
if (dis[x] == INT_MAX / 2) { // 有节点无法到达
return -1;
}
done[x] = true; // 最短路长度已确定（无法变得更小）
for (int y = 0; y < n; y++) {
// 更新 x 的邻居的最短路
dis[y] = min(dis[y], dis[x] + g[x][y]);
}
}
}
};
1353.优先队列
priority_queue<int, vector<int>, greater<>> pq;
class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
int mx = 0;
for (auto& e : events) {
mx = max(mx, e[1]);
}
// 按照开始时间分组
vector<vector<int>> groups(mx + 1);
for (auto& e : events) {
groups[e[0]].push_back(e[1]);
}
int ans = 0;
priority_queue<int, vector<int>, greater<>> pq;
for (int i = 0; i <= mx; i++) {
// 删除过期会议
while (!pq.empty() && pq.top() < i) {
pq.pop();
}
// 新增可以参加的会议
for (int end_day : groups[i]) {
pq.push(end_day);
}
// 参加一个结束时间最早的会议
if (!pq.empty()) {
ans++;
pq.pop();
}
}
return ans;
}
};
螺旋数组的遍历
通过l t r b 控制遍历螺旋
class Solution {
public:
vector<int> spiralArray(vector<vector<int>>& array)
{
if (array.empty()) return {};
int l = 0, r = array[0].size() - 1, t = 0, b = array.size() - 1;
vector<int> res;
while(true)
{
for (int i = l; i <= r; i++) res.push_back(array[t][i]); // left to right
if (++t > b) break;
for (int i = t; i <= b; i++) res.push_back(array[i][r]); // top to bottom
if (l > --r) break;
for (int i = r; i >= l; i--) res.push_back(array[b][i]); // right to left
if (t > --b) break;
for (int i = b; i >= t; i--) res.push_back(array[i][l]); // bottom to top
if (++l > r) break;
}
return res;
}
};
hash冲突与解决
rust
所有权，包管理，高性能，0开销抽象，内存安全，无谓并发，主要[treat优于继承，实现自定义]