<small id='3wWdcYn2le'></small> <noframes id='uGsOj6'>

  • <tfoot id='WBzi1f8pQ9'></tfoot>

      <legend id='674cdk5'><style id='45XIzyF'><dir id='g623fnC'><q id='o8apvsj'></q></dir></style></legend>
      <i id='OISA97xF'><tr id='s0fQF'><dt id='yJwKxv7'><q id='wKYnxI'><span id='kynKmwL'><b id='DoNcJlTn7'><form id='fkxjOp9E'><ins id='vz29EsrbD'></ins><ul id='nYpmqkD'></ul><sub id='P6Nb7hVw3'></sub></form><legend id='AVudl'></legend><bdo id='UkJbFX6'><pre id='Bx8N'><center id='XhTR'></center></pre></bdo></b><th id='1dov'></th></span></q></dt></tr></i><div id='H0awUh'><tfoot id='Xg2dh6V'></tfoot><dl id='I0DVzw'><fieldset id='C5QGVeZ'></fieldset></dl></div>

          <bdo id='ME0DiQ'></bdo><ul id='Lbghxn'></ul>

          1. <li id='EYOB2jFeM'></li>
            登陆

            微信面试算法:朋友圈个数问题

            admin 2019-07-14 247人围观 ,发现0个评论

            来历:互联网侦查

            作者:channingbreeze


            小史是一个应届生,尽管学的是电子专业,可是自己业余时间看了许多互联网与编程方面的书,专心想进BAT互联网公司。



            今天小史去了一家交际小巨子公司面试了。



            【面试现场】


            面试官:举个比方,比方现在有5个宠物,分别是小猫1,小猫2,小猫3,小狗1,小狗2。再告知你小猫1和小狗1是好朋友,小猫2和小狗1是好朋友,小猫3和小狗2是好朋友。这样它们之间就构成了2个朋友圈。


            小史:先对宠物们编号,然后一对老友联系就用一个bitmap来存。判别两个bitmap之间是否有交集,只需求进行与操作。而交融的话只需求进行并操作。

            小史在纸上画了半响进行考虑。一分钟过去了。

            小史:我如同知道了,能够在遍历老友联系的一起,把他们进行兼并,我用双向链表来做。初始时,每个宠物都是一个独自的节点,而一对老友联系过来的时分,先判别两个节点是否在同一个链表中,假如不在,就把两个节点地点的链表头尾相连,构成一个新链表。

            一分钟过去了。


            【讨教大神】


            回到校园,小史把面试状况和吕教师说了一下。


            小史:这个我早就考虑到了,13是好朋友,并不是衔接13,而是去找1的根和3的根,发现他们都是2,所以他们原本就在一个朋友圈,不需求相连。


            【并查集】


            小史:哦,对,堆也是一种树,可是它是二叉树,而且是彻底二叉树,所以才能用数组存,而且用坐标的方法核算父亲孩子节点。

            吕教师:今天的树相同能够用数组存,初始时间数组中都是-1,当有两个节点需求兼并时,只需求将其中一个数的根的值设为另一个数的根的下标就行。

            小史在纸上划拉半响,总算有点了解了。

            了解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了。


            UnionFindSet.java

            /**
             * @author xiaoshi on 2018/11/4.
             */

            public class UnionFindSet {

                // 存储并查集
                private int[] elements;

                UnionFindSet(int n) {
                    // 初始都为-1
                    elements = new int[n];
                    for (int i = 0; i < n; i++) {
                        elements[i] = -1;
                    }
                }

                // 找到一个数的根
                public int find(int x{
                    while(elements[x] != -1) {
                        x = elements[x];
                    }
                    return x;
                }

                // 把两个数的根连起来
                public void union(int x, int y{
                    // x的根
                    int rootx = find(x);
                    // y的根
                    int rooty = find(y);
                    // 假如不是同一个根就连起来
                    if(rootx != rooty) {
                        elements[rootx] = rooty;
                    }
                }

                // 核算构成了多少颗树
                public int count({
                    int count = 0;
                    for(int i=0; i<elements.length; i++) {
                        if(elements[i] == -1) {
                            count++;
                        }
                    }
                    return count;
                }

                // 打微信面试算法:朋友圈个数问题印并查集
                public void print({
                    for(int i=0; i<elements.length; i++) {
                        System.out.print(elements[i] + " ");
                    }
                    System.out.println();
                }

            }

            (友谊提示:可左右滑动)


            Main.java

            /**
             * @author xiaoshi on 2018/11/4.
             */

            public class Main {

                public static void main(String[] args) {

                    UnionFindSet ufs = new UnionFindSet(10);

                    ufs.union(01);
                    ufs.union(02);
                    ufs.union(34);
                    ufs.union(31);
                    ufs.union(57);
                    ufs.union(78);
                    ufs.union(78);

                    System.out.println(ufs.count());

                }

            }

            (友谊提示:可左右滑动)


            运转成果

            4


            【根据树高度的兼并优化】


            吕教师:1和2是好朋友,2和3是好朋友,3和4是好朋友,4和5是好朋友。

            了解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了。


            UnionFindSetMergeOptimize.java

            /**
             * @author xiaoshi on 2018/11/4.
             */

            public class UnionFindSetMergeOptimize {

                // 存储并查集
                private int[] elements;
                // 存储树的高度
                private int[] heights;

                UnionFindSetMergeOptimize(int n) {
                    elements = new int[n];
                    heights = new int[n];
                    for (int i = 0; i < n; i++) {
                        // 初始都为-1
                        elements[i] = -1;
                        // 初始高度1
                        heights[i] = 1;
                    }
                }

                // 找到一个数的根
                public int find(int x{
                    while(elements[x] != -1) {
                        x = elements[x];
                    }
                    return x;
                }

                // 把两个数的根连起来
                public void union(int x, int y{
                    // x的根
                    int rootx = find(x);
                    // y的根
                    int rooty = find(y);
                    // 假如不是同一个根就连起来
                    if(rootx != rooty) {
                        // 矮树向高树兼并
                        if(heights[rootx] > heights[rooty]) {
                            elements[rooty] = rootx;
                        } else if(heights[rootx] < heights[rooty]) {
                            elements[rootx] = rooty;
                        } else {
                            // 假如高度相同,随意兼并
                            elements[rootx] = rooty;
                            // 可是记住兼并后高度加一
                            heights[rooty]++;
                        }

                    }
                }

                // 核算构成了多少颗树
                public int count({
                    int count = 0;
                    for(int i=0; i<elements.length; i++) {
                        if(elements[i] == -1) {
                            count++;
                        }
                    }
                    return count;
                }

                // 打印并查集
                public void print({
                    for(int i=0; i<elements.length; i++) {
                        System.out.print(elements[i] + " ");
                    }
                    System.out.println();
                    for(int i=0; i<heights.length; i++) {
                        System.out.print(heights[i] + " ");
                    }
                    System.out.println();
                }

            }

            (友谊提示:可左右滑动)


            Main.java

            /**
             * @author xiaoshi on 2018/11/4.
             */

            public class Main {

                public static void main(String[] args) {

                    UnionFindSetMergeOptimize ufsmo = new UnionFindSetMergeOptimize(10);

                    ufsmo.union(01);
                    ufsmo.union(12);
                    ufsmo.union(23);
                    ufsmo.union(34);
                    ufsmo.union(45);
                    ufsmo.union(56);
               &亚洲男同志nbsp;    ufsmo.union(67);
                    ufsmo.union(78);
                    ufsmo.union(89);

                    System.out.println(ufsmo.count());

                }

            }

            (友谊提示:可左右滑动)


            运转成果

            1


            【途径紧缩优化】


            了解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了。


            UnionFindSetPathOptimize.java

            /**
             * @author xiaoshi on 2018/11/4.
             */

            public class UnionFindSetPathOptimize {

                // 存储并查集
                private int[] elements;

                UnionFindSetPathOptimize(int n) {
                    // 初始都为-1
                    elements = new int[n];
                    for (int i = 0; i < n; i++) {
                        elements[i] = -1;
                    }
                }

                // 找到一个数的根
                public int find(int x{
                    // 保存原始x值
                    int originX = x;
                    // 找到根
                    while(elements[x] != -1) {
                        x = elements[x];
                    }
                    // 把这一路的节点悉数直接连到根上
                    while(originX != x) {
                        int tempX = originX;
                        originX = elements[originX];
                        elements[tempX] = x;
                    }
                    return x;
                }

                // 把两个数的根连起来
                public void union(int x, int y{
                    // x的根
                    int rootx = find(x);
                    // y的根
                    int rooty = find(y);
                    // 假如不是同一个根就连起来
                    if(rootx != rooty) {
                        elements[rootx] = rooty;
                    }
                }

                // 核算构成了多少颗树
                public int count({
                    int count = 0;
                    for(int i=0; i<elements.length; i++) {
                        if(elements[i] == -1) {
                            count++;
                        }
                    }
                    return count;
                }

                // 打印并查集
                public void print({
                    for(int i=0; i<elements.length; i++) {
                        System.out.print(elements[i] + " ");
             微信面试算法:朋友圈个数问题       }
                    System.out.println();
                }

            }

            (友谊提示:可左右滑动)


            Main.java

            /**
             * @author xiaoshi on 2018/11/4.
             */

            public class Main {

                public static void main(String[] args) {

                    UnionFindSetPathOptimize ufspo = new UnionFindSetPathOptimize(10);

                    ufspo.union(01);
                    ufspo.union(12);
                    ufspo.union(23);
                    ufspo.union(34);
                    ufspo.union(45);
                    ufspo.union(56);
                    ufspo.union(67);
                    ufspo.union(78);
                    ufspo.union(09);

                    System.out.println(ufspo.count());

                }

            }

            (友谊提示:可左右滑动)


            运转成果:

            1


            看着自己写的代码,小史仍是不由得赞赏。


             热 文 推 荐 

             2019年6月 阿里面试题汇总(含答案)

            今天问题

            共享你对朋友圈个数问题的了解?

            大众号后台发送“爬虫”,即可获取“零根底学爬虫专栏”系列文章

            大众号后台回复“目录”:即可获取小编熬夜编列整理好的历史文章:微信面试算法:朋友圈个数问题

            目录截图如下可上下滑动):



            喜爱就点「在看」吧 !

            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP