資訊專欄INFORMATION COLUMN
摘要：注意雖然員工也是員工的一個(gè)下屬，但是由于并不是直系下屬，因此沒(méi)有體現(xiàn)在員工的數(shù)據(jù)結(jié)構(gòu)中。示例輸入輸出解釋員工自身的重要度是，他有兩個(gè)直系下屬和，而且和的重要度均為。并且利用加速查找。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一個(gè)保存員工信息的數(shù)據(jù)結(jié)構(gòu)，它包含了員工唯一的id，重要度 和 直系下屬的id。
比如，員工1是員工2的領(lǐng)導(dǎo)，員工2是員工3的領(lǐng)導(dǎo)。他們相應(yīng)的重要度為15, 10, 5。那么員工1的數(shù)據(jù)結(jié)構(gòu)是[1, 15, [2]]，員工2的數(shù)據(jù)結(jié)構(gòu)是[2, 10, [3]]，員工3的數(shù)據(jù)結(jié)構(gòu)是[3, 5, []]。注意雖然員工3也是員工1的一個(gè)下屬，但是由于并不是直系下屬，因此沒(méi)有體現(xiàn)在員工1的數(shù)據(jù)結(jié)構(gòu)中。
現(xiàn)在輸入一個(gè)公司的所有員工信息，以及單個(gè)員工id，返回這個(gè)員工和他所有下屬的重要度之和。
示例 1:
輸入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
輸出: 11
解釋:
員工1自身的重要度是5，他有兩個(gè)直系下屬2和3，而且2和3的重要度均為3。因此員工1的總重要度是 5 + 3 + 3 = 11。
注意:
一個(gè)員工最多有一個(gè)直系領(lǐng)導(dǎo)，但是可以有多個(gè)直系下屬
員工數(shù)量不超過(guò)2000。
解答：
寬度優(yōu)先搜索(使用一個(gè)隊(duì)列)，利用HashSet記錄是否已經(jīng)訪問(wèn)過(guò)。并且利用HashMap加速查找。
java ac代碼：
/*
// Employee info
class Employee {
// It"s the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List subordinates;
};
*/
class Solution {
public int getImportance(List employees, int id) {
HashSet set = new HashSet(500);
HashMap map = new HashMap(500);
for(Employee e : employees)
map.put(e.id,e);
int ans = 0;
ArrayDeque deque = new ArrayDeque(500);
deque.offer(id);
set.add(id);
while(!deque.isEmpty())
{
Integer tempid = deque.poll();
Employee e = map.get(tempid);
ans += e.importance;
for(Integer i:e.subordinates)
if(!set.contains(i))
{
set.add(i);
deque.offer(i);
}
}
return ans;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/73047.html
摘要：有效二叉搜索樹定義如下節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
摘要：每個(gè)請(qǐng)求來(lái)的時(shí)候都會(huì)先去看看中有沒(méi)有，即使使用的是的方式也不免會(huì)讓我對(duì)它的性能產(chǎn)生一些擔(dān)憂，所以性能測(cè)試就必須要來(lái)一發(fā)了。注也在阿里云執(zhí)行只要是為了在一個(gè)數(shù)據(jù)中心降低網(wǎng)絡(luò)延遲。測(cè)試因?yàn)榭紤]到服務(wù)器比較穩(wěn)定，減少壓測(cè)總數(shù)。 背景 最近我操刀了leetcode的論壇遷移，整個(gè)過(guò)程持續(xù)了幾周的時(shí)間，總算暫時(shí)告了一個(gè)段落。常使用leetcode論壇的用戶應(yīng)該已經(jīng)發(fā)現(xiàn)論壇已經(jīng)大變樣了吧~ 期間遇...
摘要：每個(gè)請(qǐng)求來(lái)的時(shí)候都會(huì)先去看看中有沒(méi)有，即使使用的是的方式也不免會(huì)讓我對(duì)它的性能產(chǎn)生一些擔(dān)憂，所以性能測(cè)試就必須要來(lái)一發(fā)了。注也在阿里云執(zhí)行只要是為了在一個(gè)數(shù)據(jù)中心降低網(wǎng)絡(luò)延遲。測(cè)試因?yàn)榭紤]到服務(wù)器比較穩(wěn)定，減少壓測(cè)總數(shù)。 背景 最近我操刀了leetcode的論壇遷移，整個(gè)過(guò)程持續(xù)了幾周的時(shí)間，總算暫時(shí)告了一個(gè)段落。常使用leetcode論壇的用戶應(yīng)該已經(jīng)發(fā)現(xiàn)論壇已經(jīng)大變樣了吧~ 期間遇...
摘要：一中心旋轉(zhuǎn)效果代碼矩形中心點(diǎn)旋轉(zhuǎn)前紅色矩形旋轉(zhuǎn)后綠色矩形二中心縮放效果代碼矩形中心點(diǎn)縮放前紅色矩形縮放后綠色矩形 一、中心旋轉(zhuǎn)效果：showImg(https://segmentfault.com/img/bVNOwx?w=396&h=339); 代碼： var canvas = document.createElement(canvas); canvas.width = 500; c...
摘要：年，阿里云在全球范圍內(nèi)率先發(fā)起數(shù)據(jù)保護(hù)倡議。借助阿里云的網(wǎng)絡(luò)溯源，警方最終成功抓捕到名犯罪嫌疑人，將黑客組織一網(wǎng)打盡。過(guò)去兩年，阿里云已陸續(xù)協(xié)助警方破獲案件數(shù)十起攻擊相關(guān)案件，抓捕百余人次。9月28日，阿里云正式發(fā)布首個(gè)企業(yè)云安全架構(gòu)和《2017阿里云安全白皮書》（以下簡(jiǎn)稱白皮書），企業(yè)可參考架構(gòu)指南和白皮書構(gòu)建安全、穩(wěn)固的信息化架構(gòu)。白皮書將用戶隱私和數(shù)據(jù)安全列為第一原則，并于2015年全...
閱讀 3012·2021-11-11 16:55
閱讀 585·2021-09-27 13:36
閱讀 1185·2021-09-22 15:35
閱讀 3014·2019-08-30 12:46
閱讀 3213·2019-08-26 17:02
閱讀 1887·2019-08-26 11:56
閱讀 1359·2019-08-26 11:47
閱讀 474·2019-08-23 17:01
