算法之路

一、位运算

1.异或^

定义

1^1=0、10=1、0^1=1、00=0，无进位相加
性质:

0^{n=n n}n=0
异或运算满足交换率，结合律

应用：

不创建新的变量就交换A和B的值（前提：A和B指向的内存是两块）
```
a = a ^ b;
b = a ^ b;
a = a ^ b;
```
算法题：
- 一个数组中有奇数个a,剩余的数都是偶数个，找出这个奇数个的a的值
  
  int eor = 0; 将eor与数组的数全部异或
- 一个数组只用两种数a,b出现了奇数次,剩下的出现偶数次
  
  int eor = 0; 与数组的数全部异或，结果就是a^b
  
  int eor2 = 0; 异或数组中某一位数为1的数(int rightOne = eor & (~eor+1) )，eor2 = a or b；
  
  eor ^ eor2 = b or a;
```
public static void main(String[] args) {
    int[] arr = {1,1,1,3,3,3,3,2};
    int ero = 0;
    for (int i : arr) {
        ero ^= i;
    }
    //ero = a ^ b
    int rightOne = ero & (~ero+1);//提取出最右的1
    int ero2 = 0;
    for (int i : arr) {
        if ((i & rightOne) == 0){
            ero2 ^= i;
        }
    }
    System.out.println(ero2+" "+(ero^ero2));
}
```

二、排序

1.选择排序

定义解释：选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换...总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
时间复杂度：O(n²)

核心代码：

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

2.冒泡排序

时间复杂度：O(n²)

核心代码：

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int e = arr.length - 1; e > 0; e--) {
        for (int i = 0; i < e; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
    }
}

public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

3.插入排序

过程演示第1:13:58位置
基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
时间复杂度：O(n²)

核心代码：

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 1; i < arr.length; i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

4.归并排序

过程演示第34:53位置
时间复杂度O(N*logN)

代码演示：

public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr, 0, arr.length - 1);
}

public static void mergeSort(int[] arr, int l, int r) {
    if (l == r) {
        return;
    }
    int mid = l + ((r - l) >> 1);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

public static void merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = m + 1;
    while (p1 <= m && p2 <= r) {
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m) {
        help[i++] = arr[p1++];
    }
    while (p2 <= r) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
}

算法题：
- 最小和问题
  
  在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
  
  例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、2; 所以小和为1+1+3+1+1+3+4+2=16
  
  左边最小和转化为右边最大和
- 逆序对
  
  在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对。

5.快速排序

引入：荷兰国旗问题：过程演示第1:45:39位置

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

1.[i]<=num,[i]和<=区的下一个数交换，<=区扩一，i++

2.[i]>num,i++
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度 O(N)

时间复杂度：O(n²)

改进后

1）在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分：
左侧<划分值、中间==划分值、右侧>划分值
2）对左侧范围和右侧范围，递归执行
3）时间复杂度为O(N*logN)

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
        int[] p = partition(arr, l, r);
        quickSort(arr, l, p[0] - 1);
        quickSort(arr, p[1] + 1, r);
    }
}

public static int[] partition(int[] arr, int l, int r) {
    int less = l - 1;
    int more = r;
    while (l < more) {
        if (arr[l] < arr[r]) {
            swap(arr, ++less, l++);
        } else if (arr[l] > arr[r]) {
            swap(arr, --more, l);
        } else {
            l++;
        }
    }
    swap(arr, more, r);
    return new int[] { less + 1, more };
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

6.堆排序

过程演示第50:53位置
时间复杂度O(n*logn)

代码：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }
    int size = arr.length;
    swap(arr, 0, --size);
    while (size > 0) {
        heapify(arr, 0, size);
        swap(arr, 0, --size);
    }
}

public static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) /2);
        index = (index - 1)/2 ;
    }
}

public static void heapify(int[] arr, int index, int size) {
    int left = index * 2 + 1;
    while (left < size) {
        int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

算法题：

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

解法：准备小根堆，将数组k+1个数放到小根堆中，弹出堆顶。

public void sortedArrDistanceLessK(int[] arr, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int index = 0;
    for (; index < Math.min(arr.length, k); index++) {
        heap.add(arr[index]);
    }
    int i = 0;
    for (; index < arr.length; i++, index++) {
        heap.add(arr[index]);
        arr[i] = heap.poll();
    }
    while (!heap.isEmpty()) {
        arr[i++] = heap.poll();
    }
}

7.基数排序

过程演示第2:00:07位置
时间复杂度：O(N*K)

8.桶排序

过程演示第2:11:12位置

public static void radixSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    radixSort(arr, 0, arr.length - 1, maxbits(arr));
}

public static int maxbits(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    int res = 0;
    while (max != 0) {
        res++;
        max /= 10;
    }
    return res;
}

public static void radixSort(int[] arr, int begin, int end, int digit) {
    final int radix = 10;
    int i = 0, j = 0;

    int[] bucket = new int[end - begin + 1];
    for (int d = 1; d <= digit; d++) {
        int[] count = new int[radix];
        for (i = begin; i <= end; i++) {
            j = getDigit(arr[i], d);
            count[j]++;
        }
        for (i = 1; i < radix; i++) {
            count[i] = count[i] + count[i - 1];
        }
        for (i = end; i >= begin; i--) {
            j = getDigit(arr[i], d);
            bucket[count[j] - 1] = arr[i];
            count[j]--;
        }
        for (i = begin, j = 0; i <= end; i++, j++) {
            arr[i] = bucket[j];
        }
    }
}

public static int getDigit(int x, int d) {
    return ((x / ((int) Math.pow(10, d - 1))) % 10);
}

9.排序总结

稳定性

排完序之后，是否保留之前数组的相对次序，比如第一个1仍在第二个1前面。

不具备稳定性的排序：选择排序、快速排序、堆排序

具备稳定性的排序：冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

目前没有找到时间复杂度O(N*logN)，额外空间复杂度O(1)，又稳定的排序。
常见的坑
- 归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，有兴趣可以搜“归并排序内部缓存法”（会破坏稳定性，那为什么不用桶排序）
- “原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成O(N^2) （为什么不直接用插入）
- 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01stable sort”（会让空间复杂度变成O(N)，为什么不直接用归并）
- 所有的改进都不重要，因为目前没有找到时间复杂度O(N*logN)，额外空间复杂度O(1)，又稳定的排序。
- 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官。

三、查找

1.二分

过程演示第1:32:24位置
时间复杂度：O(logN)
求中点：int mid = L+((R-l)>>1); L和R为开始结束坐标
算法题：
- 查找有序数组中大于等于num最左侧的下标（小于等于最右侧）
  
  使用二分法，应用在这里，二分法一定是查找到最后
- 数组，无序，任何两个相邻的数不相等，求一个局部最小(该位置的数比左小还比右小)的位置
  
  二分到死

四、递归

1.递归时间复杂度

master公式：T(N)=a*T(N/b)+O(N^d)

五、堆

1，堆结构就是用数组实现的完全二叉树结构
2，完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3，完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4，堆结构的heapInsert与heapify操作
5，堆结构的增大和减少
6，优先级队列结构，就是堆结构

左：2*i+1

右：2*i+2

父：(i-1)/2

六、链表

1.重要技巧

额外数据结构记录（哈希表等）
快慢指针

2.算法题

判断一个链表是否为回文结构

基础：

放到栈里，再弹栈，依次比较。

优化：只把后半部分放到栈里，弹一次比较一次，空间省一半（快慢指针，快指针走两步，慢指针走一步，当快指针走到尾，慢指针来到中点）

进阶：

找到中间值，将后半部分反转，头和尾同时往中间读，比较是否相等
将单向链表按某值划分成左边小、中间相等、右边大的形式

基础：

每个节点读到数组里，在数组里pation，再放回到链表

进阶：

准备六个变量，小值的头尾指针，中值的头尾指针，大值的头尾指针，开始读链表，小于5小值头尾指针指向，再读取一个后，尾指针指向，最后就是分成了三个链表，然后让三个链表头尾相接（注意某个链表是否为空）
单链表环问题

基础：

读链表，把每个节点放到哈希表当中，当出现重复的值就是有环，并返回该相交值，没有则返回null

进阶：

快慢指针，快指针一次走两步，慢指针一次走一步，有环的情况下，快慢指针一定会在环中相遇（且不超过两圈），然后让快指针回到头节点，两个指针再依次往下走，都每次走一步，就会在入环位置相遇
两个单链表相交问题
- 找到各自的尾结点并且统计长度
- 如果end节点不相同，则不相交，否则想同
- 长链表先走差值步，然后两个链表同事走，就能找到相交的点

七、二叉树

1.递归序

二叉树的递归遍历一定会让每个节点到达三次，所生成的递归序可用于二叉树的先、中、后序遍历

2.非递归遍历

先序遍历二叉树：

中序遍历二叉树：

后序遍历二叉树：

代码：

public static void preOrderUnRecur(Node head) {
    System.out.print("pre-order: ");
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();
        stack.add(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            System.out.print(head.value + " ");
            if (head.right != null) {
                stack.push(head.right);
            }
            if (head.left != null) {
                stack.push(head.left);
            }
        }
    }
    System.out.println();
}

public static void inOrderUnRecur(Node head) {
    System.out.print("in-order: ");
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
    }
    System.out.println();
}

public static void posOrderUnRecur1(Node head) {
    System.out.print("pos-order: ");
    if (head != null) {
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(head);
        while (!s1.isEmpty()) {
            head = s1.pop();
            s2.push(head);
            if (head.left != null) {
                s1.push(head.left);
            }
            if (head.right != null) {
                s1.push(head.right);
            }
        }
        while (!s2.isEmpty()) {
            System.out.print(s2.pop().value + " ");
        }
    }
    System.out.println();
}

3.层序遍历

public static void w(Node head){
    if(head == null){
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    while(!queue.isEmpty()){
        Node cur = queue.poll();
        System.out.println(cur.value);
        if(cur.left != null){
            queue.add(cur.left);
        }
        if(cur.right != null){
            queue.add(cur.right);       
        }
    }
}

4.搜索二叉树

定义：每一棵子树都是左节点的值小于根节点的值，右节点的值大于根节点的值

快速判断方法：中序遍历，输出的结果是递增的说明就是搜索二叉树

//方法一：静态查找
public static boolean isBST(Node head) {
    if (head == null) {
        return true;
    }
    LinkedList<Node> inOrderList = new LinkedList<>();
    process(head, inOrderList);
    int pre = Integer.MIN_VALUE;
    for (Node cur : inOrderList) {
        if (pre >= cur.value) {
            return false;
        }
        pre = cur.value;
    }
    return true;
}
public static void process(Node node, LinkedList<Node> inOrderList) {
    if (node == null) {
        return;
    }
    process(node.left, inOrderList);
    inOrderList.add(node);
    process(node.right, inOrderList);
}

//方法二：动态查找，由递归或者栈打印中序的方法改过来都可以
static int preValue = Integer.MIN;
public static boolean isBST(Node head) {
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                if(head.value<=preValue){
                    return false;
                }else{
                    preValue = head.value;
                }
                head = head.right;
            }
        }
    }
    System.out.println();
}

5.完全二叉树

public static boolean isCBT(Node head) {
    if (head == null) {
        return true;
    }
    LinkedList<Node> queue = new LinkedList<>();
    boolean leaf = false;
    Node l = null;
    Node r = null;
    queue.add(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        l = head.left;
        r = head.right;
        if (
            	//遇到不双全的节点之后，又发现当前节点不是叶节点
            	(leaf && (l != null || r != null)) 
            	|| 
            	(l == null && r != null)//有右无左
           ) {
            return false;
        }
        if (l != null) {
            queue.add(l);
        }
        if (r != null) {
            queue.add(r);
        } else {
            leaf = true;
        }
    }
    return true;
}

6.满二叉树

如何判断：得到树的最大深度L和节点数N，当满足N=2^L-1,则为满二叉树

7.平衡二叉树

对于任何一棵树，左树的高度与右树的高度差不超过1

8.算法题

二叉树的序列化和反序列化

就是内存里的一棵树如何变成字符串形式，又如何从字符串形式变成内存里的树

做法：做先序遍历，节点结束以下划线隔开，子树为空就用#代替

八、图

1.宽度优先遍历

public static void bfs(Node node) {
    if (node == null) {
        return;
    }
    //队列
    Queue<Node> queue = new LinkedList<>();
    //set记录表
    HashSet<Node> map = new HashSet<>();
    queue.add(node);
    map.add(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        //要怎么处理
        System.out.println(cur.value);
        
        for (Node next : cur.nexts) {
            if (!map.contains(next)) {
                map.add(next);
                queue.add(next);
            }
        }
    }
}

2.深度优先遍历

public static void dfs(Node node) {
    if (node == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    stack.add(node);
    set.add(node);
    System.out.println(node.value);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                stack.push(cur);
                stack.push(next);
                set.add(next);
                System.out.println(next.value);
                break;
            }
        }
    }
}

3.最小生成树

什么是最小生成树
- 无向图来的
- 保证点的联通性
- 边的权值是最小的
怎么生成

算法一：kruskal(卡鲁斯卡尔)算法
- 取出所有的点，所有的边，每条边一个集合
- 从最小的边开始放，先放2，看有没有生成环，没有，再放3，看有没有生成环，没有，在放5，没有环，再放7，放7有环，不放，放100有环，不放...
  
  怎么判断有环无环？
  
  并查集
  
  每个边一条集合，放入一条边的时候看from点的集合里是否有to点，没有则没有环，并且合并from，to点集合为一个集合
算法二：prim(普利姆)算法

4.Dijkstra算法

适用范围：没有权值为负数的边
定义：必须有一个起点，生成起点到每个点最短距离的表
演示：过程解说第1:59:20处

N、补充知识

1.比较器

一个学生对象，按照id的升序排序

public static class Student {
    public String name;
    public int id;
    public int age;

    public Student(String name, int id, int age) {
        this.name = name;
        this.id = id;
        this.age = age;
    }
}

写一个比较器：

public static class IdAscendingComparator implements Comparator<Student> {
    //返回负数的时候，第一个参数排在最前面
    //返回正数的时候，第二个参数排在前面
    //返回0的时候，谁在前无所谓
    @Override
    public int compare(Student o1, Student o2) {
        return o1.id - o2.id;
    }
}

//调用排序
Arrays.sort(students, new IdAscendingComparator());

如果觉得文章对你有用，请随意赞赏

算法

算法之路

https://luoxi.icu/archives/算法

作者

洛希极限

发布于

2022-10-11

更新于

2023-02-08

许可协议

CC BY 4.0

一、位运算

1.异或^

二、排序

1.选择排序

2.冒泡排序

3.插入排序

4.归并排序

5.快速排序

6.堆排序

7.基数排序

8.桶排序

9.排序总结

三、查找

1.二分

四、递归

1.递归时间复杂度

五、堆

六、链表

1.重要技巧

2.算法题

七、二叉树

1.递归序

2.非递归遍历

3.层序遍历

4.搜索二叉树

5.完全二叉树

6.满二叉树

7.平衡二叉树

8.算法题

八、图

1.宽度优先遍历

2.深度优先遍历

3.最小生成树

4.Dijkstra算法

N、补充知识

1.比较器

作者

发布于

更新于

许可协议

评论