算法总结_o(n) 线性单循环,循环次数与问题规模相关,例如顺序查找

衡量算法优劣的主要标准是时间复杂度和空间复杂度。

时间复杂度

1.如果运行时间是常数量级，则用常数1表示。
2.只保留时间函数的最高阶项
3.如果最高阶项存在，则省去最高阶项前面的系数

空间复杂度

1.常量空间，存储空间固定，和输入规模没有直接关系，O(1)
2.线性空间，分配的空间是线性的集合（如数组），大小和输入规模成正比，O(n)
3.二维空间，分配的空间是二维数组集合，集合的长度和宽度和输入规模成正比，O(n²)
4.递归空间，递归操作的内存空间和递归的深度成正比，线性的，O(n)

数组

数组在内存中顺序存储，可以实现逻辑上的顺序表。
内存是由一个个连续的内存单元组成，每一个内存单元都有自己的地址。
数组的优势在于查找劣势在于插入删除，适合读操作多，写操作少的场景。

链表

链表是一种在物理上非连续、非顺序的数据结构。
链表在内存中的存储方式是随机存储，灵活有效的利用零散的碎片空间。
链表适合频繁的插入删除元素。

栈和队列

栈是一种线性的数据结构，先进后出。
队列是一种线性数据结构，先进先出。
数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。
循环队列队尾指针指向的位置永远空出一位，队列的最大容量比数组长度小1。
双端队列，可以先进先出，也可以先进后出。
优先队列，优先级高的先出，基于二叉堆实现。

散列表

散列表也叫哈希表，提供键值的映射关系。
散列表本质上也是一个数组，通过哈希函数将keyh和数组下标进行转换。
java为例，每一个对象都有属于自己的hashcode,是一个整型变量。
最简单的转换是按照数组长度进行取模运算，index=HashCode(key)%Array.length
数组长度有限，当插入的数据越来越多，数组下表可能重复，叫哈希冲突。解决方法：开放寻址法和链表法。
开发寻址法(ThreadLocal)：下标占用，则寻找下一个空挡位置。
链表法（HashMap）:数组中的每一个元素不仅是一个Entry对象还都是一个链表的头结点。
对于JDK中的散列表实现类HashMap来说，影响其扩容的因素：
1.Capacity,HashMap的当前长度。
2.LoadFactor,HashMap的负载因子，默认值为0.75f
需要进行扩容的条件:HashMap.size >=Capacity*LoadFactor
扩容首先创建一个新的空数组长度是原先的两倍，遍历原数组重新Hash
jdk8的HashMap会把链表转化为红黑树。

树

树和图是非线性数据结构。
树的最大深度被称为树的高度或深度。

二叉树

二叉树的每个节点最多有两个孩子节点。
满二叉树：一个二叉树的所有非叶子节点都存在左右孩子，所有叶子节点都在同一层级。
完全二叉树：对于n个节点的二叉树，按层级顺序编号，跟同样深度的满二叉树到n节点的位置相同。（跟满二叉树相比，最后节点之前的节点都齐全）
二叉树可以用链式存储结构，数组表示。
数组存储时，按照层级顺序把二叉树的节点放到数组的对于位置上，如果节点的孩子空缺，数组的相应位置也空出来。
数组存储时，如果父节点的下标是parent,左孩子的下标2*parent+1,右孩子的下标2 *parnet+2
二叉树最主要的应用在于查找操作和维持相对顺序。
二叉查找树（二叉排序树）：
1、如果左子树不为空，左子树上所有节点的值均小于根节点的值。
2、如果右子树不为空，右子树上所有节点的值均大于根节点的值。
3、左右子树都是二叉查找树。
对于节点相对均衡的二叉查找树搜索节点的时间复杂度是O(logn)，和树的深度一样。
深度优先遍历：（可用递归或栈实现）
前序遍历：根节点、左子树、右子树
中序遍历：左子树、根节点、右子树
后序遍历：左子树、右子树、根节点

//二叉树的非递归前序排列
public static void preOrderTraveralWithStack(TreeNode root){
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode treeNode = root;
    while(treeNode!=null || !stack.isEmpty()){
        //迭代访问节点的左孩子，并入栈
        while(treeNode !=null){
            System.out.println(treeNode.data);
            stack.push(treeNode);
            treeNode =  treeNode.leftChild;
        }
        //如果节点没有做孩子，则弹出栈顶节点，访问节点右孩子
        if(!stack.isEmpty()){
            treeNode = stack.pop();
            treeNode =  treeNode.rightChild;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

广度优先遍历：层序遍历（可用队列实现）

//二叉树层序遍历
public static void levelOrderTraversal(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while(!queue.isEmpty()){
        TreeNode node  = queue.poll();
        System.out.println(node.data);
        if(node.leftChild!=null){
            queue.offer(node.leftChild);
        }
        if(node.rightChild != null){
            queueu.offer(node.rightChild);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二叉堆

二叉堆是一种完全二叉树。分为最大堆和最小堆。
最大堆的任何一个父节点的值都大于或等于他的左右子节点的值。
最小堆的任何一个父节点的值都小于或等于它的左右子节点的值。
二叉堆的根节点叫做堆顶，最大堆的堆顶是整个堆中最大元素，最小堆的堆顶是整个堆中最小元素。
二叉堆的自我调整：
1.插入节点:插入完全二叉树最后一个位置，与父节点比较，交换位置上浮O(logn)
2.删除节点：删除处于堆顶的节点，将堆的最后一个节点临时补充，和左右孩子进行比较，更小（大）的交换，下沉。O(logn)
3.构建二叉堆：所有非叶子节点一次下沉。O(n)
二叉堆是顺序存储。

public static void main(String[] args) {
        int[]  array =new int[]{1,3,2,6,5,7,8,9,10,0};
        upAdjust(array);
        System.out.println(Arrays.toString(array));
        array = new int[]{7,1,3,10,5,2,8,9,6};
        buildHeap(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 上浮调整
     * @param array  待调整的堆
     */
    public static void upAdjust(int[] array) {
        int childIndex = array.length -1;
        int parentIndex = (childIndex-1)/2;
        //temp保存插入的叶子节点值，用于最后的赋值
        int temp = array[childIndex];
        while(childIndex>0&&temp<array[parentIndex]){
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (parentIndex-1)/2;
        }
        array[childIndex] = temp;
    }

    /**
     * 下沉调整
     * @param array 待调整的堆
     * @param parentIndex 要下沉的父节点
     */
    public static void downAdJust(int[] array,int parentIndex){
        int temp = array[parentIndex];
        int childIndex = 2*parentIndex+1;
        while(childIndex <array.length){
            //如果有右孩子，且右孩子小于左孩子，定位到右孩子
            if(childIndex+1<array.length && array[childIndex+1]<array[childIndex]){
                childIndex++;
            }
            if(temp <array[childIndex]){
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2*childIndex+1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 构建最小堆
     * @param array 待调整的堆
     */
    public static void buildHeap(int[] array){
        for(int i=(array.length-2)/2;i>=0;i--){
            downAdJust(array,i);
        }
    }
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

优先队列

最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队。（最大堆实现）
最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队。（最小堆实现）

排序算法

时间复杂度O(n²):冒泡排序，选择排序，插入排序，希尔排序（希尔排序特殊性能略优于O（n²),比不上O(nlogn)）
时间复杂度O(nlogn):快速排序，归并排序，堆排序
时间复杂度线性：计数排序，桶排序，基数排序
根据稳定性排序算法分为，稳定排序，不稳定排序。
稳定排序：值相同的元素在排序后仍然保持排序前的顺序。
不稳定排序：值相同额元素在排序后打乱了排序前的顺序。

冒泡排序

//优化版，已经有序不在进行之后的排序，对于后面已经有序的也不再进行排序
public static void sort(int[] array){
        int disOrderLast = array.length-1;
        for(int i=0;i<array.length-1;i++){
            //有序标记，每一轮的初始值都是true
            boolean isSorted = true;
            //无序数列的边界，每次比较只需要比到这里结束
            int sortBorder = disOrderLast;
            for(int j=0;j<sortBorder;j++){
                int temp =0;
                if(array[j]>array[j+1]){
                    temp = array[j];
                    array[j]=array[j+1];
                    array[j+1] = temp;
                    //因为元素有交换，所以不是有序的，标记变为false
                    isSorted = false;
                    //把无序数列的边界更新为最后一次交换元素的位置
                    disOrderLast = j;
                }
            }
            //如何已经有序，不在进行之后的排序
            if(isSorted){
                break;
            }
        }
    }
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

鸡尾酒排序

基于冒牌排序，第一轮从左往右排序，第二轮从右往左，第三轮从左往右。。。。
鸡尾酒排序在大部分元素已经有序的情况下，可以减少回合数，缺点代码量几乎增加一倍。

public static void sort2(int[] array){
        int temp =0;
        for(int i=0;i<array.length/2;i++){
            //有序标记，每一轮的初始值都是true
            boolean isSorted = true;
            //奇数轮，从左向右比较和交换
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    temp = array[j];
                    array[j]=array[j+1];
                    array[j+1] = temp;
                    //因为元素有交换，所以不是有序的，标记变为false
                    isSorted = false;
                }
            }
            //如何已经有序，不在进行之后的排序
            if(isSorted){
                break;
            }
            isSorted = true;
            //偶数轮，从右向左比较和交换
            for(int j=array.length-2-i;j>i;j--){
                if(array[j]<array[j-1]){
                    temp = array[j];
                    array[j]=array[j-1];
                    array[j-1] = temp;
                    //因为元素有交换，所以不是有序的，标记变为false
                    isSorted = false;
                }
            }
            //如何已经有序，不在进行之后的排序
            if(isSorted){
                break;
            }
        }
    }
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
32
33
34
35
36

快速排序

快速排序属于交换排序，每一轮挑选一个基础元素，让其他比它大的元素移动到数列一边，比它小的移动到另一边，拆解数列为两部分。
平均时间复杂度为O(nlong)，最坏为O(n²)
时间复杂度O(logn)

//快速排序递归实现
public static void quickSort(int[] arr,int startIndex,int endIndex){
        if(startIndex>=endIndex){
            return;
        }
        //得到基准元素
        int pivotIndex = partition(arr,startIndex,endIndex);
        //根据基准元素，分成两部分进行递归排序
        quickSort(arr,startIndex,pivotIndex-1);
        quickSort(arr,pivotIndex+1,endIndex);
    }

    /**
     * 分治（双边循环法）
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static  int partition(int[] arr,int startIndex,int endIndex){
        //取第一个位置（也可以随机）的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
        while(left!=right){
            //控制right指针比较并左移
            while(left<right && arr[right]>pivot){
                right--;
            }
            while (left<right&& arr[left]<=pivot){
                left++;
            }
            if(left<right){
                int p = arr[left];
                arr[left] = arr[right];
                arr[right] =p;
            }
        }
        //pivot和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }
    /**
     * 分治（单边循环法）
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static  int  partition2(int[] arr,int startIndex,int endIndex){
        //取第一个位置（也可以随机）的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;
        for(int i=startIndex+1;i<=endIndex;i++){
            if(arr[i]<pivot){
                mark++;
                int p = arr[mark];
                arr[mark]= arr[i];
                arr[i] = p;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

堆排序

堆排序：把无序数组构建成二叉堆，从小到大则为最大堆，从大到小则为最小堆；循环删除堆顶，替换到二叉堆末尾，调整堆产生新的堆顶。
堆排序时间复杂度O(nlogn),空间复杂度O(1)

/**
     * 下沉调整
     * @param array 待调整的堆
     * @param parentIndex 要下沉的父节点
     */
    public static void downAdJust(int[] array,int parentIndex,int length){
        int temp = array[parentIndex];
        int childIndex = 2*parentIndex+1;
        while(childIndex <length){
            //如果有右孩子，且右孩子小于左孩子，定位到右孩子
            if(childIndex+1<length && array[childIndex+1]<array[childIndex]){
                childIndex++;
            }
            if(temp <array[childIndex]){
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2*childIndex+1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 堆升序
     * @param array
     */
    public static void heapSort(int[] array){
        //把无序数组构建成最大堆
        for(int i=(array.length-2)/2;i>=0;i--){
            downAdJust(array,i,array.length);
        }
        System.out.println(Arrays.toString(array));
        for(int i=array.length-1;i>0;i--){
            int temp = array[i];
            array[i] =array[0];
            array[0]= temp;
            downAdJust(array,0,i);
        }
    }
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
32
33
34
35
36
37
38
39
40

计数排序

当数列最大和最小值差距过大时，并不适合使用计数排序。
当数列元素不是整数时，也不适合用计数排序。

 public static int[] countSort(int[] array){
        //得到数列的最大值和最小值，并计算差值
        int max = array[0];
        int min = array[0];
        for(int i=0;i<array.length;i++){
            if(max<array[i]){
                max = array[i];
            }
            if(min>array[i]){
                min = array[i];
            }
        }
        int d = max -min;
        //创建统计数组并统计对应元素的个数
        int[] countArray = new int[d+1];
        for(int i=0;i<array.length;i++){
            countArray[array[i]-min]++;
        }
        //统计数组做变形，后面的元素等于前面元素之和，为了获得元素的位置
        for(int i=1;i<countArray.length;i++){
            countArray[i] +=countArray[i-1];
        }
        //倒序遍历原始数列，从统计数组中找到正确位置，输出到结果数列
        int[] sortedArray = new int[array.length];
        for(int i =array.length-1;i>=0;i--){
            sortedArray[countArray[array[i]-min]-1] = array[i];
            countArray[array[i]-min]--;
        }
        return sortedArray;
    }
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

桶排序

桶排序创建若干个有区间范围的桶，分别对桶内进行排序，输出所有元素。

public static double[] bucketSort(double[] array){
        double max = array[0];
        double min = array[0];
        for(int i=0;i<array.length;i++){
            if(max<array[i]){
                max = array[i];
            }
            if(min>array[i]){
                min = array[i];
            }
        }
        double d = max -min;
        //初始化桶
        int bucketNum = array.length;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
        for(int i=0;i<bucketNum;i++){
            bucketList.add(new LinkedList<Double>());
        }
        //遍历原始数组，将每个元素放入桶中
        for(int i=0;i<array.length;i++){
            int num = (int) ((array[i]-min)*(bucketNum-1)/d);
            bucketList.get(num).add(array[i]);
        }
        //对每个桶内部进行排序
        for(int i=0;i<bucketList.size();i++){
            //JDK底层采用了归并排序或归并的优化版本
            Collections.sort(bucketList.get(i));
        }
        //输出全部元素
        double[] sortedArray = new double[array.length];
        int index =0;
        for(LinkedList<Double> list:bucketList){
            for(double element:list){
                sortedArray[index]=element;
                index++;
            }
        }
        return  sortedArray;
    }
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
32
33
34
35
36
37
38
39

希尔排序

又称为缩小增量排序，基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。

static void shell_sort(int[] numbers, int start, int end) {
        int increment = end - start + 1;    //初始化划分增量
        int temp=0;
        do {    //每次减小增量，直到increment = 1
            increment = increment / 3 + 1;
            for (int i = start + increment; i <= end; ++i) {    //对每个划分进行直接插入排序
                if (numbers[i - increment] > numbers[i]) {
                    temp = numbers[i];
                    int j = i - increment;
                    do {    //移动元素并寻找位置
                        numbers[j + increment] = numbers[j];
                        j -= increment;
                    } while (j >= start && numbers[j] > temp);
                    numbers[j + increment] = temp;  //插入元素
                }
            }
        } while (increment > 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

归并排序

建立在归并操作上的一种有效的排序算法。该算法是采用分治法。将一个数组不断拆分为2个数组，最后没法拆分然后向上合并数组。

/**
     * 递归使用归并排序，对arr[l...r]的范围进行排序（前闭区间，后闭区间）
     * @param arr 待排序数组
     * @param left 数组左
     * @param right
     */
    private static void mergeSort(int[] arr, int left, int right) {
        //对于递归，要处理递归到底的判断，这里就是left>=right。
        if( left >= right)
            return;

        int mid = (left+right)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right); //将左右两部分，利用临时数组进行归并
    }

    /**
     * 将arr[l...mid]和arr[mid+1...r]两部分进行归并
     * @param arr
     * @param left
     * @param mid
     * @param right
     * i:临时数组左边比较的元素下标；j:临时数组右边比较的元素的下标；k:原数组将要放置的元素下标
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] aux = new int[right - left + 1]; //临时辅助数组
        for (int i = left; i <= right; i++)
            aux[i - left] = arr[i]; /*减去的left是原数组相对于临时数组的偏移量*/

        int i = left, j = mid + 1;
        for (int k = left; k <=right; k++) {
            if (i > mid) { //检查左下标是否越界
                arr[k] = aux[j - left];
                j++;
            } else if (j > right) { //检查右下标是否越界
                arr[k] = aux[i - left];
                i++;
            } else if (aux[i - left] <= aux[j - left]) {
                arr[k] = aux[i - left];
                i++;
            } else {
                arr[k] = aux[j - left];
                j++;
            }
        }
    }
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

查找算法

顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表
顺序查找也称为线性查找属于无序查找算法，时间复杂度O(n)

int sequenceSearch(int a[],int value,int n){
    for(int i=0;i<n;i++){
        if(a[i] == value){
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8

二分查找

元素必须是有序的，如果是无序的则要先进行排序操作。
也称为是折半查找，属于有序查找算法，时间复杂度为O(log2n)

//二分查找（折半查找）
int BinarySearch1(int a[], int value, int n){
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high){
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}
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

插值查找

基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
时间复杂度均为O(log2(log2n))

int InsertionSearch(int a[], int value, int low, int high)
{
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
        return InsertionSearch(a, value, mid+1, high);
}
1
2
3
4
5
6
7
8
9
10

知名算法

LRU算法/最近最少使用算法

使用哈希链表实现.

class Node{
        public Node pre;
        public Node next;
        private String key;
        private String value;
        Node(String key,String value){
            this.key = key;
            this.value = value;
        }
    }
    private Node head;
    private Node end;
    //缓存存储上限
    private int limit;
    private HashMap<String,Node> hashMap;
    public LRUTest(int limit){
        this.limit = limit;
        hashMap = new HashMap<>();
    }
    public String get(String key){
        Node node = hashMap.get(key);
        if(node == null){
            return null;
        }
        refreshNode(node);
        return node.value;
    }
    public void put(String key,String value){
        Node node = hashMap.get(key);
        if(node ==null){
            //如果key不存在，则插入key-value
            if(hashMap.size()>=limit){
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            node  = new Node(key,value);
            addNode(node);
            hashMap.put(key,node);
        }else{
            //如果key不存在，则刷新key-value
            node.value = value;
            refreshNode(node);
        }
    }
    private void remove(String key){
        Node node  = hashMap.get(key);
        removeNode(node);
        hashMap.remove(key);
    }
    
    /**
     * 刷新被访问的节点位置
     * @param node
     */
    private void refreshNode(Node node) {
        //如果访问的是尾节点，则无需移动节点
        if(node ==end){
            return;
        }
        //移除及节点
        removeNode(node);
        addNode(node);
    }

    /**
     * 删除节点
     * @param node
     * @return
     */
    private String removeNode(Node node) {
       if(node == head && node ==end){
           //移除唯一的节点
           head = null;
           end =null;
       }else if(node ==end){
           //移除尾节点
           end = end.pre;
           end.next = null;
       }else if(node ==head){
           //移除头部节点
           head = head.next;
           head.pre = null;
       }else{
           //移除中间节点
           node.pre.next = node.next;
           node.next.pre = node.pre;
          
       }
       return node.key;
    }

    /**
     * 尾部插入节点
     * @param node
     */
    private void addNode(Node node) {
        if(node != null){
           end.next = node;
           node.pre = end;
           node.next = null;
        }
        end = node;
        if(head ==null){
            head = node;
        }
    }
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

面试中常见算法

如何判断链表有环

追及问题，定义2个指针，一个指针步长1，一个指针步长2，如果相遇则有环；第一次相遇到第二次相遇则为环长；头结点到入环点的距离等于首次相遇点回到入环点的距离，可得入环结点。

/**
*判断是否有环
*/
public static boolean isCycle(Node head){
    Node p1 = head;
    Node p2 = head;
    while(p2!=null && p2.next!=null){
        p1=p1.next;
        p2 = p2.next.next;
        if(pi == p2){
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最小栈的实现

实现一个栈，有入栈，出栈，取最小元素，用两个栈实现,辅助栈存储最小元素。

 private Stack<Integer> mainStack = new Stack<Integer>();
 private Stack<Integer> minStack = new Stack<Integer>();
    public void push(int element){
        mainStack.push(element);
        //辅助栈为空或者新元素小于等于辅助栈栈顶，则新元素压入辅助栈
        if(minStack.isEmpty()||element<=minStack.peek()){
            minStack.push(element);
        }
    }
    public Integer pop(){
        //如果出栈元素和辅助栈栈顶元素相同，辅助栈出栈
        if(mainStack.peek().equals(minStack.peek())){
            minStack.pop();
        }
        return minStack.pop();
    }
    public int getMin() throws Exception {
        if (mainStack.isEmpty()) {
            throw new Exception("stack is empty");
        }
        return minStack.peek();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

求出最大公约数

辗转相除法/欧几里得算法：两个正整数a,b(a>b),他们的公约数等于a除以b的余数c和b之间的最大公约数。（取模运算复杂）
更相减损术：两个正整数a,b(a>b),他们的公约数等于a-b的差c和较小数b的最大公约数。（性能不稳定）

//辗转相除法和更相减损术结合
public static int gcd(int a,int b){
    if(a==b){
        return a;
    }
    if((a&1)==0 && (b%1)==0){
        return gcd(a>>1,b>>1)<<1;
    }else if((a&1)==0 && (b&1)!=0){
        return gcd(a>>1,b);
    }eles if((a&1)!=0  && (b&1)==0){
        return gcd(a,b>>1);
    }else{
        int big =a>b?a:b;
        int small = a>b?b:a;
        return gcd(big-small,small);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

判断一个数是否是2的整数次幂

计算n&(n-1)的结果是不是0

public static boolean isPowerOf2(int n){
    return (n&(n-1)) == 0;
}
1
2
3