Songbirds


春

经典算法

  • ~18.44K 字
  1. 1. 1. 排序
    1. 1.1. 1.快速排序
    2. 1.2. 2.归并排序
    3. 1.3. 3.堆排序
  2. 2. 2.二叉树
    1. 2.1. 0.二叉树简易定义
    2. 2.2. 1.DFS
    3. 2.3. 2. BFS
  3. 3. 3.单调队列
  4. 4. 4.并查集
  5. 5. 5.拓扑排序
  6. 6. 6.线段树

一些最经典（基础）的算法

1. 排序

1.快速排序

只掌握快速排序的递归写法即可

普通快速排序，在数组逆序且有序的情况，会达到最坏的情况，从而被用例卡掉。

普通快速排序
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
public static void sort(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
}

public void quickSort(int[] nums, int left, int right) {
    if (left > right) {
        return;
    }

    int i = left;
    int j = right;
    int base = nums[left];
    while (i < j) {
        while (i < j && nums[j] >= base) {
            j--;
        }
        while (i < j && nums[i] <= base) {
            i++;
        }

        if (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    nums[left] = nums[i];
    nums[i] = base;

    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
}

三数取中快速排序：将arr[left]、arr[mid]、arr[right]排序，取arr[eft]、arr[mid]、arr[right]的中位数，用中位数作为基准，这样就能避免最坏的情况。

三数取中快速排序
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
/**
 * 快速排序 三数取中
 */
public void midValueQuickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    // 三数取中
    dealPivot(arr, left, right);

    int i = left;
    int j = right;
    int base = arr[i];
    while (i < j) {
        while (i < j && arr[j] >= base) {
            j--;
        }
        while (i < j && arr[i] <= base) {
            i++;
        }

        if (i < j) {
            swap(arr, i, j);
        }
    }

    // 交换基准，arr[left + 1] = base
    swap(arr, i, left + 1);

    midValueQuickSort(arr, left, i -1);
    midValueQuickSort(arr, i + 1, right);
}

/**
 * 只需要保证中间的数是三个数的中值，这样简单一点
 */
private void dealPivot(int[] arr, int left, int right) {
        int mid = left + right >> 1;
        if (nums[left] > nums[mid]) {
            swap(nums, left, mid);
        }

        if (nums[mid] > nums[right]) {
            swap(nums, mid, right);
        }

        swap(nums, left, mid);
}

private void swap(int[] arr, int left, int mid) {
    int temp = arr[left];
    arr[left] = arr[mid];
    arr[mid] = temp;
}

2.归并排序

归并排序
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
public static void mergeSort(int[] nums) {
    int[] tempArr = new int[nums.length];
    merge(nums, 0, nums.length - 1, tempArr);
}

public void merge(int[] nums, int left, int right, int[] tempArr) {
    // 递归出口
    if (left >= right) {
        return;
    }

    // 归并
    int mid = (left + right) >> 1;
    merge(nums, left, mid, tempArr);
    merge(nums, mid + 1, right, tempArr);
    // 排序
    sort(nums, left, mid, right, tempArr);
}

public static void sort(int[] nums, int left, int mid, int right, int[] tempArr) {
    int lPos = left;
    int rPos = mid + 1;
    int pos = 0;

    // 在归并之后，每一个子数组都是有序的，
    // 原因：归并的出口时，每个子数组只有一个元素，一个就是有序，后面的多个，都是由此最基础的排序而来
    // 因此可以认为，左半子数组，右半子数组一定有序

    // 这里是将，两个有序子数组中最小的依次放入tempArr中
    while (lPos <= mid && rPos <= right) {
        // 这里使用小于等于，在左半区等于右半区的时候，能保证左半区的在前面，
        // 从而保证该排序的稳定性，规定排序是稳定排序
        if (nums[lPos] <= nums[rPos]) {
            tempArr[pos] = nums[lPos];
            // lPos+1 更容易懂得写法，后面全部采用简化的写法
            lPos++;
            pos++;
        } else {
            tempArr[pos++] = nums[rPos++];
        }
    }

    // 如果左子数组还有
    while (lPos <= mid) {
        tempArr[pos++] = nums[lPos++];
    }

    // 如果右子数组还有
    while (rPos <= right) {
        tempArr[pos++] = nums[rPos++];
    }

    // 将tempArr拷贝到nums数组中
    pos = 0;
    while (left <= right) {
        nums[left++] = tempArr[pos++];
    }
}

3.堆排序

  1. 递归版本
堆排序
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
public static void heapSort(int[] nums) {
    // 注意，这里的n是数组的长度，代表有n个节点
    int n = nums.length;
    // 下标为i的节点 父节点：（i-1）/2 【整除法】 核心点
    // 下标为i的节点 左子节点：i * 2 + 1
    // 下标为i的节点 右子节点：i * 2 + 2

    // 这里从 i = n / 2 - 1 开始的原因：
    // 对于第i个节点，其下标是 i - 1，所以节点i的父节点是 (（i - 1）- 1) / 2 = i / 2 - 1
    // 如果n表示的是下标，这里就不减去1
    // 所以i = n / 2 - 1 表示距离根节点最远的父节点
    for (int i = n / 2 - 1; i >= 0 ; i--) {
        buildMaxHeap(nums, n, i);
    }

    // 建好大顶堆后，根节点，即下标为0处是最大值，
    // 将最大值与数组当前可选部分的最后的下标交换位置，从而将大值放入最后
    for (int i = n - 1; i > 0; i--) {
        // 交换
        int temp = nums[0];
        nums[0] = nums[i];
        nums[i] = temp;
        // 交换后维护大顶堆，维护大顶堆
        // i : 需要维护的元素有i个，维护的元素是根元素
        buildMaxHeap(nums, i, 0);
    }
}

/**
     * 键堆与维护堆
     * @param nums 堆数组
     * @param n 堆数组维护的元素个数
     * @param idx 要维护元素的下标
     */
public static void buildMaxHeap(int[] nums, int n, int idx) {
    // 假定最大的元素的下标是idx
    int largest = idx;
    // 左子节点
    int lson = idx * 2 + 1;
    // 右子节点
    int rson = idx * 2 + 2;

    // 当前节点与其左右子节点中的最大节点，并将坐标赋值
    if (lson < n && nums[largest] < nums[lson]) {
        largest = lson;
    }

    if (rson < n && nums[largest] < nums[rson]) {
        largest = rson;
    }

    // 如果，当前节点idx不是最大节点，则需要交换两个节点的元素，并继续递归的维护大顶堆
    // 如果是，则说明大顶堆已构建完成，不需要再继续维护
    if (largest != idx) {
        int temp = nums[idx];
        nums[idx] = nums[largest];
        nums[largest] = temp;
        // 继续维护堆
        buildMaxHeap(nums, n, largest);
    }
}

2.二叉树

0.二叉树简易定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 二叉树简易定义
 */
class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

1.DFS

  1. DFS的递归实现
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
private List<TreeNode> nodeList = new ArrayList<>();

// 前
public void preOrder(TreeNode node) {
    if (node != null) {
        nodeList.add(node); // 前序
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 中
public void inOrder(TreeNode node) {
    if (node != null) {
        inOrder(node.left);
        nodeList.add(node); // 中序
        inOrder(node.right);
    }
}

// 后
public void postOrder(TreeNode node) {
    if (node != null) {
        postOrder(node.left);
        nodeList.add(node); // 后序
        postOrder(node.right);
    }
}
  1. DFS的迭代实现

迭代使用栈保存节点实现

DFS迭代
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
private List<Integer> nodeList = new ArrayList<>();

// 前序遍历
// 遇到直接打印，先存储右节点，再存储左节点
public void preOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.addFirst(node.val);

    while (!stack.isEmpty()) {
        // 根节点
        TreeNode treeNode = stack.pollFirst();
        nodeList.add(treeNode);
        // 前序是根左右，先压入右节点，再压入左节点，保证每一次先弹出左节点
        // 且每次只弹出一个节点，保证一开始只弹出左节点
        if (treeNode.right != null) {
            stack.addFirst(treeNode.right);
        }
        if (treeNode.left != null) {
            stack.addFirst(treeNode.left);
        }
    }
}


// 中序遍历
// 遇到先一直寻找左子节点，然后弹栈，打印。在将root置为右子节点
public void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Deque<TreeNode> stack = new ArrayDeque<>();
    while (true) {
        // 中序是左根右，需要一直一直遍历左子节点，直到无左子节点，压入栈中
        while (root != null) {
            stack.addFirst(root);
            root = root.left;
        }
        // while循环的终止条件是栈为空
        if (stack.isEmpty()) {
            break;
        }
        // 弹出栈顶的元素，（要打印的根元素）
        root = stack.pollFirst();
        nodeList.add(root.val);
        // 遍历root的右元素
        root = root.right;
    }
}

// 后序遍历
public void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root; // 当前访问的节点
    TreeNode pre = null; // 上一个访问的节点
    while (true) {
        // 中序是左右根，需要一直一直遍历左子节点，直到无左子节点，压入栈中
        while (cur != null) {
            stack.addFirst(cur);
            cur = cur.left;
        }
        if (stack.isEmpty()) {
            break;
        }
        // 获取栈顶的元素，这个元素即将被访问
        TreeNode top = stack.peek();
        // 如果右元素为空，或者右元素是上一个被访问的元素，则这个根元素需要被打印，
        // 同时这个根元素，成为上一个访问的元素
        if (top.right == null || top.right == pre) {
            stack.pollFirst();
            pre = top; // top成为上一个访问的元素
            nodeList.add(top.val);
        } else {
            // 不为空，也没有访问过，那么该节点的右节点成为cur节点
            cur = top.right;
        }
    }
}

2. BFS

  1. BFS的迭代实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static List<Integer> nodeList = new ArrayList<>();

public void bfs(TreeNode root) {
    if (root == null) {
        return;
    }
    Deque<TreeNode> nodeQueue = new ArrayDeque<>();
    nodeQueue.addLast(root);
    while (!nodeQueue.isEmpty()) {
        TreeNode node = nodeQueue.pollFirst();
        nodeList.add(node.val);
        if (node.left != null) {
            nodeQueue.addLast(node.left);
        }
        if (node.right != null) {
            nodeQueue.addLast(node.right);
        }
    }
}
  1. BFS的递归实现（了解）
1

3.单调队列

单调队列，注意与单调栈做出区分。单调队列用于得到当前的某个范围内的最小值或最大值
单调栈：没有长度，当不单调时，只能从栈首弹出。都是在尾部添加。
6247. 从链表中移除节点 - 力扣（LeetCode）：单调栈参考题目
单调队列：一般有长度，除了从尾部弹出，当长度超过限制后，会从首部移除元素。都是在尾部添加。
239. 滑动窗口最大值 - 力扣（LeetCode）：单调队列模板题

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
public static int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> queue = new ArrayDeque<>();
    // 单调队列维护的是将来可能成为最大值的数，队列首部为当前的最大值
    // 对于 1,3,-1,-3,5,3,6,7 数组，1 先进入，当3进入时，3比1大，且3比1年轻，则1无论如何都不可能成为最大值，所以1移除。
    // -1进入时候，-1比3小，所以3不移除，同时-1更年轻（-1可能是后面k的最大值），所以-1入队
    // 此处先处理长为k的，故没有我们手动移除的元素，都是被最大可能性移除的。
    for (int i = 0; i < k; i++) {
        // 此if可以精简，因为无论如何都要queue.add(nums[i]);
        if (queue.isEmpty()) {
            queue.addLast(nums[i]);
        } else {
            // 如果队列尾部的元素，不可能成为最大值，则将其移除
            while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.pollLast();
            }
            queue.addLast(nums[i]);
        }
    }

    int[] ansArr = new int[nums.length - k + 1];

    int idx = 0;
    ansArr[idx] = queue.peekFirst();
    idx++;

    for (int i = k; i < nums.length; i++) {
        // 第 i - k个元素要移除，保持滑动窗口长度为k，如果nums[i-k]等于队列首部的值，则说明队列首部是要移除的
        if (nums[i- k] == queue.peekFirst()) {
            queue.pollFirst();
        }
        // 如果队列尾部的元素，不可能成为最大值，则将其移除
        while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
            queue.pollLast();
        }
        // nums[i] 更年轻（后面有可能成为长度k的最大值），所以nums[i]是一定要入队的
        queue.addLast(nums[i]);
        ansArr[idx] = queue.peekFirst();
        idx++;
    }

    return ansArr;
}

4.并查集

并查集分为并与查两部分，主要用于查找一个对象是否属于一个集合，有两点优化：
路径压缩（找到节点i的祖先节点后，将i直接指向祖先节点，一般必须）。
按秩合并（节rank低的合并到rank高的上去，就是节树高度小的合并到高度大的上去，从而不增加树的高度。有点问题，暂未实现）。
模板题：剑指 Offer II 116. 省份数量 - 力扣（LeetCode）

并查集
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
public static int findCircleNum(int[][] isConnected) {
    // 初始化并查集
    int[] parentArr = init(isConnected.length);

    // 并的部分，将每一个点并起来
    for (int i = 0; i < isConnected.length; i++) {
        for (int j = 0; j < isConnected[i].length; j++) {
            // 第i个省份与j数组中的相连，并起来
            if (isConnected[i][j] == 1) {
                merge(i, j, parentArr);
            }
        }
    }
	
    Set ansSaveSet = new HashSet<>();
    for (int i = 0; i < isConnected.length; i++) {
        // 查的部分
        int parent = findParent(i, parentArr);
        if (!ansSaveSet.contains(parent)) {
            ansSaveSet.add(parent);
        }
    }

    return ansSaveSet.size();
}

// 初始化并查集
public static int[] init(int n) {
    // 创建祖先数组，如果两个对象的祖先数组的值相同，则他们属于同一个集合
    int[] parentArr = new int[n];
    // 初始化的祖先数组都指向自己
    for (int i = 0; i < n; i++) {
        parentArr[i] = i;
    }
    return parentArr;
}

// 查找一个省份的祖先
// 查的部分：city: 省份, parentArr: 祖先数组
public static int findParent(int city, int[] parentArr) {
    // 如果时祖先节点，则一定自己时自己的祖先节点，即：parentArr[city] == city
    if (parentArr[city] == city) {
        return city;
    }
    // 递归查找祖先节点
    int rootCity = findParent(parentArr[city], parentArr);
    // 优化点1：路径合并
    // 找到后，将city的祖先节点设置为rootCity，能够减少节点退化为链表的可能性
    parentArr[city] = rootCity;
    return rootCity;
}

// 合并两个省份到一个集合
// 并的部分，a: 省份，b: 省份，parentArr: 祖先数组
public static void merge(int a, int b, int[] parentArr) {
    // 找到a的祖先
    int parentA = findParent(a, parentArr);
    // 找到b的祖先
    int parentB = findParent(b, parentArr);
    // b成为a的祖先（合并两个祖先）
    parentArr[parentA] = parentB;
}

另外，并查集可以实现判断n个点是否有(无向)环，有向环可以用快慢指针，若需要判断是否有负环，则可以使用最短路的bell-ford算法。

并查集判断是否有无向环，靠的是统计联通分量setCount，初始化为点个数n，若题目给出的两个直接相连的节点，他们的父节点是一不样的，则说明他们不成环，联通分量减去1，最终有setCount-1个环。

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
public class DSU {
    // 联通分量,用来判断环的数量，有setCount个环
    public int setCount;
    public int[] fa;

    public DSU(int n) {
        this.fa = new int[n];
        this.setCount = n;
        for (int i = 0; i < fa.length; i++) {
            fa[i] = i;
        }
    }

    public boolean isUnion(int x, int y) {
        return findFa(x) == findFa(y);
    }

    public int findFa(int x) {
        if (fa[x] == x) {
            return x;
        }
        int rootFa = findFa(this.fa[x]);
        fa[x] = rootFa;
        return rootFa;
    }

    public void union(int x, int y) {
        int xFa = findFa(x);
        int yFa = findFa(y);
        // 连接两个不相连的点，联通分量减1
        if (xFa != yFa) {
            setCount--;
        }
        fa[xFa] = yFa;
    }
}

5.拓扑排序

207. 课程表 - 力扣（LeetCode）：拓扑排序模板题目

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
public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 用来统计入度，入度为0的点则是排在前面的点（可以被选择的点）
    int[] indegressArr = new int[numCourses];
    // 下标i表示第i门课程，courseList[i]表示第i门颗是该集合的先修课，这里可以用集合，是因为都是连着的，也可以用map<List>
    List<List<Integer>> courseList = new ArrayList<>();

    // 因为下标i表示第i门课，所以有几门课就先创建几个list（如果用邻接表数组或者map就不需要）
    for (int i = 0; i < numCourses; i++) {
        courseList.add(new ArrayList<>());
    }


    for (int i = 0; i < prerequisites.length; i++) {
        // 第prerequisites[i][0] 门课的入度+1
        indegressArr[prerequisites[i][0]]++;
        // 第prerequisites[i][1] 门课是prerequisites[i][0]门课的先修课
        courseList.get(prerequisites[i][1]).add(prerequisites[i][0]);
    }

    Deque<Integer> queue = new ArrayDeque<>();
    // 添加入读为0的课到队列，进行选择
    for (int i = 0; i < indegressArr.length; i++) {
        if (indegressArr[i] == 0) {
            queue.add(i);
        }
    }

    while (!queue.isEmpty()) {
        // 先修课
        Integer preCourse = queue.pollFirst();
        // 先修课的后面的课
        List<Integer> nextCourseList = courseList.get(preCourse);

        for (int i = 0; i < nextCourseList.size(); i++) {
            // 这些后修课程，入度-1
            indegressArr[nextCourseList.get(i)]--;
            // 为0的课程加入队列，参加后续删除
            if (indegressArr[nextCourseList.get(i)] == 0) {
                queue.addLast(nextCourseList.get(i));
            }
        }
    }

    for (int i = 0; i < indegressArr.length; i++) {
        // 如果有入度不为0的课，那么则不能修完所有课程
        if (indegressArr[i] != 0) {
            return false;
        }
    }

    return true;
}

6.线段树

单点修改线段树模板：暂记，需要整理

模板题：307. 区域和检索 - 数组可修改

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
class NumArray {

    private Node[] tree;

    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.tree = new Node[nums.length  * 4];
        // 建树
        buildTree(0, nums.length - 1, 1);
    }

    public void update(int index, int val) {
        change(index, val, 1);
    }

    public int sumRange(int left, int right) {
        return query(left, right, 1);
    }

    public void buildTree(int left, int right, int p) {
        tree[p] = new Node();
        tree[p].left = left;
        tree[p].right = right;
        if (left == right) {
            tree[p].sum = nums[left];
            return;
        }
        int mid = (left + right) / 2;
        buildTree(left, mid, p * 2);
        buildTree(mid + 1, right, p * 2 + 1);
        tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
    }

    public void change(int index, int val, int p) {
        if (tree[p].left == tree[p].right) {
            tree[p].sum = val;
            return;
        }
        int mid = (tree[p].left + tree[p].right) / 2;
        if (index <= mid) {
            change(index, val, p * 2);
        } else {
            change(index, val, p * 2 + 1);
        }
        tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
    }

    public int query(int left, int right, int p) {
        if (tree[p].left >= left && tree[p].right <= right) {
            return tree[p].sum;
        }
        int mid = (tree[p].left + tree[p].right) / 2;
        int sum = 0;
        if (left <= mid) {
            sum += query(left, right, p * 2);
        }
        if (right > mid) {
            sum += query(left, right, p * 2 + 1);
        }
        return sum;
    }

    class Node {
        public int left;
        public int right;
        public int sum;

        public Node() {}
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可