Marlin's Blog

「编译当下，重构未来」

最大公约数、同余原理

最大公约数、同余原理 最大公约数 定义 两个正整数 $a$ 和 $b$ 的最大公约数（GCD，Greatest Common Divisor）是指能够同时被 $a$ 和 $b$ 整除的最大的正整数。 求解 1. 辗转相除法 辗转相除法（Euclidean algorithm）是一种求最大公约数的算法。 时间复杂度为 $O((log a)^3)$。 设 $a$ 和 $b$ 为正整...

Posted by Marlin on August 7, 2025

重要排序算法总结

重要排序算法总结 一、排序算法的稳定性 定义： 排序算法的稳定性是指：对于原始序列中两个相等的元素，在排序后它们的相对顺序不发生改变。 ✅ 稳定：相等元素的相对位置在排序前后保持一致。 ❌ 不稳定：相等元素的相对位置可能被颠倒。 稳定性的重要性： 对基础类型（如 int、double）无意义：因为值相同就无法区分，顺序无关紧要。 对非基础类型（如对象、结构体）有...

Posted by Marlin on August 6, 2025

基数排序

基数排序 基于比较的排序 只需要定义好两个对象之间怎么比较即可，对象的数据特征并不关心，很通用。 不基于比较的排序 和比较无关的排序，对于对象的数据特征有要求，并不通用。 计数排序，非常简单，但是数值范围比较大了就不行了。 基数排序的实现细节，非常优雅的一个实现。 关键点：前缀数量分区的技巧、数字提取某一位的技巧。 时间复杂度 $0(n)$，额外空间复杂度 $0(m)$，需要辅助空间做...

Posted by Marlin on August 5, 2025

位运算实现加减乘除

位运算实现加减乘除 前提：位运算实现加减乘除，过程中不能出现任何算数运算符。 加法 利用每一步无进位相加的结果+进位的结果不停计算，直到进位消失。 1 2 3 4 5 6 7 8 9 int add(int a, int b){ int ans = a; // a和b无进位相加的结果 while(b != 0){ // 进位信息不为0时循环 ans = a...

Posted by Marlin on August 5, 2025

位运算的骚操作

位运算的骚操作 题目1 判断一个整数是不是2的幂 1 2 3 4 bool isPowerOfTwo(int n){ return n > 0 && n == (n & -n); // 或者return n > 0 && n & (n-1) == 0; } 题目2 判断一个整数是不是3的幂 1 2 3 boo...

Posted by Marlin on August 4, 2025

位图

bitset

位图 原理 用bit组成的数组来存放值，用bit状态1、0代表存在、不存在，取值和存值操作都用位运算。 限制是必须为连续范围且不能过大。好处是极大的节省空间，因为1个数字只占用1个bit的空间。 常用操作 对位图内元素的操作 增：set(num) // 把num加入到位图 删：reset(num) // 把num从位图中删除 改：flip(num) // 取反num的bi...

Posted by Marlin on August 2, 2025

堆结构常见题

堆结构常见题 1. 合并 k 个有序链表 给定 k 个有序链表，每个链表的元素值都按升序排列，请将它们合并为一个有序链表，并返回合并后的链表。 思路： 创建一个最小堆，将 k 个链表的头结点放入堆中。 取出堆顶的结点，将其指向的下一个结点放入堆中。 重复步骤 2，直到堆为空。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ...

Posted by Marlin on July 29, 2025

双向广搜

双向广度优先搜索 双向广搜常见用途 1:小优化 bfs 的剪枝策略,分两侧展开分支,哪侧数量少就从哪侧展开 双向广搜常见用途 2:重要! 用于解决特征很明显的一类问题 特征:全量样本不允许递归完全展开,但是半量样本可以完全展开 过程:把数据分成两部分,每部分各自展开计算结果,然后设计两部分结果的整合逻辑 用途 1:小优化 bfs 的剪枝策略,分两侧展开分支,哪侧数量少就从哪侧展开 ...

Posted by Marlin on July 29, 2025

自定义比较规则

C++ STL有序关系定制指南

自定义比较规则 在算法竞赛中，当处理自定义结构体时，必须明确定义数据的比较规则：比如按年龄、成绩、姓名等进行升降序排序。 此时，我们需要自定义比较规则，以便对数据进行排序。 数组排序 如果是简单的对于数组进行排序，可通过传递比较函数实现。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct Point { int x, y; };...

Posted by Marlin on July 29, 2025

洪水填充

Flood Fill

洪水填充 洪水填充算法（Flood Fill Algorithm）是一种用于填充图像中指定区域为同一颜色或值的算法。 洪水填充算法的基本思路是：从给定的起始点开始，将起始点所在区域填充为同一颜色或值，然后沿着边界向内扩展，填充相邻的未访问的点，直到填充完所有相邻的未访问的点。 题目 1 岛屿数量 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18...

Posted by Marlin on July 26, 2025

FEATURED TAGS
蓝桥杯 左程云算法 图论 位运算 二进制 数论 CSS HTML 二叉树 堆结构 对拍 对数器 并查集 拓扑排序 注解 JavaScript Servlet Spring
ABOUT ME

Marlin's Blog | 正在建设中······

FRIENDS