面试题算法

发表于 | 分类于
面试题算法

面试题算法

  • 给定一个正数 a，求这个数的开方根，要求保留精度小数点后6位。

    方法1：二分法，定义最小区间

    方法2：牛顿法，在（xn，f（xn））做一条切线，与x轴的焦点

    方法3：梯度下降法

    https://blog.csdn.net/XX_123_1_RJ/article/details/87094129

  • 无向图的双连通性

    如果一个连通的无向图中的任一顶点被删除后，剩下的图仍然连通，则这样的无向连通图为双联通的。如果一个图不是双联通的，也就是存在一些顶点，将其删除后不再连通，这样的点称为割点和关节点。

    利用DFS求解所有割点：（太难了）

  • 在做编程题的时候，图一般是输入顶点，输入边，自己构建图。如果单纯只给出一个jpg的图结构，是无法遍历的。所以这里讲述根据输入的顶点、输入的边来构建图。

  • 判断图是否存在环

    • 无向图

      • DFS构建深度优先查找森林，看是否存在回边

        对于1-2-3-1的有环图

        每个节点存在三种状态，白、灰、黑，最开始所有节点为白色，当开始访问到某节点时节点变为灰色，当该节点的所有邻接点都遍历完，节点变为黑色。如果遍历的过程中发现某个节点有一条边指向的颜色为灰色的节点，那么存在环（并且该节点不是直接前驱，所以要维护一个father数组）。当回溯到节点1，虽然有一条边指向已经访问过的3，但是3已经是黑色，所以环不会被重复计算。

        下面的代码中visit数组的值分为0 1 2三种状态分别代表白色、灰色、黑色，调用函数dfs可以输出图中存在的所有环，图用邻接矩阵表示，如果两个节点之间没有边则对应的值为INT_MAX

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        package Graph;
        public class IfCircleInGraph {
            public static void main(String[] args){}

            public void dfsVisit(int[][] graph,int curnode,int[] visit,int[] father){
                int n=graph.length;
                visit[curnode]=1;
                for (int i=0;i<n;i++){
                    if (i!=curnode&&graph[curnode][i]!=Integer.MAX_VALUE){
                        if (father[curnode]!=i&&visit[i]==1){
                            System.out.println("find");
                        }
                        else if (visit[i]==0){
                            father[i]=curnode;
                            dfsVisit(graph,i,visit,father);
                        }
                    }
                }
                visit[curnode]=2;
            }
            public void dfs(int[][] graph){
                int n=graph.length;
                int[] visit=new int[n];//每个元素的值为0，1，2，分别代表白色、灰色、黑色，即节点被遍历的状态
                int[] father=new int[n];//father[i]的表示遍历过程中i的父节点
                for (int i=0;i<n;i++){
                    if (visit[i]==0){
                        dfsVisit(graph,i,visit,father);
                    }
                }
            }
        }

      • 根据无向图的度来进行判断（难点在于要先计算图中所有节点的度）

        1
        2
        3
        4
        5
        6
        我们知道对于环1-2-3-4-1，每个节点的度都是2，基于此我们有如下算法（这是类似于有向图的拓扑排序）：
        求出图中所有顶点的度，
        删除图中所有度<=1的顶点以及与该顶点相关的边，把与这些边相关的顶点的度减一
        如果还有度<=1的顶点重复步骤2
        最后如果还存在未被删除的顶点，则表示有环；否则没有环
        时间复杂度为O（E+V），其中E、V分别为图中边和顶点的数目，这个算法我们稍后分析算法3的时候再分析。

    • 有向图

      • 拓扑排序

        1
        2
        3
        4
        5
        1.计算图中所有节点的入度，将入度为0的节点加入栈
        2.如果栈非空
        	取出栈顶顶点a，输出顶点值，删除该顶点
        	从图中删除所有以a为起始点的边，如果删除的边的的另一个顶点入度修改后为0，入栈
        3.如果图中还存在顶点，则图中有环；否则输出的顶点就是一个拓扑排序的序列

      • 利用dfs实现拓扑排序

        按照节点标记为黑色的时间，越先被标记为黑色，在拓扑排序中越靠后。新建一个栈保存拓扑排序的结果。与上面的“无向图”代码基本相同，但额外需要在visit[curnode]=2;后将curnode入栈。

      • 利用BFS实现拓扑排序

  • TreeSet

    特点如下：TreeSet是用来排序的, 可以指定一个顺序, 对象存入之后会按照指定的顺序排列

    • 是Set的一个子类，保证了元素的唯一性
    • 底层用红黑树实现，可以保证元素插入的顺序，支持排序操作

    插入TreeSet的元素可以实现Comparable接口或者传入Comparator类，以实现对插入TreeSet的对象进行排序。

  • 求解$\sqrt{x}$

    • 梯度下降法
    • 牛顿法
    • 二分法

  • 利用梯度下降法求解矩阵方程$Ax=B$

  • 最小二乘法求解

    首先需要注意的是带了转置的向量$x^T$为行向量

    • 牛顿法（拟牛顿法）
    • 梯度下降法
    • 直接求导法

  • 找出无向图中任意两点的所有路径