[Algo] Install Dependencies 安装依赖

li21 发布于2019-08-14 16:15 / 928人阅读

摘要：拓扑排序复杂度时间空间思路本题和的解法一样，不会拓扑排序的可以参考那篇文章。区别在于我们拓扑排序后的访问顺序，本来我们是用一个来进行，这里为了让依赖少的先安装，我们将换成，并以依赖数排序。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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