資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中終止程序
假設我們有 n 個程序，每個程序都有一個唯一的 ID，稱為 PID 或程序 ID，並且還有其 PPID（父程序 ID）。
每個程序只有一個父程序，但可能有一個或多個子程序。
這就像一個樹形結構。只有一個程序的 PPID = 0，這意味著該程序沒有父程序。所有 PID 都是唯一的正整數。
我們將使用兩個整數列表來表示程序列表，其中第一個列表包含每個程序的 PID，第二個列表包含相應的 PPID。因此，如果我們有兩個列表，以及一個表示我們要終止的程序的 PID，那麼我們必須找到最終將被終止的程序的 PID 列表。並且我們應該假設當一個程序被終止時，其所有子程序也將被終止。
因此，如果輸入類似於 pid = [1, 3, 10, 5] ppid = [3, 0, 5, 3] kill = 5，則輸出將為 [5,10]，
終止 5 也將終止 10。
為了解決這個問題，我們將遵循以下步驟 -
定義一個名為 child 的對映
n := pid 的大小
定義一個數組 ret
初始化 i := 0，當 i < n 時，更新（i 增加 1），執行 -
u := ppid[i]
v := pid[i]
將 v 插入到 child[u] 的末尾
定義一個佇列 q
將 kill 插入到 q 中
當 (q 不為空) 時，執行 -
curr := q 的第一個元素
從 q 中刪除元素
將 curr 插入到 ret 的末尾
初始化 i := 0，當 i < child[curr] 的大小 時，更新（i 增加 1），執行 -
將 child[curr, i] 插入到 q 中
返回 ret
示例
讓我們看看以下實現，以便更好地理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
map<int, vector<int> > child;
int n = pid.size();
vector<int> ret;
for (int i = 0; i < n; i++) {
int u = ppid[i];
int v = pid[i];
child[u].push_back(v);
}
queue<int> q;
q.push(kill);
while (!q.empty()) {
int curr = q.front();
q.pop();
ret.push_back(curr);
for (int i = 0; i < child[curr].size(); i++) {
q.push(child[curr][i]);
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,3,10,5}, v1 = {3,0,5,3};
print_vector(ob.killProcess(v, v1, 5));
}輸入
{1,3,10,5},{3,0,5,3},5輸出
[5, 10, ]
更新於: 2020-11-16
2K+ 次瀏覽
廣告