[Algo] Install Dependencies 安裝依賴

li21 發布于2019-08-14 16:15 / 929人閱讀

摘要：拓撲排序復雜度時間空間思路本題和的解法一樣，不會拓撲排序的可以參考那篇文章。區別在于我們拓撲排序后的訪問順序，本來我們是用一個來進行，這里為了讓依賴少的先安裝，我們將換成，并以依賴數排序。

Install Dependencies

給定軟件之間安裝的依賴關系，用一個二維數組表示，第一維表示依賴的序號，第二維表示依賴關系，比如要先裝deps[0][0]，才能裝deps[0][1]。安裝時，要盡可能先安裝依賴個數少的軟件。求安裝順序。

拓撲排序 復雜度

時間 O(1) 空間 O(1)

思路

本題和Course Schedule的解法一樣，不會拓撲排序的可以參考那篇文章。區別在于我們拓撲排序后的訪問順序，本來我們是用一個Queue來進行BFS，這里為了讓依賴少的先安裝，我們將Queue換成PriorityQueue，并以依賴數排序。用優先隊列遍歷圖，很像是Cost based search 或者greedy，a star這種算法。注意，由于可能出現兩個軟件有同樣依賴數的情況，比如兩個軟件剩余依賴都是0的時候，應該先裝哪個呢？這個就要和面試官討論了，可以在軟件的數據結構中加入timestamp或者總依賴數等變量，供我們在ProrityQueue中作為第二個、第三個條件來比較。

代碼

public class InstallDependencies {
    public static void main(String[] args){
        String[][] deps = {{"gcc", "gdb"},{"gcc", "visualstudio"},{"windows", "gcc"}
        , {"windows", "sublime"}, {"libc", "gcc"}, {"libc2", "gcc"}, {"unix", "cat"}
        , {"windows", "libc"}, {"windows", "libc2"}, {"linux", "cat"}, {"windows", "cat"}
        , {"solaris", "cat"}, {"macos","cat"}};
        InstallDependencies id = new InstallDependencies();
        id.install(deps, 7);
    }
    
    public void install(String[][] deps, int n){
        HashMap map = new HashMap();
        // 根據依賴關系建圖
        for(String[] dep : deps){
            Software src = map.get(dep[0]);
            Software dst = map.get(dep[1]);
            if(src == null){
                src = new Software(dep[0]);
            }
            if(dst == null){
                dst = new Software(dep[1]);
            }
            src.targets.add(dst);
            dst.deps = dst.deps + 1;
            map.put(dep[0], src);
            map.put(dep[1], dst);
        }
        // 用一個優先隊列來遍歷我們的圖
        PriorityQueue pq = new PriorityQueue(11 ,new Comparator(){
            public int compare(Software s1, Software s2){
                return s1.deps - s2.deps;
            }
        });
        for(String name : map.keySet()){
            if(map.get(name).deps == 0){
                pq.offer(map.get(name));
            }
        }
        while(!pq.isEmpty()){
            Software curr = pq.poll();
            System.out.println(curr.name);
            for(Software dst : curr.targets){
                dst.deps = dst.deps - 1;
                if(dst.deps == 0){
                    pq.offer(dst);
                }
            }
        }
    }
}

class Software{
    String name;
    int deps;
    ArrayList targets;
    public Software(String name){
        this.deps = 0;
        this.name = name;
        this.targets = new ArrayList();
    }
}

云服務器 GPU云服務器 Dependencies Algo install ruby install

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66172.html

npm install 你很明白嗎？

摘要：你很明白嗎依賴開發依賴當我們敲的時候會安裝哪些依賴，和都會安裝嗎還是只安裝項目依賴包是放在和簡單問兩個問題，勾起大家對，，的回憶。和還是有明顯區別的。結論當你在開發一個包的時候，還是要好好管理你的依賴和依賴。 npm install 你很明白嗎dependencies 依賴devDependencies 開發依賴【當我們敲 npm install 的時候會安裝哪些依賴，depende...

SnaiLiu 2019-08-26 18:27 評論0 收藏0
npm官方npm-install文檔翻譯

摘要：如果版本尚未發布到注冊表，則會失敗。參數將阻止安裝可選的依賴項。參數，它將忽略可用的包鎖或文件，而是使用。參數可用于禁止將審計報告發送到已配置的注冊表。我覺得所有程序員都在努力的學習閱讀英語吧，畢竟英語閱讀沒問題，我們才能更好的閱讀文檔，為了給大家更快的學習效率，所以翻譯了這一篇中英文對照的文章。如果你每次安裝package包時候會想，what?各種命令--save -D 之類的究...

RobinQu 2019-08-26 10:31 評論0 收藏0
什么是npm系列：一、npm簡介

摘要：本文是系列的第一篇，知識很基礎，作為一個熱身文章，如果各位已經是開發熟練工了，完全可以跳過這篇。系列匯總什么是系列一簡介什么是系列二的十八般武藝本文同步發表博客什么是系列一簡介 showImg(https://segmentfault.com/img/bVbwqLS?w=1400&h=545); npm是Node.js的包管理工具，它的誕生也極大的促進了前端的發展，在現代前端開發中都離...

dcr309duan 2019-08-26 10:48 評論0 收藏0
npm install -save 和 -save-dev

摘要：會將模塊依賴寫入節點。運行初始化項目時，會將模塊下載到項目目錄下。運行或者注明變量值為時，不會自動下載模塊到目錄中開發環境。這些模塊在我們的項目部署后是不需要的，所以我們可以使用的形式安裝。 npm install packageName //本地安裝，安裝到項目目錄下，不在package.json中寫入依賴npm install packageName -g //全局安...

zhiwei 2019-08-22 16:31 評論0 收藏0
npm的lock機制解析

摘要：但往往中指定的是一個版本范圍，例如以上這個指定的范圍是版本號大于等于且大版本號為。之后的機制滿足了要求鎖版本的開發者們的需要，我們只需要拿到一份就可以知道要安裝的依賴的具體版本號。 npm是什么 npm是一個包管理工具，開源作者可以把開源包發布在平臺上供其他人下載使用。前端的同學基本都使用過npm，這里就不做過多介紹。日常工作中npm的主要用途就是根據項目的package.json使用...

BlackFlagBin 2019-08-23 18:20 評論0 收藏0