資訊專(zhuān)欄INFORMATION COLUMN
摘要：所以這是可能的。示例輸入輸出解釋總共有門(mén)課程。拓?fù)渑判蚴莵?lái)檢測(cè)圖中有無(wú)環(huán)的算法。刪除中找到的點(diǎn)及以它為起點(diǎn)的邊。代碼鄰接表表示法存放每個(gè)點(diǎn)的入度，初始為構(gòu)造鄰接表，并求出每個(gè)點(diǎn)的初始入度。暫存入度為的節(jié)點(diǎn)。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
現(xiàn)在你總共有 n 門(mén)課需要選，記為 0 到 n-1。
在選修某些課程之前需要一些先修課程。 例如，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 ，我們用一個(gè)匹配來(lái)表示他們: [0,1]
給定課程總量以及它們的先決條件，判斷是否可能完成所有課程的學(xué)習(xí)？
示例 1:
輸入: 2, [[1,0]]
輸出: true
解釋: 總共有 2 門(mén)課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0。所以這是可能的。
示例 2:
輸入: 2, [[1,0],[0,1]]
輸出: false
解釋: 總共有 2 門(mén)課程。學(xué)習(xí)課程 1 之前，你需要先完成?課程 0；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1。這是不可能的。
解答：
利用圖的拓?fù)渑判颉?br>拓?fù)渑判蚴莵?lái)檢測(cè)圖中有無(wú)環(huán)的算法。具體步驟：
1找到一個(gè)入度為0的點(diǎn)，若沒(méi)有，則返回圖中有環(huán)。
2刪除1中找到的點(diǎn)及以它為起點(diǎn)的邊。
3重復(fù)1、2直到圖中所有點(diǎn)都被刪除，此時(shí)返回圖中無(wú)環(huán)。
下面的一種思路是建立類(lèi)似鄰接表的圖，這里的鄰接表保存的不是邊，而是指向該點(diǎn)的
其他點(diǎn)，這種算法很好理解，但是時(shí)間復(fù)雜度過(guò)大。
思想是，每一次都找到一個(gè)點(diǎn)，這個(gè)點(diǎn)沒(méi)有任何點(diǎn)指向它。然后把它刪除。
再遍歷圖，把這個(gè)點(diǎn)作為起點(diǎn)的邊(其他點(diǎn)鄰接表的元素)刪除，直到圖為空返回true
或者找不到這個(gè)點(diǎn)，返回false。
java ac代碼：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
//鄰接表，存放的是指向該節(jié)點(diǎn)的其他節(jié)點(diǎn)編號(hào)，而不是邊
//如果某個(gè)點(diǎn)沒(méi)有其他點(diǎn)指向它，那么對(duì)應(yīng)的list為空。
HashMap> map = new HashMap(numCourses);
for(int i = 0;i < numCourses;i++)
map.put(i,new ArrayList());
for(int i = 0;i < prerequisites.length;i++)
{
int previous = prerequisites[i][1];
int latter = prerequisites[i][0];
Listlist = map.get(latter);
list.add(previous);
}
while(map.size() > 0)
{
//判斷是否能找到一個(gè)沒(méi)有任何節(jié)點(diǎn)指向的節(jié)點(diǎn)
boolean flag = false;
int num = 0;
for(Map.Entry> entry:map.entrySet())
if(entry.getValue().size() == 0)
{
flag = true;
num = entry.getKey();
break;
}
if(!flag)return false;
map.remove(num);
Iterator> it = map.values().iterator();
while(it.hasNext())
it.next().remove(new Integer(num));
}
return true;
}
}
下面這種是利用一個(gè)隊(duì)列暫存入度為0的點(diǎn)的快速拓?fù)渑判蚍椒ā?/strong>
因?yàn)樗槐孛看味紡念^查找入度為0的點(diǎn)，因此時(shí)間效率得到了提示。
java ac代碼：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
//鄰接表,表示法
HashMap> map = new HashMap(numCourses);
//存放每個(gè)點(diǎn)的入度，初始為0
HashMapmap2 = new HashMap(numCourses);
for(int i = 0;i < numCourses;i++){
map.put(i,new ArrayList());
map2.put(i,0);
}
//構(gòu)造鄰接表，并求出每個(gè)點(diǎn)的初始入度。
for(int i = 0;i < prerequisites.length;i++)
{
int previous = prerequisites[i][1];
int latter = prerequisites[i][0];
Listlist = map.get(previous);
list.add(latter);
map.put(previous,list);
map2.put(latter,map2.get(latter)+1);
}
//暫存入度為0的節(jié)點(diǎn)。
ArrayDequequeue = new ArrayDeque();
for(int i = 0;i < numCourses;i++)
if(map2.get(i) == 0)
queue.offer(i);
//統(tǒng)計(jì)最終能有多少個(gè)入度為0的點(diǎn)，若該數(shù)量小于numCourses則代表有環(huán)
int count = 0;
while(!queue.isEmpty())
{
int node = queue.poll();
for(int i:map.get(node))
{
int ii = map2.get(i);
ii -= 1;
if(ii != 0)
map2.put(i,ii);
//這個(gè)點(diǎn)的入度變?yōu)榱?，可以加入隊(duì)列中
else
queue.offer(i);
}
count++;
}
return count == numCourses;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73975.html
摘要：圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小高度的樹(shù)被稱(chēng)為最小高度樹(shù)。給出這樣的一個(gè)圖，寫(xiě)出一個(gè)函數(shù)找到所有的最小高度樹(shù)并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對(duì)于一個(gè)具有樹(shù)特征的無(wú)向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡(jiǎn)介：大家好，我是車(chē)神哥，府學(xué)路18號(hào)的車(chē)神? ?個(gè)人主頁(yè)：應(yīng)無(wú)所住而生...
摘要：對(duì)于每個(gè)氣球，提供的輸入是水平方向上，氣球直徑的開(kāi)始和結(jié)束坐標(biāo)?？梢陨涑龅墓臄?shù)量沒(méi)有限制。弓箭一旦被射出之后，可以無(wú)限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問(wèn)題，不太好說(shuō)清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對(duì)于每個(gè)氣球，提供的輸入是水平方...
摘要：有效二叉搜索樹(shù)定義如下節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。而我們二叉搜索樹(shù)保證了左子樹(shù)的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹(shù)的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 1981·2019-08-30 15:54
閱讀 3608·2019-08-29 13:07
閱讀 3133·2019-08-29 12:39
閱讀 1799·2019-08-26 12:13
閱讀 1555·2019-08-23 18:31
閱讀 2167·2019-08-23 18:05
閱讀 1856·2019-08-23 18:00
閱讀 1052·2019-08-23 17:15
