大O表示法

参考：https://www.bilibili.com/video/BV1DY4y1H7DG

在开发的时候，我们如何评估一个算法的好坏，如何描述一个算法运行效率的高低呢？通俗一点的表达方法就是程序执行快或慢，但是这只是一种较为宽泛的描述，我们如何直观科学的用的描述它呢？

有同学可能会说，用其运行时间不就可以很好很直观的描述它了。不过，不同的语言，不同的编译器，不同的CPU来说，对程序的处理的时间是不同的，我们无法单单用运行时间来描述某个算法执行效率。另外，当需要处理的数据增长时，算法的基本操作要重复执行的次数也会增长，对于不同的算法的增长的速度也不一样。

数学果然是个不错的工具，为了描述算法的运行时间的增长情况，我们可以用不同数学公式来分析。在计算机科学上，我们是有专门的术语来表征算法的效率，就是大O表示法。大O并不是表示算法运行需要多长时间，它表示的是算法运行时间的增速，即算法的运行时间以不同的速度增加，也叫渐进时间复杂度。

我们可以用下面的表达式来表示：

T(n)=O(f(n))

通常主要有以下几种表达式来描述时间复杂度：

O(1)：常量时间
O(n)：线性时间
O(log n)：对数时间
O(n^2)：二次方时间
O(2^n)：指数时间
O(n!)：阶乘时间

O(1)

O(1)：是最低的时间复杂度，表示算法的速度和数量无关，不论数量是多少，算法的速度始终不变，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。

哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）。

O(n)

O(n)：也叫线性时间，表示算法的速度和数量增加呈现线性增长。

典型算法有：简单查找。

即在n个数中轮询查找a所处的位置，当n的数量+1时算法查找的次数也+1。

O(log n)

O(log n)：也叫对数时间

典型算法有：二分查找法

即当数量每扩大两倍，查询次数仅仅需要+1次，是一种随着数量越多，算法耗时增速越慢的算法。

O(n²)

典型算法有：选择排序、冒泡排序，是一种速度较慢的排序法。

O(n * log n)

典型算法有：快速排序法，是一种速度较快的排序法。

O(n!)

是一种非常慢的算法

即当数量为n时，查询算法耗时为a时，当数量+1时查询算法将耗时a*(n+1),当数量较多时耗时将变得非常大。

注意，大 O 表示法只是一种估算，当数据量大的时候才有用。

大部分情况下你用直觉就可以知道一个算法的大 O 表示法。

比如说，如果你的代码用一个循环遍历你输入的每个元素，那么这个算法就是O(n)。

如果是循环套循环，那就是O(n^2)。如果 3 个循环套在一起就是O(n^3)，以此类推。

排序算法

十大经典排序算法 | 菜鸟教程 (runoob.com)

排序算法可以分为：

内部排序：数据记录在内存中进行排序。
外部排序open in new window：因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等，本文只讲解内部排序算法。用一张图概括：

上图存在错误：

插入排序的最好时间复杂度为 O(n) 而不是 O(n^2) 。
希尔排序的平均时间复杂度为 O(nlogn)

图片名词解释：

n：数据规模
k：“桶” 的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存

术语说明

稳定：如果 A 原本在 B 前面，而 A=B，排序之后 A 仍然在 B 的前面。
不稳定：如果 A 原本在 B 的前面，而 A=B，排序之后 A 可能会出现在 B 的后面。
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
时间复杂度：定性描述一个算法执行所耗费的时间。
空间复杂度：定性描述一个算法执行所需内存的大小。

算法分类

十种常见排序算法可以分类两大类别：比较类排序和非比较类排序。

常见的快速排序、归并排序、堆排序以及冒泡排序等都属于比较类排序算法。比较类排序是通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。在冒泡排序之类的排序中，问题规模为 n，又因为需要比较 n 次，所以平均时间复杂度为 O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为 logn 次，所以时间复杂度平均 O(nlogn)。

比较类排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

而计数排序、基数排序、桶排序则属于非比较类排序算法。非比较排序不通过比较来决定元素间的相对次序，而是通过确定每个元素之前，应该有多少个元素来排序。由于它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度 O(n)。

非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

冒泡排序

冒泡排序是一种简单的排序算法。它重复地遍历要排序的序列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行直到没有再需要交换为止，此时说明该序列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的头部。

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤 1~3，直到排序完成。

public static void bubbleSort() {
    int[] arr = {6,5,3,9,1};
    int temp = 0;
    //第一层循环的边界，是到数组最后一位
    for (int i = 0; i < arr.length - 1; i++) {
        //第二层循环的边界，是到数组最后一位，减去i的长度，因为数组最后边i个数，已经是最大的，不需要比较了
        // 设置标志，如果为true，说明数组本来即使排好序的
        boolean flag = true;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            //若前值大于后值，交换顺序
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 改变标志
                flag = false;
            }
        }
        // 标志没有改变，说明没有走交换的逻辑，即第一位数字小于后边的每一个数字，
        // 所以这个数组本来就是排序好的，不需要继续循环了
        if (flag) {
            break;
        }
    }
    // 输出
    for (int i = 0; i < arr.length; i++){
        System.out.println(arr[i]);
    }
}

算法分析

稳定性：稳定
时间复杂度：最佳：O(n) ，最差：O(n2)，平均：O(n2)
空间复杂度：O(1)
排序方式：In-place

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第 2 步，直到所有元素均排序完毕。

public static void selectionSort() {
    int[] arr = {6,5,3,9,1};
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                // 记录目前能找到的最小值的下标
                minIndex = j;
            }
        }
        if (i != minIndex) {// 将找到的最小值和i位置所在的值进行交换
            int tmp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = tmp;
        }
    }
    for (int i = 0; i < arr.length; i++){
        System.out.println(arr[i]);
    }
}

算法分析

稳定性：不稳定
时间复杂度：最佳：O(n2) ，最差：O(n2)，平均：O(n2)
空间复杂度：O(1)
排序方式：In-place

插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

算法步骤

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤 2~5。

/**
 * 插入排序
 * @param arr
 * @return arr
 */
public static int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preIndex = i - 1;
        int current = arr[i];
        while (preIndex >= 0 && current < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex -= 1;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：O(n) ，最差：O(n2)，平均：O(n2)
空间复杂度：O(1)
排序方式：In-place

希尔排序 (Shell Sort)

希尔排序是希尔 (Donald Shell) 于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破 O(n²) 的第一批算法之一。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。

算法步骤

我们来看下希尔排序的基本步骤，在此我们选择增量 gap=length/2，缩小增量继续以 gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示，{n/2, (n/2)/2, ..., 1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列 {t1, t2, …, tk}，其中 (ti>tj, i<j, tk=1)；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 t，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

/**
 * 希尔排序
 *
 * @param arr
 * @return arr
 */
public static int[] shellSort(int[] arr) {
    int n = arr.length;
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int current = arr[i];
            int preIndex = i - gap;
            // Insertion sort
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = current;

        }
        gap /= 2;
    }
    return arr;
}

算法分析

稳定性：不稳定
时间复杂度：最佳：O(nlogn)，最差：O(n^2) 平均：O(nlogn)
空间复杂度：O(1)

归并排序 (Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

算法步骤

归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：

如果输入内只有一个元素，则直接返回，否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列；
分别对这两个子序列进行归并排序，使子序列变为有序状态；
设定两个指针，分别指向两个已经排序子序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
重复步骤 3 ~4 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

/**
 * 归并排序
 *
 * @param arr
 * @return arr
 */
public static int[] mergeSort(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }
    int middle = arr.length / 2;
    int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
    int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
    return merge(mergeSort(arr_1), mergeSort(arr_2));
}

/**
 * Merge two sorted arrays
 *
 * @param arr_1
 * @param arr_2
 * @return sorted_arr
 */
public static int[] merge(int[] arr_1, int[] arr_2) {
    int[] sorted_arr = new int[arr_1.length + arr_2.length];
    int idx = 0, idx_1 = 0, idx_2 = 0;
    while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
        if (arr_1[idx_1] < arr_2[idx_2]) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 += 1;
        } else {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 += 1;
        }
        idx += 1;
    }
    if (idx_1 < arr_1.length) {
        while (idx_1 < arr_1.length) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 += 1;
            idx += 1;
        }
    } else {
        while (idx_2 < arr_2.length) {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 += 1;
            idx += 1;
        }
    }
    return sorted_arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：O(nlogn)，最差：O(nlogn)，平均：O(nlogn)
空间复杂度：O(n)

快速排序

快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。

快速排序的基本思想：通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

算法步骤

快速排序使用分治法open in new window（Divide and conquer）策略来把一个序列分为较小和较大的 2 个子序列，然后递回地排序两个子序列。具体算法描述如下：

从序列中随机挑出一个元素，做为 “基准”(pivot)；
重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。

public class Test {

    public static void main(String[] args) {

        //算法步骤
        //从数列中挑出一个元素，称为 "基准"（pivot）;
        //重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
        //递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
        
        int[] arr = {8,5,4,2,7};
        quickSort(arr,0, arr.length- 1);

        for (int i : arr) {
            System.out.println(i);
        }
    }

    /**
     *
     * @param arr 数组
     * @param left 数组左边界
     * @param right 数组右边界
     */
    public static void quickSort(int arr[], int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    //交换数据
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

算法分析

稳定性：不稳定
时间复杂度：最佳：O(nlogn)，最差：O(nlogn)，平均：O(nlogn)
空间复杂度：O(logn)

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。

算法步骤

将初始待排序列 (R1, R2, ……, Rn) 构建成大顶堆，此堆为初始的无序区；
将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ……, Rn-1) 和新的有序区 (Rn), 且满足 R[1, 2, ……, n-1]<=R[n]；
由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2, ……, Rn-1) 调整为新堆，然后再次将 R [1] 与无序区最后一个元素交换，得到新的无序区 (R1, R2, ……, Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。

// Global variable that records the length of an array;
static int heapLen;

/**
 * Swap the two elements of an array
 * @param arr
 * @param i
 * @param j
 */
private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

/**
 * Build Max Heap
 * @param arr
 */
private static void buildMaxHeap(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapify(arr, i);
    }
}

/**
 * Adjust it to the maximum heap
 * @param arr
 * @param i
 */
private static void heapify(int[] arr, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (right < heapLen && arr[right] > arr[largest]) {
        largest = right;
    }
    if (left < heapLen && arr[left] > arr[largest]) {
        largest = left;
    }
    if (largest != i) {
        swap(arr, largest, i);
        heapify(arr, largest);
    }
}

/**
 * Heap Sort
 * @param arr
 * @return
 */
public static int[] heapSort(int[] arr) {
    // index at the end of the heap
    heapLen = arr.length;
    // build MaxHeap
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        // Move the top of the heap to the tail of the heap in turn
        swap(arr, 0, i);
        heapLen -= 1;
        heapify(arr, 0);
    }
    return arr;
}

算法分析

稳定性：不稳定
时间复杂度：最佳：O(nlogn)，最差：O(nlogn)，平均：O(nlogn)
空间复杂度：O(1)

计数排序 (Counting Sort)

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序 (Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。

算法步骤

找出数组中的最大值 max、最小值 min；
创建一个新数组 C，其长度是 max-min+1，其元素默认值都为 0；
遍历原数组 A 中的元素 A[i]，以 A[i]-min 作为 C 数组的索引，以 A[i] 的值在 A 中元素出现次数作为 C[A[i]-min] 的值；
对 C 数组变形，新元素的值是该元素与前一个元素值的和，即当 i>1 时 C[i] = C[i] + C[i-1]；
创建结果数组 R，长度和原始数组一样。
从后向前遍历原始数组 A 中的元素 A[i]，使用 A[i] 减去最小值 min 作为索引，在计数数组 C 中找到对应的值 C[A[i]-min]，C[A[i]-min]-1 就是 A[i] 在结果数组 R 中的位置，做完上述这些操作，将 count[A[i]-min] 减小 1。

/**
 * Gets the maximum and minimum values in the array
 *
 * @param arr
 * @return
 */
private static int[] getMinAndMax(int[] arr) {
    int maxValue = arr[0];
    int minValue = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i];
        } else if (arr[i] < minValue) {
            minValue = arr[i];
        }
    }
    return new int[] { minValue, maxValue };
}

/**
 * Counting Sort
 *
 * @param arr
 * @return
 */
public static int[] countingSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    int[] extremum = getMinAndMax(arr);
    int minValue = extremum[0];
    int maxValue = extremum[1];
    int[] countArr = new int[maxValue - minValue + 1];
    int[] result = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - minValue] += 1;
    }
    for (int i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        int idx = countArr[arr[i] - minValue] - 1;
        result[idx] = arr[i];
        countArr[arr[i] - minValue] -= 1;
    }
    return result;
}

算法分析

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n+k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量额外内存空间。

稳定性：稳定
时间复杂度：最佳：O(n+k) 最差：O(n+k) 平均：O(n+k)
空间复杂度：O(k)

桶排序 (Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行。

算法步骤

设置一个 BucketSize，作为每个桶所能放置多少个不同数值；
遍历输入数据，并且把数据依次映射到对应的桶里去；
对每个非空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
从非空桶里把排好序的数据拼接起来。

/**
 * Gets the maximum and minimum values in the array
 * @param arr
 * @return
 */
private static int[] getMinAndMax(List<Integer> arr) {
    int maxValue = arr.get(0);
    int minValue = arr.get(0);
    for (int i : arr) {
        if (i > maxValue) {
            maxValue = i;
        } else if (i < minValue) {
            minValue = i;
        }
    }
    return new int[] { minValue, maxValue };
}

/**
 * Bucket Sort
 * @param arr
 * @return
 */
public static List<Integer> bucketSort(List<Integer> arr, int bucket_size) {
    if (arr.size() < 2 || bucket_size == 0) {
        return arr;
    }
    int[] extremum = getMinAndMax(arr);
    int minValue = extremum[0];
    int maxValue = extremum[1];
    int bucket_cnt = (maxValue - minValue) / bucket_size + 1;
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < bucket_cnt; i++) {
        buckets.add(new ArrayList<Integer>());
    }
    for (int element : arr) {
        int idx = (element - minValue) / bucket_size;
        buckets.get(idx).add(element);
    }
    for (int i = 0; i < buckets.size(); i++) {
        if (buckets.get(i).size() > 1) {
            buckets.set(i, sort(buckets.get(i), bucket_size / 2));
        }
    }
    ArrayList<Integer> result = new ArrayList<>();
    for (List<Integer> bucket : buckets) {
        for (int element : bucket) {
            result.add(element);
        }
    }
    return result;
}

算法分析

稳定性：稳定
时间复杂度：最佳：O(n+k) 最差：O(n²) 平均：O(n+k)
空间复杂度：O(n+k)

基数排序 (Radix Sort)

基数排序也是非比较的排序算法，对元素中的每一位数字进行排序，从最低位开始排序，复杂度为 O(n×k)，n 为数组长度，k 为数组中元素的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法步骤

取得数组中的最大数，并取得位数，即为迭代次数 N（例如：数组中最大数值为 1000，则 N=4）；
A 为原始数组，从最低位开始取每个位组成 radix 数组；
对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；
将 radix 依次赋值给原数组；
重复 2~4 步骤 N 次

/**
 * Radix Sort
 *
 * @param arr
 * @return
 */
public static int[] radixSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    int N = 1;
    int maxValue = arr[0];
    for (int element : arr) {
        if (element > maxValue) {
            maxValue = element;
        }
    }
    while (maxValue / 10 != 0) {
        maxValue = maxValue / 10;
        N += 1;
    }
    for (int i = 0; i < N; i++) {
        List<List<Integer>> radix = new ArrayList<>();
        for (int k = 0; k < 10; k++) {
            radix.add(new ArrayList<Integer>());
        }
        for (int element : arr) {
            int idx = (element / (int) Math.pow(10, i)) % 10;
            radix.get(idx).add(element);
        }
        int idx = 0;
        for (List<Integer> l : radix) {
            for (int n : l) {
                arr[idx++] = n;
            }
        }
    }
    return arr;
}

算法分析

稳定性：稳定
时间复杂度：最佳：O(n×k) 最差：O(n×k) 平均：O(n×k)
空间复杂度：O(n+k)

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值

字符串算法题

KMP算法

谈到字符串问题，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有 O(m)。因为“暴力搜索”的方法会反复回溯主串，导致效率低下，而 KMP 算法可以利用已经部分匹配这个有效信息，保持主串上的指针不回溯，通过修改子串的指针，让模式串尽量地移动到有效的位置。

具体算法细节请参考：

除此之外，再来了解一下 BM 算法！

BM 算法也是一种精确字符串匹配算法，它采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。《字符串匹配的 KMP 算法》:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

替换空格

剑指 offer：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为 We Are Happy.则经过替换之后的字符串为 We%20Are%20Happy。

/**
   * 第一种方法：常规方法。利用String.charAt(i)以及String.valueOf(char).equals(" "
   * )遍历字符串并判断元素是否为空格。是则替换为"%20",否则不替换
   */
public static String replaceSpace(StringBuffer str) {
    int length = str.length();
    // System.out.println("length=" + length);
    StringBuffer result = new StringBuffer();
    for (int i = 0; i < length; i++) {
        char b = str.charAt(i);
        if (String.valueOf(b).equals(" ")) {
            result.append("%20");
        } else {
            result.append(b);
        }
    }
    return result.toString();
}

/**
   * 第二种方法：利用API替换掉所用空格，一行代码解决问题
   */
public static String replaceSpace2(StringBuffer str) {
    return str.toString().replaceAll("\\s", "%20");
}

// 对于替换固定字符（比如空格）的情况，第二种方法其实可以使用 replace 方法替换，性能更好!
str.toString().replace(" ","%20");

最长公共前缀

Leetcode：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “"。

示例：
输入: ["flower","flow","flight"]
输出: "fl"

示例：
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

思路：先利用 Arrays.sort(strs)为数组排序，再将数组第一个元素和最后一个元素的字符从前往后对比即可！

public class Main {
    public static String replaceSpace(String[] strs) {

        // 如果检查值不合法及就返回空串
        if (!checkStrs(strs)) {
            return "";
        }
        // 数组长度
        int len = strs.length;
        // 用于保存结果
        StringBuilder res = new StringBuilder();
        // 给字符串数组的元素按照升序排序(包含数字的话，数字会排在前面)
        Arrays.sort(strs);
        int m = strs[0].length();
        int n = strs[len - 1].length();
        int num = Math.min(m, n);
        for (int i = 0; i < num; i++) {
            if (strs[0].charAt(i) == strs[len - 1].charAt(i)) {
                res.append(strs[0].charAt(i));
            } else
                break;

        }
        return res.toString();

    }

    private static boolean checkStrs(String[] strs) {
        boolean flag = false;
        if (strs != null) {
            // 遍历strs检查元素值
            for (int i = 0; i < strs.length; i++) {
                if (strs[i] != null && strs[i].length() != 0) {
                    flag = true;
                } else {
                    flag = false;
                    break;
                }
            }
        }
        return flag;
    }

    // 测试
    public static void main(String[] args) {
        String[] strs = { "customer", "car", "cat" };
        // String[] strs = { "customer", "car", null };//空串
        // String[] strs = {};//空串
        // String[] strs = null;//空串
        System.out.println(Main.replaceSpace(strs));// c
    }
}

回文串

回文串：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。百度百科

最长回文串

LeetCode：给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如"Aa"不能当做一个回文字符串。注意：假设字符串的长度不会超过 1010。

例如输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

我们上面已经知道了什么是回文串？现在我们考虑一下可以构成回文串的两种情况：

字符出现次数为双数的组合
字符出现次数为偶数的组合+单个字符中出现次数最多且为奇数次的字符

统计字符出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如“abcba”，所以如果最后有字母落单，总长度可以加 1。首先将字符串转变为字符数组。然后遍历该数组，判断对应字符是否在 hashset 中，如果不在就加进去，如果在就让 count++，然后移除该字符！这样就能找到出现次数为双数的字符个数。

//https://leetcode-cn.com/problems/longest-palindrome/description/
class Solution {
    public int longestPalindrome(String s) {
        if (s.length() == 0)
            return 0;
        // 用于存放字符
        HashSet<Character> hashset = new HashSet<Character>();
        char[] chars = s.toCharArray();
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (!hashset.contains(chars[i])) {// 如果hashset没有该字符就保存进去
                hashset.add(chars[i]);
            } else {// 如果有,就让count++（说明找到了一个成对的字符），然后把该字符移除
                hashset.remove(chars[i]);
                count++;
            }
        }
        return hashset.isEmpty() ? count * 2 : count * 2 + 1;
    }
}

验证回文串

LeetCode：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。

示例 1：

1
2

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2：

1
2

输入: "race a car"
输出: false

//https://leetcode-cn.com/problems/valid-palindrome/description/
class Solution {
    public  boolean isPalindrome(String s) {
        if (s.length() == 0)
            return true;
        int l = 0, r = s.length() - 1;
        while (l < r) {
            // 从头和尾开始向中间遍历
            if (!Character.isLetterOrDigit(s.charAt(l))) {// 字符不是字母和数字的情况
                l++;
            } else if (!Character.isLetterOrDigit(s.charAt(r))) {// 字符不是字母和数字的情况
                r--;
            } else {
                // 判断二者是否相等
                if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
                    return false;
                l++;
                r--;
            }
        }
        return true;
    }
}

最长回文子串

LeetCode：最长回文子串，给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：

1
2

输入: "cbbd"
输出: "bb"

以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。

//https://leetcode-cn.com/problems/longest-palindromic-substring/description/
class Solution {
    private int index, len;

    public String longestPalindrome(String s) {
        if (s.length() < 2)
            return s;
        for (int i = 0; i < s.length() - 1; i++) {
            PalindromeHelper(s, i, i);
            PalindromeHelper(s, i, i + 1);
        }
        return s.substring(index, index + len);
    }

    public void PalindromeHelper(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        if (len < r - l - 1) {
            index = l + 1;
            len = r - l - 1;
        }
    }
}

最长回文子序列

LeetCode: 最长回文子序列给定一个字符串 s，找到其中最长的回文子序列。可以假设 s 的最大长度为 1000。最长回文子序列和上一题最长回文子串的区别是，子串是字符串中连续的一个序列，而子序列是字符串中保持相对位置的字符序列，例如，“bbbb"可以是字符串"bbbab"的子序列但不是子串。

给定一个字符串 s，找到其中最长的回文子序列。可以假设 s 的最大长度为 1000。

示例 1：

输入:
"bbbab"
输出:
4

一个可能的最长回文子序列为 “bbbb”。

示例 2：

输入:
"cbbd"
输出:
2

一个可能的最长回文子序列为 “bb”。

动态规划： dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j) otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int [][] dp = new int[len][len];
        for(int i = len - 1; i>=0; i--){
            dp[i][i] = 1;
            for(int j = i+1; j < len; j++){
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][len-1];
    }
}

括号匹配深度

爱奇艺 2018 秋招 Java：一个合法的括号匹配序列有以下定义:

空串"“是一个合法的括号匹配序列

如果"X"和"Y"都是合法的括号匹配序列,“XY"也是一个合法的括号匹配序列

如果"X"是一个合法的括号匹配序列,那么”(X)“也是一个合法的括号匹配序列

每个合法的括号序列都可以由以上规则生成。

例如: “”,”()”,”()()”,"((()))“都是合法的括号序列对于一个合法的括号序列我们又有以下定义它的深度:

空串"“的深度是 0

如果字符串"X"的深度是 x,字符串"Y"的深度是 y,那么字符串"XY"的深度为 max(x,y)

如果"X"的深度是 x,那么字符串”(X)“的深度是 x+1

例如: “()()()“的深度是 1,”((()))“的深度是 3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

输入描述:
输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含'('和')'。

输出描述:
输出一个正整数,即这个序列的深度。

示例：

输入:
(())
输出:
2

代码如下：

import java.util.Scanner;

/**
 * https://www.nowcoder.com/test/8246651/summary
 *
 * @author Snailclimb
 * @date 2018年9月6日
 * @Description: TODO 求给定合法括号序列的深度
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int cnt = 0, max = 0, i;
        for (i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(')
                cnt++;
            else
                cnt--;
            max = Math.max(max, cnt);
        }
        sc.close();
        System.out.println(max);
    }
}

把字符串转换成整数

剑指 offer: 将一个字符串转换成一个整数(实现 Integer.valueOf(string)的功能，但是 string 不符合数字要求时返回 0)，要求不能使用字符串转换整数的库函数。数值为 0 或者字符串不是一个合法的数值则返回 0。

//https://www.weiweiblog.cn/strtoint/
public class Main {

    public static int StrToInt(String str) {
        if (str.length() == 0)
            return 0;
        char[] chars = str.toCharArray();
        // 判断是否存在符号位
        int flag = 0;
        if (chars[0] == '+')
            flag = 1;
        else if (chars[0] == '-')
            flag = 2;
        int start = flag > 0 ? 1 : 0;
        int res = 0;// 保存结果
        for (int i = start; i < chars.length; i++) {
            if (Character.isDigit(chars[i])) {// 调用Character.isDigit(char)方法判断是否是数字，是返回True，否则False
                int temp = chars[i] - '0';
                res = res * 10 + temp;
            } else {
                return 0;
            }
        }
        return flag != 2 ? res : -res;

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String s = "-12312312";
        System.out.println("使用库函数转换：" + Integer.valueOf(s));
        int res = Main.StrToInt(s);
        System.out.println("使用自己写的方法转换：" + res);
    }

}

trim()方法：去除字符串两端的空格

public static String myTrim(String str) {
    //开始值
    int start = 0;
    //结束值
    int end = str.length()-1;
    while(start <= end && str.charAt(start) == ' ') {
        start++;
    }
    while(end >= start && str.charAt(end) == ' '){
        end--;
    }
    return str.substring(start, end+1);
}

字符串逆序

public static void reverse(String string) {
    char[] a = string.toCharArray();
    for (int start=0,end=a.length-1; start<end; start++,end--) {
        char temp = a[start];
        a[start]=a[end];
        a[end]= temp;
    }
    System.out.println(a.toString());
}

子串在整串中出现的次数

public static void shownum(String string ,String key) {
    //记录位置
    int index = 0;
    //记录出现次数
    int count = 0;

    while ( string.indexOf(key)!=-1) {
        index =string.indexOf(key);
        //进行字符串切割
        string= string.substring(index+key.length());
        count++;
    }
    System.out.println(count);
}

输出数组a中存在，数组b中不存在的值

String[] a = {"a","c","ab"};
String[] b = {"a","cd","a","b","c"};
for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < b.length; j++) {
        if (a[i] == b[j]) {
            break;
        }
        if(j == b.length - 1 ){
            System.out.println(a[i]);
        }
    }
}

链表算法题

翻转链表

剑指 offer：输入一个链表，反转链表后，输出链表的所有元素。

思路：让后一个节点指向前一个节点。

// 定义链表
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

翻转方法：

public ListNode ReverseList(ListNode head) {
    ListNode next = null;
    ListNode pre = null;

    while (head != null) {
        // 保存要反转到头的那个节点
        next = head.next;
        // 要反转的那个节点指向已经反转的上一个节点(备注:第一次反转的时候会指向null)
        head.next = pre;
        // 上一个已经反转到头部的节点
        pre = head;
        // 一直向链表尾走
        head = next;
    }
    return pre;
}

测试方法：

public static void main(String[] args) {

    ListNode a = new ListNode(1);
    ListNode b = new ListNode(2);
    ListNode c = new ListNode(3);
    ListNode d = new ListNode(4);
    ListNode e = new ListNode(5);
    a.next = b;
    b.next = c;
    c.next = d;
    d.next = e;
    new Solution().ReverseList(a);
    while (e != null) {
        System.out.println(e.val);
        e = e.next;
    }
}

输出：

链表中倒数第 k 个节点

剑指 offer：输入一个链表，输出该链表中倒数第 k 个结点。

链表中倒数第 k 个节点也就是正数第(L-K+1)个节点

首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第 k 个节点也就是正数第(L-K+1)个节点。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

// 时间复杂度O(n),一次遍历即可
// https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        // 如果链表为空或者k小于等于0
        if (head == null || k <= 0) {
            return null;
        }
        // 声明两个指向头结点的节点
        ListNode node1 = head, node2 = head;
        // 记录节点的个数
        int count = 0;
        // 记录k值，后面要使用
        int index = k;
        // p指针先跑，并且记录节点数，当node1节点跑了k-1个节点后，node2节点开始跑，
        // 当node1节点跑到最后时，node2节点所指的节点就是倒数第k个节点
        while (node1 != null) {
            node1 = node1.next;
            count++;
            if (k < 1) {
                node2 = node2.next;
            }
            k--;
        }
        // 如果节点个数小于所求的倒数第k个节点，则返回空
        if (count < index)
            return null;
        return node2;

    }
}

删除链表的倒数第 N 个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

1
2
3

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

**说明：**给定的 n 保证是有效的。

我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第 (L - n + 1)个结点，其中 L 是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。

两次遍历法

首先我们将添加一个 哑结点 作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 L。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n) 个结点那里。我们把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点，完成这个算法。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
// https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 哑结点，哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部
        ListNode dummy = new ListNode(0);
        // 哑结点指向头结点
        dummy.next = head;
        // 保存链表长度
        int length = 0;
        ListNode len = head;
        while (len != null) {
            length++;
            len = len.next;
        }
        length = length - n;
        ListNode target = dummy;
        // 找到 L-n 位置的节点
        while (length > 0) {
            target = target.next;
            length--;
        }
        // 把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点
        target.next = target.next.next;
        return dummy.next;
    }
}

进阶——一次遍历法：

链表中倒数第 N 个节点也就是正数第(L - n + 1)个节点。

其实这种方法就和我们上面第四题找“链表中倒数第 k 个节点”所用的思想是一样的。基本思路就是： 定义两个节点 node1、node2;node1 节点先跑，node1 节点跑到第 n+1 个节点的时候,node2 节点开始跑.当 node1 节点跑到最后一个节点时，node2 节点所在的位置就是第（L - n ）个节点（L 代表总链表长度，也就是倒数第 n + 1 个节点）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 声明两个指向头结点的节点
        ListNode node1 = dummy, node2 = dummy;

        // node1 节点先跑，node1节点 跑到第 n 个节点的时候,node2 节点开始跑
        // 当node1 节点跑到最后一个节点时，node2 节点所在的位置就是第 （L-n ） 个节点，也就是倒数第 n+1（L代表总链表长度）
        while (node1 != null) {
            node1 = node1.next;
            if (n < 1 && node1 != null) {
                node2 = node2.next;
            }
            n--;
        }
        node2.next = node2.next.next;
        return dummy.next;
    }
}

合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

我们可以这样分析：

假设我们有两个链表 A,B；
A 的头节点 A1 的值与 B 的头结点 B1 的值比较，假设 A1 小，则 A1 为头节点；
A2 再和 B1 比较，假设 B1 小,则，A1 指向 B1；
A2 再和 B2 比较就这样循环往复就行了，应该还算好理解。

考虑通过递归的方式实现。

递归版本：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
//https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}

两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

1
2
3

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

Leetcode 官方详细解答地址：

https://leetcode-cn.com/problems/add-two-numbers/solution/

要对头结点进行操作时，考虑创建哑节点 dummy，使用 dummy->next 表示真正的头节点。这样可以避免处理头节点为空的边界问题。

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。

我们首先从最低有效位也就是列表 l1 和 l2 的表头开始相加。注意需要考虑到进位的情况！

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//https://leetcode-cn.com/problems/add-two-numbers/description/
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        //carry 表示进位数
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            //进位数
            carry = sum / 10;
            //新节点的数值为sum % 10
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项。 n<=39。

示例代码：

采用迭代法：

int Fibonacci(int number) {
    if (number <= 0) {
        return 0;
    }
    if (number == 1 || number == 2) {
        return 1;
    }
    int first = 1, second = 1, third = 0;
    for (int i = 3; i <= number; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return third;
}

采用递归：

public int Fibonacci(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1||n==2) {
        return 1;
    }
    return Fibonacci(n - 2) + Fibonacci(n - 1);
}

跳台阶问题

题目描述：

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

问题分析：

正常分析法：

a.如果两种跳法，1 阶或者 2 阶，那么假定第一次跳的是一阶，那么剩下的是 n-1 个台阶，跳法是 f(n-1); b.假定第一次跳的是 2 阶，那么剩下的是 n-2 个台阶，跳法是 f(n-2) c.由 a，b 假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

找规律分析法：

f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5，可以总结出 f(n) = f(n-1) + f(n-2)的规律。但是为什么会出现这样的规律呢？假设现在 6 个台阶，我们可以从第 5 跳一步到 6，这样的话有多少种方案跳到 5 就有多少种方案跳到 6，另外我们也可以从 4 跳两步跳到 6，跳到 4 有多少种方案的话，就有多少种方案跳到 6，其他的不能从 3 跳到 6 什么的啦，所以最后就是 f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。

所以这道题其实就是斐波那契数列的问题。

代码只需要在上一题的代码稍做修改即可。和上一题唯一不同的就是这一题的初始元素变为 1 2 3 5 8…..而上一题为 1 1 2 3 5 …….。另外这一题也可以用递归做，但是递归效率太低，所以我这里只给出了迭代方式的代码。

示例代码：

int jumpFloor(int number) {
    if (number <= 0) {
        return 0;
    }
    if (number == 1) {
        return 1;
    }
    if (number == 2) {
        return 2;
    }
    int first = 1, second = 2, third = 0;
    for (int i = 3; i <= number; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return third;
}

变态跳台阶问题

题目描述：

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

问题分析：

假设 n>=2，第一步有 n 种跳法：跳 1 级、跳 2 级、到跳 n 级跳 1 级，剩下 n-1 级，则剩下跳法是 f(n-1) 跳 2 级，剩下 n-2 级，则剩下跳法是 f(n-2) …… 跳 n-1 级，剩下 1 级，则剩下跳法是 f(1) 跳 n 级，剩下 0 级，则剩下跳法是 f(0) 所以在 n>=2 的情况下： f(n)=f(n-1)+f(n-2)+…+f(1) 因为 f(n-1)=f(n-2)+f(n-3)+…+f(1) 所以 f(n)=2*f(n-1) 又 f(1)=1,所以可得f(n)=2^(number-1)

示例代码：

1
2
3

int JumpFloorII(int number) {
    return 1 << --number;//2^(number-1)用位移操作进行，更快
}

补充：

java 中有三种移位运算符：

“«” : 左移运算符，等同于乘 2 的 n 次方
“»”: 右移运算符，等同于除 2 的 n 次方
“»>” : 无符号右移运算符，不管移动前最高位是 0 还是 1，右移后左侧产生的空位部分都以 0 来填充。与»类似。

1
2
3

int a = 16;
int b = a << 2;//左移2，等同于16 * 2的2次方，也就是16 * 4
int c = a >> 2;//右移2，等同于16 / 2的2次方，也就是16 / 4

二维数组查找

题目描述：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

问题解析：

这一道题还是比较简单的，我们需要考虑的是如何做，效率最快。这里有一种很好理解的思路：

矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，因此从左下角开始查找，当要查找数字比左下角数字大时。右移要查找数字比左下角数字小时，上移。这样找的速度最快。

示例代码：

public boolean Find(int target, int [][] array) {
    //基本思路从左下角开始找，这样速度最快
    int row = array.length-1;//行
    int column = 0;//列
    //当行数大于0，当前列数小于总列数时循环条件成立
    while((row >= 0)&& (column< array[0].length)){
        if(array[row][column] > target){
            row--;
        }else if(array[row][column] < target){
            column++;
        }else{
            return true;
        }
    }
    return false;
}

用两个栈实现队列

题目描述：

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。队列中的元素为 int 类型。

问题分析：

先来回顾一下栈和队列的基本特点： **栈：**后进先出（LIFO） 队列： 先进先出很明显我们需要根据 JDK 给我们提供的栈的一些基本方法来实现。先来看一下 Stack 类的一些基本方法：

peek()：查看此栈顶部的对象，而不从栈中删除它。

pop()：删除此栈顶部的对象，并将该对象作为此函数的返回值。

push()：将新项推送到此栈的顶部。

search()：返回一个对象在此栈上的基于1的位置。

既然题目给了我们两个栈，我们可以这样考虑当 push 的时候将元素 push 进 stack1，pop 的时候我们先把 stack1 的元素 pop 到 stack2，然后再对 stack2 执行 pop 操作，这样就可以保证是先进先出的。（负[pop]负[pop]得正[先进先出]）

**考察内容：**队列+栈

示例代码：

//左程云的《程序员代码面试指南》的答案
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    //当执行push操作时，将元素添加到stack1
    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        //如果两个队列都为空则抛出异常,说明用户没有push进任何元素
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        //如果stack2不为空直接对stack2执行pop操作，
        if(stack2.empty()){
            while(!stack1.empty()){
                //将stack1的元素按后进先出push进stack2里面
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

栈的压入,弹出序列

题目描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4，5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

题目分析：

这道题想了半天没有思路，参考了 Alias 的答案，他的思路写的也很详细应该很容易看懂。作者：Alias https://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106 来源：牛客网

【思路】借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是 1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是 4，很显然 1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

举例：

入栈 1,2,3,4,5

出栈 4,5,3,2,1

首先 1 入辅助栈，此时栈顶 1≠4，继续入栈 2

此时栈顶 2≠4，继续入栈 3

此时栈顶 3≠4，继续入栈 4

此时栈顶 4 ＝ 4，出栈 4，弹出序列向后一位，此时为 5，,辅助栈里面是 1,2,3

此时栈顶 3≠5，继续入栈 5

此时栈顶 5=5，出栈 5,弹出序列向后一位，此时为 3，,辅助栈里面是 1,2,3

…. 依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。

**考察内容：**栈

示例代码：

import java.util.ArrayList;
import java.util.Stack;
//这道题没想出来，参考了Alias同学的答案：https://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0 || popA.length == 0)
            return false;
        Stack<Integer> s = new Stack<Integer>();
        //用于标识弹出序列的位置
        int popIndex = 0;
        for(int i = 0; i< pushA.length;i++){
            s.push(pushA[i]);
            //如果栈不为空，且栈顶元素等于弹出序列
            while(!s.empty() &&s.peek() == popA[popIndex]){
                //出栈
                s.pop();
                //弹出序列向后一位
                popIndex++;
            }
        }
        return s.empty();
    }
}

其他

数值的整数次方

题目描述：

给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。

问题解析：

这道题算是比较麻烦和难一点的一个了。我这里采用的是二分幂思想，当然也可以采用快速幂。更具剑指 offer 书中细节，该题的解题思路如下：1.当底数为 0 且指数<0 时，会出现对 0 求倒数的情况，需进行错误处理，设置一个全局变量； 2.判断底数是否等于 0，由于 base 为 double 型，所以不能直接用==判断 3.优化求幂函数（二分幂）。当 n 为偶数，a^n =（a^n/2）_（a^n/2）；当 n 为奇数，a^n = a^[(n-1)/2] _ a^[(n-1)/2] * a。时间复杂度 O(logn)

时间复杂度：O(logn)

示例代码：

public class Solution {
    boolean invalidInput=false;
    public double Power(double base, int exponent) {
        //如果底数等于0并且指数小于0
        //由于base为double型，不能直接用==判断
        if(equal(base,0.0)&&exponent<0){
            invalidInput=true;
            return 0.0;
        }
        int absexponent=exponent;
        //如果指数小于0，将指数转正
        if(exponent<0)
            absexponent=-exponent;
        //getPower方法求出base的exponent次方。
        double res=getPower(base,absexponent);
        //如果指数小于0，所得结果为上面求的结果的倒数
        if(exponent<0)
            res=1.0/res;
        return res;
    }
    //比较两个double型变量是否相等的方法
    boolean equal(double num1,double num2){
        if(num1-num2>-0.000001&&num1-num2<0.000001)
            return true;
        else
            return false;
    }
    //求出b的e次方的方法
    double getPower(double b,int e){
        //如果指数为0，返回1
        if(e==0)
            return 1.0;
        //如果指数为1，返回b
        if(e==1)
            return b;
        //e>>1相等于e/2，这里就是求a^n =（a^n/2）*（a^n/2）
        double result=getPower(b,e>>1);
        result*=result;
        //如果指数n为奇数，则要再乘一次底数base
        if((e&1)==1)
            result*=b;
        return result;
    }
}

当然这一题也可以采用笨方法：累乘。不过这种方法的时间复杂度为 O（n），这样没有前一种方法效率高。

// 使用累乘
public double powerAnother(double base, int exponent) {
    double result = 1.0;
    for (int i = 0; i < Math.abs(exponent); i++) {
        result *= base;
    }
    if (exponent >= 0)
        return result;
    else
        return 1 / result;
}

调整数组顺序使奇数位于偶数前面

题目描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

问题解析：

这道题有挺多种解法的，给大家介绍一种我觉得挺好理解的方法：我们首先统计奇数的个数假设为 n,然后新建一个等长数组，然后通过循环判断原数组中的元素为偶数还是奇数。如果是则从数组下标 0 的元素开始，把该奇数添加到新数组；如果是偶数则从数组下标为 n 的元素开始把该偶数添加到新数组中。

示例代码：

时间复杂度为 O（n），空间复杂度为 O（n）的算法

public class Solution {
    public void reOrderArray(int [] array) {
        //如果数组长度等于0或者等于1，什么都不做直接返回
        if(array.length==0||array.length==1)
            return;
        //oddCount：保存奇数个数
        //oddBegin：奇数从数组头部开始添加
        int oddCount=0,oddBegin=0;
        //新建一个数组
        int[] newArray=new int[array.length];
        //计算出（数组中的奇数个数）开始添加元素
        for(int i=0;i<array.length;i++){
            if((array[i]&1)==1) oddCount++;
        }
        for(int i=0;i<array.length;i++){
            //如果数为基数新数组从头开始添加元素
            //如果为偶数就从oddCount（数组中的奇数个数）开始添加元素
            if((array[i]&1)==1)
                newArray[oddBegin++]=array[i];
            else newArray[oddCount++]=array[i];
        }
        for(int i=0;i<array.length;i++){
            array[i]=newArray[i];
        }
    }
}

获取上传的文件名

public static void getFileName() {
    String string = "D:\\20120512\\day12\\Demo1.java";
//最快捷办法  从后寻找\\
//int index = string.lastIndexOf("\\");
//string = string.substring(index+1);
//System.out.println(string);
//第二种方法 切割字符串
    String [] array  = string.split("\\\\");
    if (array!=null&&array.length>0) {
        String x = array[array.length-1];
        System.out.println(x);
    }

}

List去重

//创建一个数组
ArrayList<String>arrayList = new ArrayList<>();
//追加数据
arrayList.add("1");
arrayList.add("2");
arrayList.add("2");
arrayList.add("3");
//创建临时数组
ArrayList<String>temp = new ArrayList<>();
//循环旧数组
for (String string : arrayList) {
    //用旧数组的每个元素比对新数组是否存在
    if (!temp.contains(string)) {
        temp.add(string);
    }

}
//如果只是去重，把旧指针重新指向即可
arrayList = temp;
System.out.println(arrayList);

实现copy一个文件，把之前的a.txt，copy一份到b.txt

//方法1:不用缓冲流
//获得a的输入流
FileInputStream inputStream = new FileInputStream("C:\\Users\\wangmeng\\Desktop\\a.txt");
//获得b的输出流
FileOutputStream outputStream = new FileOutputStream("C:\\Users\\wangmeng\\Desktop\\b.txt");
int num = 0;
//循环读取
while ((num=inputStream.read())!=-1) {
    //写入
    outputStream.write(num);
}
//关闭
inputStream.close();
outputStream.close();
//方法2:使用缓冲流
//获得a的输入流
FileInputStream inputStream = new FileInputStream("C:\\Users\\wangmeng\\Desktop\\a.txt");
//获得b的输出流
FileOutputStream outputStream = new FileOutputStream("C:\\Users\\wangmeng\\Desktop\\b.txt");
//创建缓冲
byte[] bs = new byte[5];
int num=0;
while ((num=inputStream.read())!=-1) {
    //写入b
    outputStream.write(num);
}
inputStream.close();
outputStream.close();

求1到100之间所有质数的和

注：
1.质数是只能被1和它本身整除的数
2.1不是质数

当前有一泛型为integer的LinkedList，依次向list中添加数字，

要求任何时候这个list都是有序的。
如：依次插入3、2、1、2，希望list的顺序是1、2、2、3

一个10G的文件，里面全是IP，找出重复次数大于100次的IP。

因为不限制工具，可以先将数据导入mysql，用mysql处理。

select 
    ip,
    count(1)
from table_name
group by ip
having count(1) > 100

大O表示法#

O(1)#

O(n)#

O(log n)#

O(n²)#

O(n * log n)#

O(n!)#

排序算法#

术语说明#

算法分类#

冒泡排序#

算法步骤#

算法分析#

选择排序#

算法步骤#

算法分析#

插入排序#

算法步骤#

算法分析#

希尔排序 (Shell Sort)#

算法步骤#

算法分析#

归并排序 (Merge Sort)#

算法步骤#

算法分析#

快速排序#

算法步骤#

算法分析#

堆排序#

算法步骤#

算法分析#

计数排序 (Counting Sort)#

算法步骤#

算法分析#

桶排序 (Bucket Sort)#

算法步骤#

算法分析#

基数排序 (Radix Sort)#

算法步骤#

算法分析#

字符串算法题#

KMP算法#

替换空格#

最长公共前缀#

回文串#

最长回文串#

验证回文串#

最长回文子串#

最长回文子序列#

括号匹配深度#

把字符串转换成整数#

trim()方法：去除字符串两端的空格#

字符串逆序#

子串在整串中出现的次数#

输出数组a中存在，数组b中不存在的值#

链表算法题#

翻转链表#

链表中倒数第 k 个节点#

删除链表的倒数第 N 个节点#

合并两个排序的链表#

两数相加#

斐波那契数列#

跳台阶问题#

变态跳台阶问题#

二维数组查找#

用两个栈实现队列#

栈的压入,弹出序列#

其他#

数值的整数次方#

调整数组顺序使奇数位于偶数前面#

获取上传的文件名#

List去重#

实现copy一个文件，把之前的a.txt，copy一份到b.txt#

求1到100之间所有质数的和#

当前有一泛型为integer的LinkedList，依次向list中添加数字，#

一个10G的文件，里面全是IP，找出重复次数大于100次的IP。#

因为不限制工具，可以先将数据导入mysql，用mysql处理。#

可以使用redis实现#

大O表示法

O(1)

O(n)

O(log n)

O(n²)

O(n * log n)

O(n!)

排序算法

术语说明

算法分类

冒泡排序

算法步骤

算法分析

选择排序

算法步骤

算法分析

插入排序

算法步骤

算法分析

希尔排序 (Shell Sort)

算法步骤

算法分析

归并排序 (Merge Sort)

算法步骤

算法分析

快速排序

算法步骤

算法分析

堆排序

算法步骤

算法分析

计数排序 (Counting Sort)

算法步骤

算法分析

桶排序 (Bucket Sort)

算法步骤

算法分析

基数排序 (Radix Sort)

算法步骤

算法分析

字符串算法题

KMP算法

替换空格

最长公共前缀

回文串

最长回文串

验证回文串

最长回文子串

最长回文子序列

括号匹配深度

把字符串转换成整数

trim()方法：去除字符串两端的空格

字符串逆序

子串在整串中出现的次数

输出数组a中存在，数组b中不存在的值

链表算法题

翻转链表

链表中倒数第 k 个节点

删除链表的倒数第 N 个节点

合并两个排序的链表

两数相加

斐波那契数列

跳台阶问题

变态跳台阶问题

二维数组查找

用两个栈实现队列

栈的压入,弹出序列

其他

数值的整数次方

调整数组顺序使奇数位于偶数前面

获取上传的文件名

List去重

实现copy一个文件，把之前的a.txt，copy一份到b.txt

求1到100之间所有质数的和

当前有一泛型为integer的LinkedList，依次向list中添加数字，

一个10G的文件，里面全是IP，找出重复次数大于100次的IP。

因为不限制工具，可以先将数据导入mysql，用mysql处理。

可以使用redis实现