日期：2026年8月5日
LeetCode 題目連結：3310. Remove Methods From Project
解題想法
中等難度題。對我而言，這題最大的困難在於看懂題目的意思。題目給一個計畫的方法之間先後順序的關係，方法數量為 $n$，編號為 $0$ 到 $n-1$，其中編號 $k$ 是可疑的方法，$k$ 之後的方法都被視為可疑的方法；但如果有這群可疑方法之外沒有問題的方法指向這個群組，則整群可疑的方法都不能被移除；最後要回傳剩下的方法。可以將這些方法視為有向圖的節點，先用 BFS 或 DFS 從節點 $k$ 出發，將 $k$ 及相連的節點都標記為可疑。再用一個 for 迴圈掃過所有節點，如果節點 $u$ 是沒有問題的節點，而且 $u$ 指向任何一個可疑的節點，則所有節點都不能被移除。如果需要移除可疑的節點，只回傳沒有問題的節點；反之，回傳所有節點。
Python 程式碼
BFS. Runtime: 227 ms, beats 90.15%. Memory: 99.66 MB, beats 89.39%.
class Solution:
def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
# 用接鄰矩陣儲存下一個相關的方法
adj = [[] for _ in range(n)]
for u, v in invocations:
adj[u].append(v)
# 用 BFS 標記可疑的方法
suspicious = [False] * n
que = deque([k])
while que:
u = que.popleft()
suspicious[u] = True
for v in adj[u]:
if not suspicious[v]:
que.append(v)
# 檢查是否有外部可用的方法呼叫任何可疑的方法，如果有，不能移除任何可疑的方法
removed = True
for u in range(n):
if not suspicious[u]:
for v in adj[u]:
if suspicious[v]:
removed = False
break
# 回傳答案，如果需要移除可疑的方法，只回傳可用的方法
if removed:
return [i for i in range(n) if not suspicious[i]]
else: # 反之，不能移除任何方法，回傳全部的方法
return list(range(n))
DFS. Runtime: 271 ms, beats 76.51%. Memory: 144.79 MB, beats 36.36%.
class Solution:
def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
# 用接鄰矩陣儲存下一個相關的方法
adj = [[] for _ in range(n)]
for u, v in invocations:
adj[u].append(v)
# 用 DFS 標記可疑的方法
suspicious = [False] * n
def dfs(u):
suspicious[u] = True
for v in adj[u]:
if not suspicious[v]:
dfs(v)
dfs(k) # 呼叫 dfs，從方法 k 開始遍歷
# 檢查是否有外部可用的方法呼叫任何可疑的方法，如果有，不能移除任何可疑的方法
removed = True
for u in range(n):
if not suspicious[u]:
for v in adj[u]:
if suspicious[v]:
removed = False
break
# 回傳答案，如果需要移除可疑的方法，只回傳可用的方法
if removed:
return [i for i in range(n) if not suspicious[i]]
else: # 反之，不能移除任何方法，回傳全部的方法
return list(range(n))
C++ 程式碼
BFS. Runtime: 323 ms, beats 39.66%. Memory: 331.55 MB, beats 42.07%.
class Solution {
public:
vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
// 用接鄰矩陣儲存下一個相關的方法
vector<vector<int>> adj (n);
for(auto it : invocations) {
adj[it[0]].push_back(it[1]);
}
// 用 BFS 標記可疑的方法
vector<bool> suspicious (n, false);
queue<int> que;
que.push(k);
while(!que.empty()) {
int u = que.front();
que.pop();
suspicious[u] = true;
for(int v : adj[u]) {
if (!suspicious[v]) {
que.push(v);
}
}
}
// 檢查是否有外部可用的方法呼叫任何可疑的方法，如果有，不能移除任何可疑的方法
bool removed = true;
for(int u = 0; u < n; u++) {
if (!suspicious[u]) {
for(int v : adj[u]) {
if (suspicious[v]) {
removed = false;
break;
}
}
}
}
// 回傳答案，如果需要移除可疑的方法，只回傳可用的方法
vector<int> ans;
if (removed) {
for(int i = 0; i < n; i++) {
if (!suspicious[i]) {
ans.push_back(i);
}
}
} else { // 反之，不能移除任何方法，回傳全部的方法
ans.resize(n);
iota(ans.begin(), ans.end(), 0);
}
return ans;
}
};
DFS. Runtime: 333 ms, beats 36.60%. Memory: 336.62 MB, beats 40.00%.
class Solution {
public:
vector<vector<int>> adj;
vector<bool> suspicious;
void dfs(int u) {
suspicious[u] = true;
for(int v : adj[u]) {
if (!suspicious[v]) {
dfs(v);
}
}
}
vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
// 用接鄰矩陣儲存下一個相關的方法
adj.clear();
adj.resize(n);
for(auto it : invocations) {
adj[it[0]].push_back(it[1]);
}
// 用 DFS 標記可疑的方法
suspicious.assign(n, false);
dfs(k); // 呼叫 dfs，從方法 k 開始遍歷
// 檢查是否有外部可用的方法呼叫任何可疑的方法，如果有，不能移除任何可疑的方法
bool removed = true;
for(int u = 0; u < n; u++) {
if (!suspicious[u]) {
for(int v : adj[u]) {
if (suspicious[v]) {
removed = false;
break;
}
}
}
}
// 回傳答案，如果需要移除可疑的方法，只回傳可用的方法
vector<int> ans;
if (removed) {
for(int i = 0; i < n; i++) {
if (!suspicious[i]) {
ans.push_back(i);
}
}
} else { // 反之，不能移除任何方法，回傳全部的方法
ans.resize(n);
iota(ans.begin(), ans.end(), 0);
}
return ans;
}
};
沒有留言:
張貼留言