算法之不定期更新（三）（2018-04-24）

darryrzhong 发布于2019-08-22 16:40 / 3102人阅读

摘要：实现这个想法之后就发现，时间复杂度真的太高了。本期算法小分享就到这里咯刚做完探索里的初级，还有好多已经说烂了的题就不分享了。如果有什么意见或者想法欢迎在评论区和我交流

题目

input:


n // 代表无向图的顶点数 // 从1开始

m // 无向图的边数

arr1 // 各边的情况，形如[[1, 2], [3, 4],...]（代表顶点0和顶点2相连，顶点3和顶点4相连）

arr2 // 希望求得的连通情况数组，形如[[1, 3], [1, 4], ...] （代表希望知道顶点1，顶点3的连通情况，顶点1和顶点4的连通情况）

output： num，arr2中可以连通的数量
示例： input:

n = 3
m = 1
arr1 = [[1, 3]]
arr2 = [[2, 3]]

output: 0

下面是我解决这个题的时候的思路

解题思路

这个题，刚拿到的时候，我最初的想法是使用无向图的邻接矩阵，然后在检查点的时候通过广度优先遍历查看两个点是否连通。实现这个想法之后就发现，时间复杂度真的太高了。每一次都会产生许多的无用查询。

然后我想了另外一个思路，既然只查询两个点是否连通，那么我们维护一个连通集合不就可以了。一开始每一个孤立的点都是一个多带带的连通集合，形如["1", "2", "3", "4"]，在加上一条边之后，就是该边的两个顶点所在的连通集合合并成同一个连通集合，即加上边[1, 3]后，连通集合变成["13", "2", "4"]。这样，在查询的时候，去寻找顶点B是否在顶点A所处的连通集合里就可以了。于是我写出了如下的代码。

代码

function solution(n, m, arr1, arr2) {
    let hash = new Array(n + 1) // 代表每个点的所在的连通集合,undefined代表这个点还不与其他点相连,0位无效
    let map = {} // 保留每个联通集合的点集
    let index = 1 // 下一个联通集合的编号
    for (let i = 0; i < m; i++) { // 依次添加边到连通集合里
        let edge = arr1[i]
        let A = edge[0] // 顶点A
        let B = edge[1] // 顶点B
        if (hash[A] === undefined && hash[B] === undefined) { // 这两个都是孤立的点，新建一个连通集合
            hash[A] = index
            hash[B] = index
            map[index++] = [A, B]
        } else if (hash[B] === undefined) { // 点A不是孤立的，点B是孤立的，把B加入A的连通集合里
            hash[B] = hash[A]
            map[hash[A]].push(B)
        } else if (hash[A] === undefined) { // 点B不是孤立的，点A是孤立的，把A加入B的连通集合里
            hash[A] = hash[B]
            map[hash[B]].push(A)
        } else if (hash[A] !== hash[B]) { // A,B均不是孤立的，把B的连通集合,加入A的连通集合里
            B_list = map[hash[B]] // B所在的连通集合的顶点列表
            group = hash[A]
            for (let i = B_list.length - 1; i >= 0; i--) { // 每个顶点的连通集合修改为A的
                hash[B_list[i]] = group
            }
            map[group] = map[group].concat(map[hash[B]])
            delete map[hash[B]]
        }
    }
    let result = 0 // 连通的数量
    for (let i = arr2.length - 1; i >= 0; i--) {
        let test = arr2[i]
        let groupA = hash[test[0]]
        let groupB = hash[test[1]]
        if (groupA && groupB && groupA === groupB) {
            result++
        }
    }
    return result
}

也就是，用hash来存放对应的点所在的连通集合，map存放连通集合对应的点。

本期算法小分享就到这里咯（leetcode刚做完探索里的初级，还有好多已经说烂了的题就不分享了。）如果有什么意见或者想法欢迎在评论区和我交流

GPU云服务器云服务器 webrtc之vad算法看动画学算法之:hashtable webrtc agc算法三负载均衡支持三种调度算法

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

转载请注明本文地址：https://www.ucloud.cn/yun/94559.html

算法之不定期更新（二）（2018-04-15）

摘要：题目中的数字可以分割出来的连续数字串的所有组合，不同组合之间用一个和连接示例和和和和和和和和和和这里给同学提个醒。。解题思路利用二叉树。说到这这个题就很容易解决了，利用二叉树的层次遍历，每一层遍历的时候都基于上一层的遍历结果生成答案。题目 input: noutput: 1...n中的数字可以分割出来的连续数字串的所有组合，不同组合之间用一个和连接示例：input: 3output...

Aklman 2019-08-22 16:19 评论0 收藏0
算法之不定期更新（四）—— 从前序与中序遍历序列构造二叉树（2018-06-02）

摘要：树的前序，中序遍历的结构如下图可以看出，通过前序遍历可以确定根节点，再通过中序遍历和根节点的位置可以确定出左子树和右子树。另外左子树的前序遍历和中序遍历的顺序跟在其父树中的顺序一样。因此可以确定有一种递归解法。从前序与中序遍历序列构造二叉树今天带来的是Leetcode上的一个经典题：从前序与中序遍历序列构造二叉树原题干： /** Definition for a binary ...

charles_paul 2019-08-26 11:57 评论0 收藏0
算法之不定期更新（一）（2018-04-12）

摘要：算法的确有他独特的魅力。然后我在做这个题的时候，其实也用到了类似质因数分解，只是其实我们可以更好的利用到因数这一个特性。判断一个数是否是质数质数列表一开始我们认为每一个数都可能是自身的幂线性筛为质数遍历质数列表为质数的幂前言从三月份到现在，大大小小笔试了十几家公司（主要是因为一直solo code，没人内推），然后也能感觉到自己的进步把。从编程题只能ac一题到后来的ak。今天面腾讯...

Martin91 2019-08-22 16:16 评论0 收藏0
CSS技巧

摘要：技巧使你的更加专业这是上关于技巧的一篇译文，另外你也可以在本项目看到原文。列举了一些很实用的技巧，比如给空内容的标签添加内容，逗号分隔列表等等。排序算法看源码，把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。成为专业程序员路上用到的各种优秀资料、神器及框架成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 评论0 收藏0