本文最后更新于:8 个月前
My Submission
Problem AC: 4
Problem Try: 4
Wrong Answer: 2
题意分析
签到题,优先队列 + 标记
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int minimumOperations (vector<int >& nums) { priority_queue<int , vector<int >, greater<>> pq; int lazy = 0 , ans = 0 ; for (int v: nums) if (v != 0 ) pq.push (v); while (!pq.empty () && lazy != pq.top ()) { int num = pq.top (); lazy += num - lazy; ans++; while (!pq.empty () && pq.top () == num) pq.pop (); } return ans; } };
题意分析
脑筋急转弯:
按等差数列分组,若每次可以满足则下一个组人数 + 1,否则直接结束循环
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int maximumGroups (vector<int >& grades) { int ans = 1 , now = 1 , next = 2 ; while (now + next <= grades.size ()) { ans++; now += next; next++; } return ans; } };
题意分析
广度优先搜索 + 记录距离
遍历node1
和node2
的所有节点并统计距离,再遍历距离返回符合要求的答案
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 #include "bits/stdc++.h" #include "iomanip" using namespace std;#define fastIO() ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define pb push_back #define loop(t) while (t-- > 0) #define enhanceFor(t) for (auto it: t) typedef unordered_map<int , int > umii;const double eps = 1e-6 ;const int MOD = 1e9 + 7 ;const int i32 = 0x3f3f3f3f ;const ll i64 = 0x3f3f3f3f3f3f3f3f ;using vvi = vector<vi>;class Solution {public : int closestMeetingNode (vector<int >& edges, int node1, int node2) { int n = edges.size (); vvi grid (n) ; for (int i = 0 ; i < n; ++i) { if (edges[i] == -1 ) continue ; grid[i].pb (edges[i]); } int dis = 1 ; us<int > vis; queue<int > queue; umii u1,u2; queue.push (node1); while (!queue.empty ()) { int size = queue.size (); loop (size) { int pos = queue.front (); queue.pop (); if (vis.count (pos)) continue ; vis.insert (pos); u1[pos] = dis; for (int v: grid[pos]) queue.push (v); } dis++; } dis = 1 ; vis.clear (); queue.push (node2); while (!queue.empty ()) { int size = queue.size (); loop (size) { int pos = queue.front (); queue.pop (); if (vis.count (pos)) continue ; vis.insert (pos); u2[pos] = dis; for (int v: grid[pos]) queue.push (v); } dis++; } int ans = -1 ; dis = i32; enhanceFor (u1) { if (u2.count (it.first)) { if (max (it.second, u2[it.first]) < dis) { dis = max (it.second, u2[it.first]); ans = it.first; } else if (max (it.second, u2[it.first]) == dis) { ans = min (ans, it.first); } } } return ans; } };
题意分析
给定一个图,返回其中最大的环
拓扑排序 + 深度优先搜索
先使用拓扑排序的方法,确定图种环的节点序号
对于每一个环上的点深搜确定其长度
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #include "bits/stdc++.h" #include "iomanip" using namespace std;#define fastIO() ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define pb push_back #define fori(a, b) for (int i = a; i < b; i++) #define enhanceFor(t) for (auto it: t) #define us unordered_set const double eps = 1e-6 ;const int MOD = 1e9 + 7 ;const int i32 = 0x3f3f3f3f ;const ll i64 = 0x3f3f3f3f3f3f3f3f ;using vi = vector<int >;using vvi = vector<vi>;class Solution {public : int ans = -1 ; us<int > set; void dfs (vvi &grid, int dee, int pos) { if (set.count (pos)) { ans = max (ans, dee); return ; } set.insert (pos); for (int v: grid[pos]) { dfs (grid, dee + 1 , v); } } int longestCycle (vector<int >& edges) { int n = edges.size (); vi systemIO (n,0 ) ; vvi grid (n) ; for (int i = 0 ; i < n; ++i) { if (edges[i] != -1 ) { systemIO[edges[i]]++; grid[i].pb (edges[i]); } } queue<int > queue; fori(0 ,n){ if (systemIO[i]==0 ) queue.push (i); } while (!queue.empty ()) { int size = queue.size (); loop (size){ int pos = queue.front (); queue.pop (); enhanceFor (grid[pos]) { systemIO[it]--; if (systemIO[it] == 0 ) queue.push (it); } } } fori(0 ,n){ if (!set.count (i) && systemIO[i] == 1 ) { dfs (grid, 0 , i); } } return ans; } };