Marlin的博客 | Marlin's Blog

拓扑排序

介绍拓扑排序（Topological Sorting）是一种常用的排序算法，它是对有向无环图（DAG, Directed Acyclic Graph）的一种排序方法。应用拓扑排序在许多领域都有重要的应用。拓扑排序可以用于：检测有向环：如果一个有向图无法进行拓扑排序，说明该图中存在有向环。因此，拓扑排序可以用于检测有向图中是否存在环，这在许多图算法和问题中都有重要的应用。最...

Posted by Marlin on June 8, 2025

素数筛

埃氏筛、欧拉筛

素数筛素数筛是一种用于找出一定范围内所有素数的算法。试除法试除法是一种用于判断一个数是否为素数以及分解质因数的基本方法。判断素数基本思想：对于给定的正整数 n，从 2 开始，依次用每个小于等于 $sqrt{n}$ 的正整数 i 去除 n，如果 n 能被 i 整除，那么 n 就不是素数；如果 n 不能被任何小于等于 $\sqrt{n}$ 的正整数整除，那么 n 就是素数。 1 2 3...

Posted by Marlin on June 6, 2025

建图的三种方式

邻接矩阵、邻接表、链式前向星

建图的三种方式 1.邻接矩阵定义：是一个二维数组matrix[n][n]，其中n是图中顶点的数量。对于无向图，如果顶点i和顶点j之间有边相连，则matrix[i][j]和matrix[j][i]的值为1（若边有权值，则存储权值），否则为0。对于有向图，若存在从顶点i到顶点j的边，则matrix[i][j]为1（或权值），matrix[j][i]为0。优点：可以快速判断任意两个...

Posted by Marlin on June 6, 2025

字符串的切割

字符串的切割题目描述给定一个字符串，请实现一个函数，将该字符串按照某个字符分割，并返回一个包含每个子串的向量。输入样例 1 1 2 参数1:"hello world" 参数2:' ' 输出样例 1 1 ["hello", "world"] 输入样例 2 1 2 参数1:"a b c d e f g h i j k l m n o p q r s t u v w x ...

Posted by Marlin on May 14, 2025

二叉树高频题目

题目一:BFS的两种方式二叉树的层序遍历 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 vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ans;...

Posted by Marlin on May 9, 2025

归并排序

归并排序左部分排好序、右部分排好序，利用merge过程让左右整体有序 merge过程：谁小拷贝谁，直到左右两部分所有的数字耗尽递归实现和非递归实现时间复杂度O(n * log n) 需要辅助数组，所以额外空间复杂度O(n) 归并排序为什么比O(n^2)的排序快？因为比较行为没有浪费！利用归并排序的便利性可以解决很多问题 - 归并分治注意： ...

Posted by Marlin on May 4, 2025

归并分治

归并分治的原理与补充说明原理思考一个大问题的答案是否等于小问题的答案之和：将一个大问题分解为若干个小问题，分别求解这些小问题的答案。如果左右两部分的答案是有序的，并且跨越左右产生的答案可以高效计算，那么整个问题可以通过归并的方式解决。计算“跨越左右产生的答案”：如果加上左、右各自有序这个设定，会获...

Posted by Marlin on May 4, 2025

异或运算的骚操作

异或

异或运算的骚操作问题描述先来个好玩的问题：袋子里有 ( a ) 个白球、( b ) 个黑球。每次从袋子里拿出 2 个球，每个球被拿出的概率均等。如果拿出的是 2 个白球或 2 个黑球，那么就往袋子里重新放入 1 个白球；如果拿出的是 1 个白球和 1 个黑球，那么就往袋子里重新放入 1 个黑球。那么最终袋子里一定会只剩 1 个球，请问最终的球是黑球的概率是多少？用 ( a ) 和 ...

Posted by Marlin on May 2, 2025

二叉树

二叉树的遍历前序遍历访问根节点前序遍历左子树前序遍历右子树 (根左右) 1 2 3 4 5 6 7 8 void preorder(TreeNode* root) { if(root == NULL){ return; } cout << root->val << endl; // 根 preorder(roo...

Posted by Marlin on May 2, 2025

对拍-验证的重要手段

对拍的C++代码实现

前言在算法竞赛和编程中，对拍（Diff Testing）是一种高效验证代码正确性的方法。它通过对比暴力解法（Brute Force）和优化解法（Optimized Solution）的输出，快速发现逻辑错误。本文将提供完整的C++对拍代码，并逐步讲解其实现原理，帮助你轻松应用到自己的项目中。对拍的实现你想要测的方法a 实现复杂度不好但是正确的暴力解法b 实现一个随机样本...

Posted by Marlin on May 1, 2025

Marlin's Blog