乐趣区

关于java:算法很美听我讲完这些Java经典算法包你爱上她

大家好,我是小羽。

对于编程来说的话,只有把握了算法才是理解了 编程的灵魂,算法对于老手来说的话,属实有点难度,然而当前想有更好的倒退,失去更好的进阶的话,对算法进行零碎的学习是重中之重的。

对于 Java 程序员来说,这一门后端语言只是咱们的外功,咱们更多的是学习它的语法,框架以及一些工具的应用。而算法才是咱们真正的内功,它更多的是关注如何设计零碎,如何编写高性能的代码,一直 造就咱们的思维能力,从而晋升咱们的工作效率。

小羽明天为大家介绍的是对于 Java 中咱们须要理解的一些经典算法,心愿大家能从这些经典算法中,品味到算法的美好与奇异,对她产生趣味,更好的为咱们的职业倒退助力前行。好了,开始进入咱们的注释:

二分查找

简介

根本思维 :又叫折半查找,要求待查找的序列 有序,是一种疾速查找算法,工夫复杂度为 O(logn),要求数据集为一个有序数据集。

应用

利用场景 :个别用于 查找数组 元素,并且数组在查找之前必须曾经排好序(个别是升序)。

步骤

1、取 两头地位 的值与待查关键字比拟,如果两头地位的值比待查关键字大,则在前半部分循环这个查找的过程,

2、如果两头地位的值比待查关键字小,则在后半局部循环这个查找的过程。

3、直到 查找到了 为止,否则序列中没有待查的关键字。

代码示例:

public static int biSearch(int []array,int a){
    int lo=0;
    int hi=array.length-1;
    int mid;
    while(lo<=hi){mid=(lo+hi)/2;// 两头地位
        if(array[mid]==a){return mid;}else if(array[mid]<a){ // 向右查找
            lo=mid+1;
        }else{ // 向左查找
            hi=mid-1;
        } 
  }
    return -1;
}

冒泡排序算法

简介

根本思维 :比拟 前后相邻 的两个数据,如果后面数据大于前面的数据,就将这二个数据交换。这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后,最大的一个数据就“沉”到数组第 N-1 个地位。N=N-1,如果 N 不为 0 就反复后面二步,否则排序实现。

应用

利用场景 :数据量不大,对稳定性有要求,且数据根本 有序 的状况。

步骤

1、将序列中所有元素两两比拟,将最大的放在最初面。

2、将残余序列中所有元素两两比拟,将最大的放在最初面。

3、反复第二步,直到只剩下 一个数

代码示例:

public static void bubbleSort1(int [] a, int n){
    int i, j;
    for(i=0; i<n; i++){// 示意 n 次排序过程。for(j=1; j<n-i; j++){if(a[j-1] > a[j]){// 后面的数字大于前面的数字就替换
                // 替换 a[j-1]和 a[j]
                int temp;
                temp = a[j-1];
                a[j-1] = a[j];
                a[j]=temp;
            } 
    }
  }
}

插入排序算法

简介

根本思维 :通过构建有序序列,对于未排序数据,在已排序序列中 从后向前 扫描,找到相应的地位并插入。

应用

利用场景 :数据量不大,对算法的稳定性有要求,且数据 部分或者整体 有序的状况。

步骤

1、将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最初一个元素当成是未排序序列。

2、从头到尾 顺次扫描未排序序列,将扫描到的每个元素插入有序序列的适当地位。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的前面。)

代码示例

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不扭转参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为 1 的元素开始抉择适合的地位插入,因为下标为 0 的只有一个元素,默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从曾经排序的序列最左边的开始比拟,找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数,插入
            if (j != i) {arr[j] = tmp;
            }

        }
        return arr;
    }
}

疾速排序算法

简介

根本思维 :抉择一个要害值作为 基准值。比基准值小的都在右边序列(个别是无序的),比基准值大的都在左边(个别是无序的)。个别抉择序列的第一个元素。

应用

利用场景 数值 范畴较大,雷同值的概率较小,数据量大且不思考稳定性的状况,数值远大于数据量时威力更大。

步骤

1、一次循环,从后往前 比拟,用基准值和最初一个值比拟,如果比基准值小的替换地位,如果没有持续比拟下一个,直到找到第一个比基准值小的值才替换。

2、找到这个值之后,又 从前往后 开始比拟,如果有比基准值大的,替换地位,如果没有持续比拟下一个,直到找到第一个比基准值大的值才替换。

3、直到从前往后的比拟索引 > 从后往前比拟的索引,完结第一次循环,此时,对于 基准值 来说,左右两边就是有序的了。

代码示例:

public void sort(int[] a,int low,int high){
    int start = low;
    int end = high;
    int key = a[low]; 
        while(end>start){
            // 从后往前比拟
            while(end>start&&a[end]>=key) 
                // 如果没有比要害值小的,比拟下一个,直到有比要害值小的替换地位,而后又从前往后比拟
                end--;
            if(a[end]<=key){int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            // 从前往后比拟
            while(end>start&&a[start]<=key)
                // 如果没有比要害值大的,比拟下一个,直到有比要害值大的替换地位
                start++;
            if(a[start]>=key){int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        // 此时第一次循环比拟完结,要害值的地位曾经确定了。右边的值都比要害值小,左边的值都比要害值大,然而两边的程序还有可能是不一样的,进行上面的递归调用
        }
        // 递归
        if(start>low) sort(a,low,start-1);// 右边序列。第一个索引地位到要害值索引 -1
        if(end<high) sort(a,end+1,high);// 左边序列。从要害值索引 +1 到最初一个
    }
}

希尔排序算法

简介

根本思维 :先将整个待排序的记录序列宰割成为若干子序列别离进行间接插入排序,待整个序列中的记录“ 根本有序”时,再对整体记录进行顺次间接插入排序。

应用

利用场景 :数据量较大,不要求 稳定性 的状况。

步骤

1、抉择一个增量序列 t1,t2,…,tk,其中 ti>tj,tk=1;

2、按增量序列个数 k,对序列进行 k 趟排序;

3、每趟排序,依据对应的增量 ti,将待排序列宰割成若干长度为 m 的子序列,别离对各子表进行 间接 插入排序。仅增量因子为 1 时,整个序列作为一个表来解决,表长度即为整个序列的长度。

代码示例

private void shellSort(int[] a) {
    int dk = a.length/2; 
    while(dk >= 1){ShellInsertSort(a, dk); 
        dk = dk/2;
    }
}

private void ShellInsertSort(int[] a, int dk) {
    // 相似插入排序,只是插入排序增量是 1,这里增量是 dk, 把 1 换成 dk 就能够了
    for(int i=dk;i<a.length;i++){if(a[i]<a[i-dk]){
            int j;
            int x=a[i];//x 为待插入元素
            a[i]=a[i-dk];
            for(j=i-dk; j>=0 && x<a[j];j=j-dk){
                // 通过循环,一一后移一位找到要插入的地位。a[j+dk]=a[j];
            }
            a[j+dk]=x;// 插入
        }
  }
}

归并排序算法

简介

根本思维 :归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。而后再把有序子序列 合并 为整体有序序列。

场景应用

利用场景 :内存少的时候应用,能够进行 并行计算 的时候应用。

步骤

1、抉择 相邻 两个数组成一个有序序列。

2、抉择相邻的两个有序序列组成一个有序序列。

3、反复第二步,直到全副组成一个 有序 序列。

代码示例

public class MergeSortTest {public static void main(String[] args) {int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7}; 
        print(data); 
        mergeSort(data); 
        System.out.println("排序后的数组:"); 
        print(data); 
    } 

  public static void mergeSort(int[] data) {sort(data, 0, data.length - 1); 
    } 

  public static void sort(int[] data, int left, int right) {if (left >= right) 
            return; 
        // 找出两头索引
        int center = (left + right) / 2; 
        // 对右边数组进行递归
        sort(data, left, center); 
        // 对左边数组进行递归
        sort(data, center + 1, right); 
        // 合并
        merge(data, left, center, right); 
        print(data); 
    } 
  
    /** 
    * 将两个数组进行归并,归并后面 2 个数组已有序,归并后仍然有序
    * @param data 
    * 数组对象
    * @param left 
    * 左数组的第一个元素的索引
    * @param center 
    * 左数组的最初一个元素的索引,center+1 是右数组第一个元素的索引
    * @param right 
    * 右数组最初一个元素的索引
    */ 
    public static void merge(int[] data, int left, int center, int right) { 
        // 长期数组
        int[] tmpArr = new int[data.length]; 
        // 右数组第一个元素索引
        int mid = center + 1; 
        // third 记录长期数组的索引
        int third = left; 
        // 缓存左数组第一个元素的索引
        int tmp = left; 
        while (left <= center && mid <= right) { 
            // 从两个数组中取出最小的放入长期数组
            if (data[left] <= data[mid]) {tmpArr[third++] = data[left++]; 
            } else {tmpArr[third++] = data[mid++]; 
            } 
        } 
        // 残余局部顺次放入长期数组(实际上两个 while 只会执行其中一个)while (mid <= right) {tmpArr[third++] = data[mid++]; 
        } 
        while (left <= center) {tmpArr[third++] = data[left++]; 
        } 
        // 将长期数组中的内容拷贝回原数组中
        //(原 left-right 范畴的内容被复制回原数组)while (tmp <= right) {data[tmp] = tmpArr[tmp++]; 
        } 
    } 
  
    public static void print(int[] data) {for (int i = 0; i < data.length; i++) {System.out.print(data[i] + "\t"); 
        } 
        System.out.println();} 
}

桶排序算法

简介

根本思维 :把数组 arr 划分为 n 个 大小雷同 子区间(桶),每个子区间各自排序,最初合并。计数排序是桶排序的一种非凡状况,能够把计数排序当成每个桶里只有一个元素的状况。

应用

利用场景 :在数据量十分大,而 空间绝对富余 的时候是很实用的,能够大大降低算法的运算数量级。

步骤

1、找出待排序数组中的最大值 max、最小值 min

2、咱们应用 动静数组 ArrayList 作为桶,桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1

3、遍历数组 arr,计算每个元素 arr[i] 放的桶

4、每个桶各自排序

代码示例

public static void bucketSort(int[] arr){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    // 创立桶
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){bucketArr.add(new ArrayList<Integer>());
    }
    // 将每个元素放入桶
    for(int i = 0; i < arr.length; i++){int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    // 对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){Collections.sort(bucketArr.get(i));
    }
}

基数排序算法

简介

根本思维 :将所有待比拟数值(正整数)对立为同样的数位长度,数位较短的数后面补零。而后,从 最低位 开始,顺次进行一次排序。这样从最低位排序始终到最高位排序实现当前, 数列就变成一个有序序列。

应用

利用场景 :用于大量数, 很长的数 进行排序时的状况。

步骤

1、将所有的数的 个位数 取出,依照个位数进行排序,形成一个序列。

2、将新形成的所有的数的 十位数 取出,依照十位数进行排序,形成一个序列。

代码示例

public class radixSort {inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};
    
  public radixSort(){sort(a);
        for(inti=0;i<a.length;i++){System.out.println(a[i]);
        }
  }
  
    public void sort(int[] array){
        // 首先确定排序的趟数;
        int max=array[0];
        for(inti=1;i<array.length;i++){if(array[i]>max){max=array[i];
            }
    }
        int time=0;
        // 判断位数;
        while(max>0){
            max/=10;
            time++;
        }
        // 建设 10 个队列;
        List<ArrayList> queue=newArrayList<ArrayList>();
        for(int i=0;i<10;i++){ArrayList<Integer>queue1=new ArrayList<Integer>();
            queue.add(queue1);
        }
        // 进行 time 次调配和收集;
        for(int i=0;i<time;i++){
            // 调配数组元素;
            for(intj=0;j<array.length;j++){
                // 失去数字的第 time+1 位数;
                int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
                ArrayList<Integer>queue2=queue.get(x);
                queue2.add(array[j]);
                queue.set(x, queue2);
            }
            int count=0;// 元素计数器;
            // 收集队列元素;
            for(int k=0;k<10;k++){while(queue.get(k).size()>0){ArrayList<Integer>queue3=queue.get(k);
                    array[count]=queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
      }
    }
  }
}

剪枝算法

简介

根本思维 :在搜索算法中优化中,剪枝,就是通过某种判断,防止一些不必要的遍历过程,形象的说,就是剪去了搜寻树中的某些“枝条”,故称剪枝。利用剪枝优化的外围问题是 设计剪枝判断办法,即确定哪些枝条该当舍弃,哪些枝条该当保留的办法。

应用

利用场景 :通常利用在 DFSBFS 搜索算法中,寻找 过滤条件,提前缩小不必要的搜寻门路。

步骤

1、基于训练数据集生成 决策树,生成的决策树要尽量大;

2、用验证数据集最已生成的树进行剪枝并抉择 最优子树,这时用损失函数最小作为剪枝的规范

代码示例

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);
        LinkedList<Integer> track = new LinkedList<>();
        combinationSum(candidates, 0, target, track);
        return result;
    }

    private List<List<Integer>> result = new ArrayList<>();

    private void combinationSum(int[] candidates, int start, int target, LinkedList<Integer> track) {if (target < 0) {return;} else if (target == 0) {result.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < candidates.length; i++) {if (target < candidates[i]) {break;}
            track.add(candidates[i]);
            combinationSum(candidates, i, target - candidates[i], track);
            track.removeLast();}

    }
}

回溯算法

简介

根本思维 :回溯算法实际上一个相似枚举的搜寻尝试过程,次要是在 搜寻尝试过程中 寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的门路。

应用

利用场景 :设置一个递归函数,函数的参数会携带一些以后的可能解的信息,依据这些参数得出可能解或者不可能而回溯,平时常常见的有 N 皇后、数独、汇合 等状况。

步骤

1、定义一个 解空间,它蕴含问题的解;

2、利用适于搜寻的办法组织解空间;

3、利用深度优先法搜寻解空间;

4、利用限界函数防止挪动到不可能产生解的子空间。

代码示例

function backtrack(n, used) {
    // 判断输出或者状态是否非法
    if (input/state is invalid) {return;}
    // 判读递归是否该当完结,满足完结条件就返回后果
    if (match condition) {return some value;}
    // 遍历以后所有可能呈现的状况,并尝试每一种状况
    for (all possible cases) {
        // 如果上一步尝试会影响下一步尝试,须要写入状态
        used.push(case)
        // 递归进行下一步尝试,搜寻该子树
        result = backtrack(n + 1, used)
        // 在这种状况下曾经尝试结束,重置状态,以便于上面的回溯尝试
        used.pop(case)
    } 
}

最短门路算法

简介

根本思维 :从某顶点登程,沿图的边达到另一顶点所通过的门路中, 各边上权值之和最小 的一条门路叫做最短门路。解决最短路的问题有以下算法,Dijkstra 算法,Bellman-Ford 算法,Floyd 算法和 SPFA 算法等。

应用

利用场景 :利用有计算机网络路由算法,机器人探路, 交通路线导航,人工智能,游戏设计等。

步骤:(Dijkstra 算法示例)

1、拜访路网中里 起始点最近且没有被查看过 的点,把这个点放入 OPEN 组中期待查看。

2、从 OPEN 表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到 CLOSE 表中。

3、遍历考查这个点的子节点。求出这些子节点距起始点的间隔值,放子节点到 OPEN 表中。

4、反复 2,3,步。直到 OPEN 表为空,或找到指标点。

代码示例

//Dijkstra 算法
static int[] pathSrc = new int[9];
static int[] shortPath = new int[9];
static void shortestPath_DijkStra(MGraph m, int v0) {// finalPath[w] = 1 示意曾经获取到顶点 V0 到 Vw 的最短门路    
    int[] finalPath = new int[9];    
    for (int i = 0; i < m.numVertexes; i++) {finalPath[i] = 0;        
        shortPath[i] = m.arc[v0][i];        
        pathSrc[i] = 0;    
    }    
    // v0 到 v0 的门路为 0    
    shortPath[v0] = 0;    
    // vo 到 v0 不需要求门路    
    finalPath[v0] = 1;    
    for (int i = 1; i < m.numVertexes; i++) {        
        // 以后所知的离 V0 最近的间隔        
        int min = INFINITY;        
        int k = 0;        
        for (int w = 0; w < m.numVertexes; w++) {if(shortPath[w] < min && finalPath[w] == 0) {min = shortPath [w];                
                k = w;            
            }        
        }  
        finalPath[k] = 1; // 批改 finalPath 的值,标记为曾经找到最短门路
        for (int w = 0; w < m.numVertexes; w++) {            
            // 如果通过 V 顶点的门路比原来的门路(不通过 V)短的话            
            if(finalPath[w] == 0 && (min + m.arc[k][w]) < shortPath[w]) {       
                // 阐明找到了更短的门路,批改                
                shortPath[w] = min + m.arc[k][w]; // 批改门路的长度
                pathSrc[w] = k; // 批改顶点下标 W 的前驱顶点
            }        
        }    
    }
}

最大子数组算法

简介

根本思维 :给定一个整数数组 nums,找到一个具备 最大和 的间断子数组(子数组起码蕴含一个元素),返回其最大和。

应用

利用场景 :生存中能够用来查看股票一周之内的 增长状态,须要失去最合适的买入和卖出工夫。

步骤

1、将子串和为正数的子串丢掉,只留 和为正 的子串。

2、如果 nums 中有负数,从左到右遍历 nums,用变量 cur 记录每一步的累加和,遍历到负数 cur 减少,遍历到正数 cur 缩小。

3、当 cur>=0 时,每一次累加都可能是最大的累加和,所以,用另外一个变量 max 全程跟踪记录 cur 呈现的 最大值 即可。

代码示例

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    int maxSubArray(vector<int> nums) {if(nums.size()<=0){return 0;} 
        int max=INT_MIN,cur=0;//c++ 最小值
        for(int i=0; i<nums.size(); i++)  
        {if(cur < 0)
                cur = nums[i];// 如果后面加起来的和小于 0,摈弃后面的
            else
                cur+=nums[i];
 
            if(cur > max)
                max = cur;
        }  
        return max;  
        
    }
};

最长公共子序算法

简介

根本思维 :最长公共子序列是一个在一个序列汇合中用来查找所有序列中 最长子序列 的问题。这与查找最长公共子串的问题不同的中央是:子序列不须要在原序列中占用间断的地位。

应用

利用场景 :最长公共子序列问题是一个经典的计算机科学问题,也是 数据比拟程序 ,比方 Diff 工具,和生物信息学利用的根底。它也被宽泛地利用在 版本控制,比方 Git 用来和谐文件之间的扭转。

步骤

1、能够应用 递归 去解决,须要遍历出所有的可能,很慢;

2、对于个别的 LCS 问题,都属于 NP 问题;

3、当数列的量为肯定的时,都能够采纳 动静布局 去解决。

代码示例

class Solution {public int longestCommonSubsequence(String text1, String text2) {int length1 = text1.length();
        int length2 = text2.length();
        int[][] a = new int[length1 + 1][length2 + 1];// 0 行 0 列保留
        for(int i = 1; i <= length1; i++){for(int j = 1; j <= length2; j++){if (text1.charAt(i - 1) == text2.charAt(j - 1)) {a[i][j] = a[i - 1][j - 1] + 1;
                } else {if (a[i][j - 1] > a[i-1][j]) {a[i][j] = a[i][j - 1];
                    } else {a[i][j] = a[i - 1][j];
                    }
                }
            }
        }
        return a[length1][length2];
    }
}

最小生成树算法

简介

根本思维 :在含有 n 个顶点的 带权无向连通图 中抉择 n - 1 条边,形成一棵极小连通子图,并使该连通子图中 n - 1 条边上权值之和达到最小,则称其为连通网的最小生成树(不肯定惟一)。

个别状况,要解决最小生成树问题,通常采纳两种算法:Prim 算法 Kruskal 算法

应用

利用场景 :个别用来计算 老本最小化 的状况。

步骤:(Prim 算法示例)

1、以某一个点开始,寻找以后该点能够拜访的 所有的边

2、在曾经寻找的边中发现 最小边,这个边必须有一个点还没有拜访过,将还没有拜访的点退出咱们的汇合,记录增加的边;

3、寻找以后汇合能够拜访的所有边,反复 2 的过程,直到没有新的点能够退出;

4、此时由所有边形成的 即为最小生成树。

代码示例

/** prim 算法
    * @param first  形成最小生成树的终点的标识
    * @return  返回最小生成树形成的边
    */
public List<Edge> generateMinTreePrim(T first){
    // 存储最小生成树形成的边
    List<Edge> result=new LinkedList<>();
    // 首先建设 map,key 为 vertex,value 为 edge
    HashMap<Vertex<T>, Edge> map=new HashMap<>();
    Iterator<Vertex<T>> vertexIterator=getVertexIterator();
    Vertex<T> vertex;
    Edge edge;
    while(vertexIterator.hasNext()){
        // 一开始,value 为 edge 的两端的都为本人,weight=maxDouble
        vertex=vertexIterator.next();
        edge=new Edge(vertex, vertex, Double.MAX_VALUE);
        map.put(vertex, edge);
    }
    //first 是形成最小生成树的终点的标识
    vertex=vertexMap.get(first);
    if(vertex==null){System.out.println("没有节点:"+first);
        return result;
    }
    // 所有不在生成树中的节点,都是 map 的 key, 如果 map 为空,代表所有节点都在树中
    while(!map.isEmpty()){
        // 这次循环要退出生成树的节点为 vertex,边为 vertex 对应的 edge(也就是最小的边)edge=map.get(vertex);
        // 每将一个结点 j 退出了树 A,首先从 map 中去除这个节点
        map.remove(vertex);
        result.add(edge);
        System.out.println("生成树退出边,顶点:"+vertex.getLabel()+
                ",边的起点是:"+edge.getEndVertex().getLabel()+",边的权值为:"+edge.getWeight());;
        // 如果是第一个节点,对应的边是到本人的,删除
        if(vertex.getLabel().equals(first)){result.remove(edge);
        }
        // 而后看 map 中残余的节点到节点 j 的间隔,如果这个边的间隔小于之前边的间隔,就将边替换成这个到节点 j 的边
        // 在遍历替换中,同时发现间隔最短的边 minEdge
        Edge minEdge=new Edge(vertex, vertex, Double.MAX_VALUE);
        for(Vertex<T> now:map.keySet()){edge=map.get(now);
            //newEdge 为 now 到节点 j 的边
            Edge newEdge=now.hasNeighbourVertex(vertex);
            if(newEdge!=null&&newEdge.getWeight()<edge.getWeight()){
                // 如果这个边的间隔小于之前边的间隔,就将边替换成这个到节点 j 的边
                edge=newEdge;
                map.put(now, edge);
            }
            if(edge.getWeight()<minEdge.getWeight()){
                // 更新 minEdge
                minEdge=edge;
            }
        }
        // 这里设定边的方向是不在树上的 v(为起始点)到树上的 u
        // 这条边的起始点是不在树上的,是下一个退出生成树的节点
        vertex=minEdge.getBeginVertex();}        
    return result;
}

最初

算法无论是对于学习还是工作,都是必不可少的。如果说咱们把握了这些算法背地的 逻辑思维,那么是会对咱们的学习和工作有很好的促进作用的。

其次算法对于面试,尤其是进入 一些大厂 BAT 等公司 都是一块敲门砖,大公司都会通过算法来评估你的整体技术水平,如果你有很好的算法功底,置信对你将来的职场路线也会有很大帮忙。

在职业倒退前期,领有良好的算法技能,能够帮忙咱们更快、更高效的实现编码,往 架构师 的方向倒退,同样的岗位,你有相应的算法常识的话,能拿到的薪资也会比他人更好一点。

当然,算法远不止这些列举的,还有很多简单的算法须要去一直学习,一起加油吧~

退出移动版