image.png

1. 排序算法

主流的排序算法，按照时间复杂度分为三大类：

1）时间复杂度为 O(n2)

  • 冒泡排序
  • 选择排序
  • 插入排序

2）时间复杂度为O(nlogn)

  • 快速排序
  • 堆排序
  • 归并排序

3) 时间复杂度为线性的排序算法

  • 计数排序
  • 桶排序
  • 计数排序

我们这里挑几种 来说 ：

冒泡排序

顾名思义，向小水泡一样，咕噜咕噜的往前走，一圈遍历，得到一个最大的值；再一圈得到n-1 打的值；
以下面的数组为例，我们分析 一次遍历的数组变化；

image.png

因为排序过程无新增内存空间，空间复杂度：O(1);
因为每一次都是与所有元素（大约）比较，时间复杂度：O(n2);

示例代码如下：

  1. // 从小到大排序
  2. public void bubbleSort(int [] a){
  4.     for(int i = a.length - 1 ; i > 0 ; i--){
  6.         boolean isChange = false;
  7.         int ci = i;
  8.         for(int j = i - 1 ; j >= 0 ; j--){
  9.             if(a[j]  >  a[ci]){  // 大于，交换
  10.                 int temp = a[ci];
  11.                 a[ci] = a[j];
  12.                 a[j] = temp ;
  14.                 ci = j;
  16.                 isChange = true;
  17.             }
  18.         }
  20.         if(!isChange){ // 未发生变化，说明顺序已OK，返回
  21.             return;
  22.         }
  24.     }
  27. }

堆排序

堆排序需要对二叉堆有所了解，堆排序用的是最大堆和最小堆；
最大堆定义：父节点大于任何一个子节点的值；

堆在数组中的表示行为如下：
假设父节点为 p,
左节点： l = 2 p + 1;
右节点: r = 2 p + 2;

以从小到大堆排序的为例，说一下堆排序步骤：
1）将目标数组转化为最大堆；
2）a[0] 与 a[n-1] 交换；
3）将0~n-2 再次排成最大堆；
4）a[0] 与 a[n-2] 交换；
5）重复3、4步骤；

示例代码如下：

  2. // 向下调整
  3. public void down(int [] a ,int start ,int end){
  5.     int p = start;
  6.     int l = 2 * p + 1;
  8.     while(l < end){
  9.         if(a[l] < a[l+1]){ // 取最大的子节点
  10.             l++;
  11.         }
  12.         if(a[p] < a[l]){ // 最大孩子 > 父节点,交换
  13.             int temp = a[p];
  14.             a[p] = a[l];
  15.             a[l] = temp;
  16.         }
  18.         p = l;
  19.         l = 2 * l + 1; 
  20.     }
  22. }
  24. // 堆排序
  25. public void heapSort(int [] a){
  27.     // 将数组转化为最大堆
  28.     for(int i = a.length/2 - 1 ; i >= 0 ; i--){
  29.         down(a, i , a.length - 1);
  30.     }
  32.     // 一次取最大元素，完成排序
  33.     for(int i = a.length - 1; i > 0 ; i--){
  34.         int temp = a[0];
  35.         a[0] = a[i];
  36.         a[i] = temp;
  38.         // 再次转化为最大堆
  39.         down(a,0,i-1);
  40.     }
  42. }

快速排序

快速排序，思想有点类似于2分法；

步骤：

  • 1）定义两个指针，一个left, 一个right; 定义一个基准点，通常去第一个元素；
  • 2）left 向右移动 找大于基准点的值，right 向左自动，找小于基准点的值；
  • 3）同时找到，或者 left > right ,停止；此时 left 或 right 左边是小于的，右边是大于的；
  • 4）分隔数组，0~left, left ~n-1;
  • 5）重复执行以上步骤，完成排序；

依次轮询示例图：
image.png

示例代码：

  1.  // 快速排序
  2.     public void quickSort(int [] a ,int left ,int right){
  3.         int point = left;
  4.         int start = left;
  5.         int end = right;
  7.         if(left < right){
  8.             while(left < right){
  10.                 while(left < right  && a[left] < a[point]){
  11.                     left++;
  12.                 }
  13.                 while(left < right && a[right] > a[point]){
  14.                     right--;
  15.                 }
  17.                 int temp = a[left];
  18.                 a[left] = a[right];
  19.                 a[right] = temp;
  21.             }
  22.             quickSort(a,start, point - 1);
  23.             quickSort(a,point + 1, end);
  24.         }
  25.     }

2. 经典算法

这部分内容为常见的面试算法：

2.1 如何判断链表有环？

示例环如下：
image.png

方式一：遍历链表，将链表存入Set集合，若新入元素在Set集合中已存在，则此链表有环；
这种方式：时间复杂度O(n),空间复杂度也是O(n);

方式二：定义两个指针，同时向右移动，一个步长为1，一个步长为2，两个指针若相遇，则此链表中有环；

示例代码：

链表节点定义：

  1. @Data
  2. public class LinkNode{
  4.     private Integer data;
  5.     private LinkNode next;
  7. }
  1. public class RingLink{
  3.     // 获取一个环形链表
  4.     public LinkNode initData(){
  5.         LinkNode n1 = new LinkNode();
  6.         LinkNode n2 = new LinkNode(2,n6);
  7.         LinkNode n6 = new LinkNode(6,n8);
  8.         LinkNode n8 = new LinkNode(8,n1);
  10.         LinkNode n7 = new LinkNode(7,n2);
  11.         LinkNode n3 = new LinkNode(3,n3);
  12.         LinkNode n5 = new LinkNode(5,n3);
  14.         n1.setData(1);
  15.         n1.setNext(n2);
  16.     }
  18.     // 获取相遇的点
  19.     public LinkNode getBingPoint(LinkNode link){
  20.         LinkNode v1 = link.next;
  21.         LinkNode v2 = link.next.next;
  23.         while(!Objects.equals(v1,v2)){
  24.             v1 = v1.next;
  25.             LinkNode v2 = v2.next.next;
  26.         }
  27.         return v1;
  28.     }
  30.     // 求出环的起始点
  31.     public LinkNode getRingStart(LinkNode bingNode,LinkNode link){
  32.         LinkNode v1 = bingNode.next;
  33.         LinkNode v2 = link.next;
  35.         while(!Objects.equals(v1,v2)){
  36.             v1 = v1.next;
  37.             v2 = v2.next;
  38.         }
  39.         return v1;
  40.     }
  41. }

2.2 最小栈

实现一个栈，该栈带有出栈（pop）、入栈（push）、取最小元素（get_min）3个方法。要保证这3个方法的时间复杂度都是O（1） 最小栈实现；

解法思想：题目说了时间复杂度O(1), 那么肯定要牺牲空间了，

  • 我们准备一个与目标栈A一样的栈B；
  • push() 时 ，如果新入元素比 栈顶元素小，将此元素也入栈B;

再次入栈时，先与栈B比较，如果 < 栈B的栈顶元素，将此元素也入栈 B;

  • pop() 时，如果当前 栈B 的栈顶元素，与 栈 A的栈顶元素一样，那么同时pop();

示例图：
image.png

示例代码：

  2. /**
  3.  *
  4.  * 实现一个栈，该栈带有出栈（pop）、入栈（push）、取最小元素（get_min）3个方法。要保证这3个方法的时间复杂度都是O（1）
  5.  * 最小栈实现
  6.  */
  7. public class MinStack {
  9.     private int [] stackA = new int[1024];
  11.     private int [] stackB = new int[1024];
  13.     private int currentA = 0;
  15.     private int currentB = 0;
  18.     // 入栈
  19.     public void push(int value){
  20.         stackA[currentA] = value;
  21.         if(currentA == 0 || value  <  stackB[currentB - 1]){
  22.             stackB[currentB] = value;
  23.             currentB++;
  24.         }
  26.         currentA++;
  27.     }
  29.     // 出站
  30.     public int pop(){
  31.         int value = stackA[currentA - 1];
  33.         if(value  ==  stackB[currentB - 1]){
  34.             stackB[currentB - 1] = 0;
  35.             currentB--;
  36.         }
  37.         stackA[currentA - 1] = 0;
  38.         currentA--;
  40.         return value;
  41.     }
  43.     // 获取最小值
  44.     public int getMin(){
  45.         if(currentB <= 0){
  46.             return -1;
  47.         }
  48.         return stackB[currentB - 1];
  49.     }
  51.     public static void main(String[] args) {
  52.         MinStack stack = new MinStack();
  53.         stack.push(4);
  54.         stack.push(9);
  55.         stack.push(7);
  56.         stack.push(3);
  57.         stack.push(8);
  58.         stack.push(5);
  60.         System.out.println("stack pop " + stack.pop() + " , min = " + stack.getMin());
  61.         System.out.println("stack pop " + stack.pop() + " , min = " + stack.getMin());
  62.         System.out.println("stack pop " + stack.pop() + " , min = " + stack.getMin());
  63.         System.out.println("stack pop " + stack.pop() + " , min = " + stack.getMin());
  64.         System.out.println("stack pop " + stack.pop() + " , min = " + stack.getMin());
  65.         System.out.println("stack pop " + stack.pop() + " , min = " + stack.getMin());
  67.     }
  69. }

2.3 如何求出最大公约数

辗转相除法

两个正整数a,b(a>b), 它们的最大公约数 = a除以b的余数c和较小数b之间的最大公约数。
例如：10和25, 25除以10=2…5， 那么10和25的最大公约数， 等同于10和余数5的最大公约数。

更相减损术

两个正整数a,b(a>b), 它们的最大公约数 = a-b的差值c和较小数b之间的最大公约数。
例如：10和25, 25-10=15， 那么10和25的最大公约数， 等同于10和15的最大公约数。
两个整数较大时候的场景，取模性能会比较差，更相减损术更适合。但如果两个数相差悬殊，比如10000和1时，更相减损术就要递归9999次。此时可以用方法三

更相减损术+移位（最优）：

  1. 当a,b均为偶数时，gcd(a,b) = 2gcd(a/2,b/2) = 2gcd(a>>1,b>>1)，gcd为方法名；
  2. 当a为偶数，b为奇数时，gcd(a,b) = gcd(a/2,b) = gcd(a>>1,b)；
  3. 当a为奇数，b为偶数时，gcd(a,b) = gcd(a,b/2) = gcd(a,b>>1)；
  4. 当a,b均为奇数，先使用更相减损术运算一次，gcd(a,b) = gcd(b,a-b)，此时a-b必然是偶数，然后又可以继续进行移位运算

ps. >>相当于除以2，<<相当于乘以2

  3.     /**
  4.      *  更相减损数  +  辗转相除 优化版
  5.      */
  6.     public Integer gcd(int a, int b) {
  7.         if (a == b) {
  8.             return a;
  9.         }
  10.         if ((a & 1) == 0 && (b & 1) == 0) { // a b 均为偶数
  11.             return gcd(a >> 1, b >> 1) * 2;
  12.         } else if ((a & 1) != 0 && (b & 1) == 0) { // a b 均为偶数
  13.             return gcd(a, b >> 1);
  14.         } else if ((a&1) == 0 && (b&1)!=0 ){ // a b 均为偶数
  15.             return gcd(a >> 1, b);
  16.         }else{
  17.             int max = Math.max(a, b);
  18.             int min = Math.min(a, b);
  19.             return gcd(max - min, min);
  20.         }
  22.     }

2.4 给定一个数组，求相邻元素的最大差值

  2. /**
  3.  * 给定一个数组，求相邻元素的最大差值
  4.  */
  5. public class MaxArrayGap {
  6.     public int getMaxGap(int [] array){
  7.         int [] minArray = new int[array.length + 1];
  8.         int [] maxArray = new int[array.length + 1];
  10.         boolean [] hasArray = new boolean[array.length + 1];
  13.         int max = array[0];
  14.         int min = array[0];
  15.         // 获取最大值 和最小值
  16.         for (int loop : array) {
  17.             max = Math.max(max, loop);
  18.             min = Math.min(min,loop);
  19.         }
  21.         // 将数据插入到新定义的桶中
  22.         for (int loop : array) {
  23.             // 计算当前值 在桶中的位置 max / array.length = loop/position
  24.             int position = (loop *  array.length) / max;
  25.             minArray[position] = loop;
  26.             maxArray[position] = loop;
  27.             if(hasArray[position]){
  28.                 minArray[position] = Math.min(minArray[position],loop);
  29.                 maxArray[position] = Math.max(maxArray[position],loop);
  30.             }
  32.             hasArray[position] = true;
  33.         }
  35.         // 遍历桶 ，取间隔最大的数据
  36.         int maxGap = 0;
  37.         int previousValue = maxArray[0];
  38.         for (int i = 1; i <= array.length; i++) {
  39.             if(hasArray[i]){
  40.                 maxGap = Math.max(minArray[i] - previousValue,maxGap);
  41.                 previousValue = maxArray[i];
  42.             }
  43.         }
  44.         return maxGap;
  45.     }
  47.     @Test
  48.     public void test() {
  49.         int[] array = {0, 6, 3, 16, 7, 10, 9, 11, 20, 18};
  50.         int maxGap = getMaxGap(array);
  52.         System.out.println("最大的间隔：" + maxGap);
  53.     }
  54. }

2.5 用栈来模拟一个队列，要求实现队列的两个基本操作：入队、出队

思想：使用两个栈，一个用于出，一个用于进。

  1. package com.uu.study;
  3. import org.junit.Test;
  5. import java.util.Stack;
  7. /**
  8.  * 用栈来模拟一个队列，要求实现队列的两个基本操作：入队、出队
  9.  */
  10. public class StackQueue {
  12.     Stack<Integer> a = new Stack<>();
  13.     Stack<Integer> b = new Stack<>();
  15.     public void push(Integer value){
  16.         a.push(value);
  17.     }
  19.     public Integer pop(){
  20.         if(b.isEmpty()){  // b = null ,先填充B
  21.             if(a.isEmpty()){
  22.                return null;
  23.             }
  24.             Integer pop = null;
  25.             while (!a.isEmpty()){
  26.                b.push(a.pop());
  27.             }
  28.         }
  29.         return b.pop();
  30.     }
  32.     @Test
  33.     public void test(){
  34.         StackQueue queue = new StackQueue();
  35.         for (int i = 1; i <= 9; i++) {
  36.             queue.push(i);
  37.         }
  39.         for (int i = 1; i <= 9; i++) {
  40.             System.out.println(queue.pop());
  41.         }
  42.     }
  43. }

2.6 获取全排列的下一个数

示例： 1,2,4,7,6,3
下一个数： 1,2,6,3,4,7

思想：
1）反向获取数组，获取第一个逆序位置；
2）获取逆序位置 到 最后一个数 中 刚刚大于 它的数字进行交换 ；
3）将 第一个逆序位置 到 最后一个 顺序反转；

注：逆序位置 至 最后一位，是有序的（这点要清楚哈😄，理解的关键）；

  1. public class FullNextNum{
  4.     public void getFullNextNum(int [] array){
  5.         // 1) 获取第一个逆序 位置 数
  6.         int unOrderIndex = 0;
  7.         for(int i = array.length - 1 ; i > 0 ; i--){
  8.             if(array[i - 1] < array[i]){
  9.                  unOrderIndex = i;
  10.                  break;
  11.             }
  12.         }
  14.         // 2) 逆序数-1  与 刚刚大于这个数的位置交换
  15.         int temp = array[unOrderIndex - 1];
  16.         for(int i = array.length - 1 ; i > unOrderIndex;  i-- ){
  17.             if(temp < array[i]){
  18.                 array[unOrderIndex - 1] = array[i];
  19.                 array[i] = temp;
  20.                 break;
  21.             }
  22.         }
  24.         // 3) 将 unOrderIndex 后的数据 反转
  25.         for(int i = unOrderIndex,j = array.length - 1; i < j ; i++,j--){
  26.             int t = array[i];
  27.             array[i] = array[j];
  28.             array[j] = t;
  29.         }
  30.     }
  32. }

参见

求两个整数的最大公约数，要尽量优化算法的性能
默认标题_动态分割线_2022-03-15-0.gif