?
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=bfs+貪心
?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優于繼承，實現自定義]
?
)
)
