算法面试点汇总

算法面试点汇总

我们会在这里介绍我所涉及到的算法相关的面试点内容，本篇内容持续更新

我们会介绍下述算法的相关面试点：

• 二分查找
• 冒泡排序
• 选择排序
• 插入排序
• 快速排序

二分查找

我们在这里介绍二分查找的面试点

二分查找算法

我们首先给出二分查找的基本算法：

/*第一套模板*/

public class Bsearch_1 {

    // 首先准备一个已经排序的数组
    static int[] array = {1,3,4,6,8,10,14,16,17,20};

    public static void main(String[] args) {

        // 我们直接假定一个需要查找的值
        int x = 14;

        // 我们需要定义最开始的左端点和右端点
        int l = 0,r = array.length - 1;

        // 进行二分查找，对两者中间点判断，并根据中间点与查找点的关系修改端点值
        while (l <  r){

            int mid = (l+r)/2;

            if (array[mid] >= x){
                r = mid;
            }else {
                l = mid +1;
            }

        }

        // 最后出来是必定是l==r,这时l就是结果所在位置
        System.out.println(array[l]);
    }

}

/*第二套模板*/

public class Bsearch_2 {

    // 首先准备一个已经排序的数组
    static int[] array = {1,3,4,6,8,10,14,16,17,20};

    public static void main(String[] args) {

        // 我们直接假定一个需要查找的值
        int x = 4;

        // 我们需要定义最开始的左端点和右端点
        int l = 0,r = array.length - 1;

        // 进行二分查找，对两者中间点判断，并根据中间点与查找点的关系修改端点值
        while (l <  r){

            // 注意这里：(l+r+1)/2
            int mid = (l+r+1)/2;

            if (array[mid] <= x){
                l = mid;
            }else {
                r = mid - 1;
            }

        }

        // 最后出来是必定是l==r并且该值就是查找值（若存在）
        System.out.println(array[l]);
    }

}

/*第三套模板*/

public class Bsearch_3 {


    // 首先准备一个已经排序的数组
    static int[] array = {1,3,4,6,8,10,14,16,17,20};

    public static void main(String[] args) {

        // 我们直接假定一个需要查找的值
        int x = 14;

        // 我们需要定义最开始的左端点和右端点
        int l = 0,r = array.length - 1;

        // 这里我们直接一直判断到l<=r
        while (l <= r){

            int mid = (l+r)/2;

            // 这里我们对各种情况进行罗列，不用担心边界问题
            if (array[mid] > x){
                r = mid - 1;
            }else if(array[mid] < x){
                l = mid + 1;
            }else {
                System.out.println(array[l]);
                break;
            }

        }
        
        // 最后查找不到，我们可以选择输出
        // return -1;
        
    }

}

二分查找mid定义问题

我们会注意到上述其实有两套模板，其中根据其check条件而修改mid的值：

int Bsearch_2(int l,int r){
    
    // 区间[l,r]划分为[l,mid - 1]和[mid,r]使用
    
    // 首先对整个数组进行遍历
    while(l < r){
        
        // 约定一个起始的分界点
        int mid = (l+r+1)/2;
        
        // 对该分界点进行判定
        if(check(mid)){
            // 如果满足条件时该点在[mid,r]之间
            l = mid;
        } else {
            // 如果不满足条件，说明该点在[l,mid - 1]之间
            r = mid - 1;
        }
        
    }
    
    // 最后我们l==r，这个点就是我们二分查找出来的点
    return l;
}

/*
上述是+1的模板，我们+1的根本原因是因为边界问题，

因为我们将边界设置为l=mid，所以我们才需要对mid的赋值进行+1操作

因为我们的int类型是向下整分的，也就是2.5会变为2

那么如果我们的l = r - 1，这种情况下，我们的将l = mid = （l + l + 1）/2，这时l不会发生变化，我们的范围还是[l,r]不改变

因此为了避免无限循环，所以我们需要将mid的值加上0.5(1)，这时我们再将l = mid，l就会向前进1，这时就不会发生循环
*/

二分查找数值越界问题

我们的数组如果在正数范围的临界值，我们的mid操作可能会导致数值越界导致错误：

/*数组越界问题*/

public class Bsearch_1 {
    
    // INT类型最大值
    final int MAXINT = 32767;

    // 当我们设置一个较大的临界数组时
    static int[] array = new int[MaxInt];

    public static void main(String[] args) {

        int x = 14;

        int l = 0,r = array.length;

        while (l <  r){

            // 我们这里还采用l+r的话就会导致下标越界，从而变为负数，而数组还不存在负数，导致算法出错
            int mid = (l+r)/2;

            if (array[mid] > x){
                r = mid;
            }else {
                l = mid +1;
            }

        }

        System.out.println(array[l]);
    }

}

我们可以采用两种方法进行修改防止下标越界：

/*数学类解决方法：提前除2，采用+，-并行的方法*/

public class Bsearch_1 {
    
    // INT类型最大值
    final int MAXINT = 32767;

    // 当我们设置一个较大的临界数组时
    static int[] array = new int[MaxInt];

    public static void main(String[] args) {

        int x = 14;

        int l = 0,r = array.length;

        while (l <  r){

            // 我们下面其实就是l/2+r/2,但由于是正数，可能会出现数据相除后误差，我们一个采用-，一个采用+来消减除以2的误差
            int mid = l + (-l/2 + r/2);

            if (array[mid] > x){
                r = mid;
            }else {
                l = mid +1;
            }

        }

        System.out.println(array[l]);
    }

}

/*位运算解决方法：直接采用位运算来处理*/

public class Bsearch_1 {
    
    // INT类型最大值
    final int MAXINT = 32767;

    // 当我们设置一个较大的临界数组时
    static int[] array = new int[MaxInt];

    public static void main(String[] args) {

        int x = 14;

        int l = 0,r = array.length;

        while (l <  r){

            // 我们之所以出现数组越界问题，是因为使用(l+r)/2时，最高位会被当作+-号判断来处理
            // 所以我们只需要采用位运算，将其向右移动一位，就可以去除掉+-号的那一位，从而相当于进行除数运算
            
            // 无符号右移(>>>):无符号右移则始终补0，不考虑正负数。
            int mid = (l+r) >>> 1;

            if (array[mid] > x){
                r = mid;
            }else {
                l = mid +1;
            }

        }

        System.out.println(array[l]);
    }

}

二分查找面试题技巧

如果我们在面试中需要手写二分查找代码：

• 我们这里推荐使用模板1或模板2

如果我们在面试中需要计算二分查找次数：

• 我们需要采用模板3（默认JDK中的Arrays类中binarySearch方法）来进行计算
• 如果数组为奇数，我们直接取中间值
• 如果数组为偶数，我们取两个中间值靠左的值

冒泡排序

我们在这里介绍冒泡排序的面试点

冒泡排序基础算法

我们首先给出冒泡排序的暴力算法：

public class Increase_1 {

    // 我们首先给出一组不规则的数组
    static int[] array = {5,2,7,4,1,3,8,9};

    public static void main(String[] args) {

        // 冒泡排序就是遍历数组，每次遍历所有元素， 使当前元素和下一个元素对比，若当前元素大于下一个元素，就进行交换

        // 这一层循环：代表需要循环的总次数
        for (int i = 0; i < array.length - 1; i++) {
            // 这一层循环：代表每次循环数组中的数据个数
            for (int j = 0; j < array.length - 1; j++) {
                // 进行判断，如果当前值大于下一个数，就进行交换
                if (array[j] > array[j+1]){
                    swap(j,j+1);
                }
            }
        }

        // 最后打印排序后的数组判断是否正确
        for (int i: array) {
            System.out.print(i + " ");
        }

    }

    /**
     * 交换算法
     * @param a
     * @param b
     */
    public static void swap(int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

冒泡排序基础两重优化

我们可以针对上述的基础算法进行两层优化：

/*数组内部优化*/

public class Increase_2 {
    
    static int[] array = {5,2,7,4,1,3,8,9};

    public static void main(String[] args) {
        
        for (int i = 0; i < array.length - 1; i++) {
            // 这里，我们将遍历数的极限改为array.length-i-1
            // 因为每次循环，我们都可以确定最新的最后一位一定已经归位了，所以我们可以减少内部的遍历次数
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j+1]){
                    swap(j,j+1);
                }
            }
        }
        
        for (int i: array) {
            System.out.print(i + " ");
        }

    }
    
    public static void swap(int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

/*数组整体次数优化*/

public class Increase_3 {

    static int[] array = {5,2,7,4,1,3,8,9};

    public static void main(String[] args) {

        for (int i = 0; i < array.length - 1; i++) {

            // 当我们提前完成排序时，明明排序已经结束，但foreach循环仍在继续
            // 所以我们可以设置一个判断条件，如果排序已经结束，我们就提前结束掉循环
            boolean isFinished = false;

            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j+1]){
                    swap(j,j+1);
                    // 如果进行交换，说明还没有结束
                    isFinished = true;
                }
            }

            // 我们在每次循环结束时，进行判断，如果排序结束直接跳出循环
            if (!isFinished){
                break;
            }
        }

        for (int i: array) {
            System.out.print(i + " ");
        }

    }

    public static void swap(int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

冒泡算法非常规最优解

最后我们给出一个非常规的冒泡算法思想：

public class Increase_Best {

    static int[] array = {5,2,7,4,1,3,8,9};

    public static void main(String[] args) {

        // 最开始肯定是数组整体，n = array.length - 1
        // 我们设置n为每次运算的数组截至位置（注意这里是每次循环的结束点）
        int n = array.length - 1;

        while (true){

            // 我们设置一个数，表示我们下次应该遍历到哪里（只有最后所交换的下标值才是下一次遍历的位置）
            int turnInt = 0;

            // 我们每次遍历到n，n第一次是全部，后面都是由turnInt赋值的最后一次交换位置
            for (int i = 0; i < n; i++) {
                // 我们记录每次交换时的位置，但是turnInt只会保存我们最后一次交换的下标
                if (array[i] > array[i+1]){
                    swap(i,i+1);
                    turnInt = i;
                }
            }

            // 将最后一次交换下标作为下一次的遍历结束点
            n = turnInt;

            // 当我们的turnInt = 0时就表示整个数组已经遍历结束了，我们就可以跳出循环
            if (turnInt == 0){
                break;
            }

        }

        for (int i: array) {
            System.out.print(i + " ");
        }

    }

    public static void swap(int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

选择排序

我们在这里介绍选择排序的面试点

选择排序算法

我们这里直接给出选择排序的具体算法：

public class SelectSort {

    // 首先我们准备一个未排序的数组
    static int[] array = {5,2,7,4,1,3,8,9};

    public static void main(String[] args) {

        // 选择排序思想：将数组划分为已排序和未排序的两侧，在未排序的数组中每次寻找一个当前最小值加入已排序数组中

        // 我们需要遍历array.length - 1次(最后只剩一个元素时，就不需要交换了，肯定是排序正确的)
        for (int i = 0; i < array.length - 1; i++) {
            // 我们首先需要一个数，表示我们当前需要交换的已排序数组的交换位置
            int s = i;
            // 遍历未排序数组的所有数，找到最小的值
            for (int j = i; j < array.length; j++) {
                // 判断，如果当前值小于我们已找到的最小值，就将下标赋予s
                if (array[s] > array[j]){
                    s = j;
                }
            }
            // 在当前循环结束后，我们找到的s就是最小值的下标，如果s ！= i就需要进行交换
            if (s != i){
                swap(s,i);
            }
        }

        // 最后打印一下查看是否排序成功
        for (int i: array) {
            System.out.print(i + " ");
        }

    }

    /**
     * 交换算法
     * @param a
     * @param b
     */
    public static void swap(int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

}

选择排序和冒泡排序对比

首先我们需要知道两者的时间复杂度是相同的：

• 两者时间复杂度均为O(n^2)

其次我们需要判断选择排序和冒泡排序的速度比：

• 当正常情况下，选择排序是优于冒泡排序的，因为交换次数较少
• 但如果数组的整齐度高，那么冒泡排序是优于选择排序的

最后我们需要介绍一个稳定性概念：

• 稳定性：当数组中出现相同元素时，稳定性算法在排序过程中不会改变相同元素的位置；但非稳定性算法会改变相同元素的位置
• 选择排序是非稳定性算法；冒泡排序为稳定性算法

插入排序

我们在这里介绍插入排序的面试点

插入排序算法

我们这里直接给出插入排序的具体算法：

public class InsertSort {

    // 首先我们准备一个未排序的数组
    static int[] array = {5,2,7,4,1,3,8,9};

    public static void main(String[] args) {

        // 插入排序思想：我们同样将数组划分为已排序和未排序
        // 我们将已排序的数组按照递增形式储存，我们每次找未排序数组的第一个元素来加入到已排序数组

        // 当元素只有1个时不需要排序，所以我们的i从1开始
        for (int i = 1; i < array.length; i++) {

            // 我们当前i就是未排序数组的第一位，我们取出来
            int t = array[i];

            // 这里j表示已排序数组最后一位
            int j = i - 1;

            // 我们的j设置为已排序数组的最后一位，从后往前遍历(当j = -1时结束循环)
            while (j >= 0){
                // 我们的已排序数组需要按照从小到大的顺序，所以我们进行数据比较
                if (t < array[j]){
                    // 如果t < array[j]：那么说明t应该放在前面的位置，那么我们将j+1位置的值变为j
                    // （注意：j+1位置的值为t或者已经被赋值给后面的值了）
                    array[j+1] = array[j];
                }else {
                    // 如果t > array[j]:那么说明应该放在j的后面，我们直接跳出循环，在外面赋值
                    break;
                }

                // 持续循环，直到结束
                j--;

            }

            // 我们在这里统一赋值t，因为有可能全部遍历，t均小于array[j]，那么t就应该放在第0下标位置
            array[j+1] = t;

        }

        // 最后打印一下查看是否排序成功
        for (int a: array) {
            System.out.print(a + " ");
        }

    }

}

插入排序优化算法

我们在这里介绍一个插入排序的优化算法思想：

/*希尔排序*/

由于面试中并不经常考察希尔排序算法，我们在这里仅给出思路
    
/*产生原因*/
    
由于插入排序会进行多次的数据交换（将已排序数组中的高位值移动到高位）
如果我们的数组前面的值均为大值，就会导致进行多次数据交换，从而导致时间较长
    
/*解决思想*/
    
我们每次间隔n个数，将0，n，n*2,n*3...n*？下标的数，进行插入排序运算

目的就是为了让较大值在不进行多次移动情况下快速到达后面的位置
    
我们可以采用2的n次方的数来进行运算，比如第一个相隔n位，第二次就相隔n/2位...直到n=1，进行原始的插入排序即可

插入排序和选择排序对比

首先我们需要知道两者的时间复杂度是相同的：

• 两者时间复杂度均为O(n^2)
• 但是有序情况下插入排序的时间复杂度为O(n)

其次我们需要判断插入排序和选择排序的速度比：

• 大部分情况下插入排序都是优于选择排序

最后就是稳定性对比：

• 插入排序是稳定性的；选择排序不是稳定性的

快速排序

我们在这里介绍快速排序的面试点

快速排序基础算法

我们首先依照快速排序的两种思路写出两种快速排序方法：

/*单边快速排序*/

单边循环快排：

    1.选择最右元素作为基准点元素，ij均从最左侧开始
    2.j指针负责找到比基准点小的元素，一旦找到与i进行交换
    3.i指针负责找到比基准点大的元素，一旦找到，等待j指针找到并交换
    4.最后基准点与i进行交换，作为分区点，然后对左右两边进行递归循环直到排序成功
    
/*双边快速排序*/
    
双边循环快排：
    
    1.选择最左元素作为基准点
    2.j指针从右侧开始查找比基准点小的元素，找到后停留在该点
    3.i指针从左侧开始查找比基准点大的元素，找到后停留在该点
    4.注意判断i < j ? swap(a[i],a[j]) : break
    5.最后交换基准点和i的位置
    
/*注意点*/
    
由于上面两种属于官方算法，会出现限制条件：
    1.我们在进行i，j移动时，可以一直判断是否iwhile(i < j && a[j] < findInt)）
    2.我们在i,j判断时，我们需要先进行j指针循环，在进行i指针循环，并且需要给i指定为>=的条件，否则可能出现无限循环或者排序错误

快速排序优化算法

我现在给出的整个快排算法是Acming中闫老师给出的算法，我们的面试尽量书写这个算法：

/*快排优化算法*/

import java.util.Scanner;

public class quick_sort {
    public static void main(String[] args) {
        // 输入数组的数量和数组的值

        int n;

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        int[] ints = new int[n];

        for (int i = 0 ; i < n;i++){
            ints[i] = scanner.nextInt();
        }

        // 展示数组

        System.out.print("排序前：");
        for (int i = 0; i < n; i++) {
            System.out.print(ints[i] + " ");
        }
        System.out.println(" ");

        // 进行快速排序
        quick_sort(ints,0,n-1);

        // 展示数组

        System.out.print("排序后：");
        for (int i = 0; i < n; i++) {
            System.out.print(ints[i] + " ");
        }
        System.out.println(" ");
    }

    public static void quick_sort(int[] ints,int l,int r){

        // 整个循环判断条件：l >= r,说明该区间已经不是区间了，停止排序
        while (l >= r){
            return;
        }

        // 我们的quick采用双指针算法，从左右两侧分别使用i，j寻找比mid值大的数和比mid值小的数（mid属于随机取的一个数）
        int mid = (l+r)/2;

        // 我们开始位置为区间的两侧外侧，因为里面我们采用的是先++，后判断
        int i = l - 1 ,j = r + 1 ;

        // 循环判断条件：l < r
        while (i < j){

            // l，r没有顺序限制，i负责寻找大于等于mid的值，j负责寻找小于等于mid的值

            while ( ints[++i] < ints[mid]);

            while ( ints[--j] > ints[mid]);

            // 最后进行i，j交换，在进行交换之前，需要先判断，防止交换的位置已经是经过排序的顺序
            if (i < j){
                int temp = ints[i];
                ints[i] = ints[j];
                ints[j] = temp;
            }

        }

        // 当该位置点左右两侧排序结束后，该点左侧都是小于等于该点的值，该点右侧都是大于等于该点的值，我们无法确定x在哪一侧

        // 我们还需要对截至点的左右两侧区间进行循环(我们在进行循环时，其实还是有将mid的那个点再次进入排序中去)
        quick_sort(ints,l,i);
        quick_sort(ints,i + 1,r);

    }
}

结束语

目前关于算法的面试点就到这里，该篇内容将会持续更新~

附录

参考资料：

1. 黑马Java八股文面试题视频教程：基础篇-02-二分查找_演示_哔哩哔哩_bilibili

2. 竞赛Acwing闫老师视频教程：AcWing